15 Concurrent Constraint Programming

In the remainder of the lecture, we introduce concurrent constraints programming in depth and apply it to natural language processing.

In this chapter, we recall the general ideas of concurrent constraint programming and introduce the corresponding programming concepts provided by Oz. We illustrate these concepts at some small examples relevant to computational linguistics.

We consider agreement checking based on finite domain constraints and present a solver for proposition logics which is based on disjunctive propagators. Furthermore, we introduce finite set constraints that will be needed all over the place in the follow up chapters.

• 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