<< Prev
- Up -
Next >>
Part IV: Concurrent Constraint Programming and Semantic Underspecification
15 Concurrent Constraint Programming
15.1 General Ideas (Recalled)
15.1.1 Combinatoric Explosion
15.1.2 Constraint Store and Propagators
15.1.3 Distribution
15.1.4 Ambiguities versus Disjunction
15.2 Finite Domain Constraints
15.2.1 FD-Membership
15.2.2 FD-Propagators
15.2.3 FD-Reflect
15.2.4 FD-Distribution
15.3 Finite Domains and Agreement Testing
15.3.1 What's the Problem
15.3.2 Finite Domains as Abstract Data Structures
15.3.3 Finite Domain Functor
15.3.4 Domains of Atoms and Integers
15.3.5 Auxilary Arithmetic Functions
15.3.6 Products of Domains
15.3.7 Application to Agreement Checking
15.3.8 The Complete Package:
domains.pkg
15.4 Finite Set Constraints
15.5 Disjunctive Propagators
15.5.1 or-Statements
15.5.2 Operational Semantics
15.5.3 Propositional Logic
15.5.4 Choice Points versus Choice Variables
15.6 Selection Constraint
15.6.1 Element Constraint
Syntax and Semantics
Example (Finite Functions)
Propagation Rules
15.6.2 Finite Set Selection Constraints
Syntax and Semantics
Example
15.7 Reified Constraints
15.8 Summary
15.9 Exercises
15.9.1 Finite Domains
15.9.2 Non-deterministic parsing
16 Constraints in Semantic Underspecification
16.1 Semantic Underspecification
16.1.1 Compositionality
16.1.2 Scope Underspecification
16.1.3 Formulas as Trees
16.1.4 Graphs Describing Trees
16.1.5 Dominance Constraints
16.1.6 Syntax-Semantics Interface
16.1.7 Exercises
16.2 Complexity of Dominance Constraints
16.2.1 Dominance Constraints
16.2.2 Constraints as Graphs
16.2.3 Partitioning Trees
16.2.4 A Generate and Test Algorithm
16.2.5 Complexity of Dominance Constraints
16.3 Solving Dominance Constraints Efficiently
16.3.1 Sets of Nodes
16.3.2 Encoding Nodes as Records
16.3.3 Translation to Set Constraints
16.3.4 Treeness Condition
16.3.5 Encoding Dominance Constraints
16.3.6 The Solver as a Module
16.3.7 Solution Predicate
16.3.8 Graphical Output with DaVinci
16.3.9 Exercises
16.3.10 Complete Solver
16.4 Summary
<< Prev
- Up -
Next >>
Denys Duchier
,
Claire Gardent
and
Joachim Niehren
Version 1.3.99 (20050412)