Table of Contents

• Table of Contents
• 1 Introduction
• 2 Constraint Satisfaction Problems
  • 2.1 What is a CSP?
  • 2.2 Constraint-based Representation of Assignments
    • 2.2.1 Basic Constraints
  • 2.3 Improving partial info by constraint propagation
    • 2.3.1 Non-Basic Constraints
  • 2.4 Searching For Solutions
    • 2.4.1 Propagation
    • 2.4.2 Distribution
• 3 Efficient Encodings of Finite Domains
  • 3.1 Finite Domain Constraints
  • 3.2 Simple Example
  • 3.3 Encoding Products of Finite Domains
    • 3.3.1 Establishing a bijection between tuples and integers
    • 3.3.2 Implementation
      • Features and Attributes
      • Init Method
      • Encode Method
      • Decode Method
      • Niceties
  • 3.4 Application to German Agreement
    • 3.4.1 Lexicon
  • 3.5 Application
    • 3.5.1 Implementation
  • 3.6 Projections
    • 3.6.1 Selection Constraint
    • 3.6.2 Partial Agreement
    • 3.6.3 Application
• 4 Dominance Constraints
  • 4.1 Descriptions of Trees
    • 4.1.1 DTree Grammar
    • 4.1.2 Underspecified Semantic Representation
  • 4.2 Dominance Constraints
    • 4.2.1 Models of Dominance Constraints
    • 4.2.2 Solved Forms of Dominance Constraints
  • 4.3 Solving Dominance Constraints
    • 4.3.1 Well-Formedness Constraints
      • Characteristic Set Constraints
      • Well-Formedness Clauses
      • Disjunctive Propagator
    • 4.3.2 Problem-Specific Constraints
    • 4.3.3 Searching for Solved Forms
  • 4.4 Implementation
    • 4.4.1 MakeNode
    • 4.4.2 Characteristic Constraints
    • 4.4.3 Well-Formedness Clauses
    • 4.4.4 Solver class
      • Attributes
      • init method
      • var2node method
      • lab method
      • dom method
      • labeled method
      • labeled method
  • 4.5 Application
    • 4.5.1 Implementation
• 5 Dependency Parsing
  • 5.1 Overview
  • 5.2 Formal Presentation
    • 5.2.1 Dependency Tree
    • 5.2.2 Well-Formedness Principles
  • 5.3 Improving Lexical Economy
  • 5.4 Constraint Model
    • 5.4.1 Representation
      • Lexical Attributes
      • Daughter Sets
      • Lexicon
    • 5.4.2 Lexical Constraints
    • 5.4.3 Valency Constraints
    • 5.4.4 Role Constraints
    • 5.4.5 Treeness Constraints
    • 5.4.6 Yield and Acyclicity
    • 5.4.7 Solving the CSP
  • 5.5 Implementation
    • 5.5.1 Demo Session
    • 5.5.2 Entry.oz
      • Agreement
      • Category
      • Roles
      • Verb Prefixes And Marks
      • Encoder of Lexicon Entry
    • 5.5.3 Lexicon.oz
      • Proper Names
      • Pronouns
      • Common Nouns
      • Determiners
      • Verbs
      • Auxiliaries
      • Modals
      • Adjectives
      • Miscellaneous
    • 5.5.4 Gamma.oz
      • Variables
      • Predicates
    • 5.5.5 Parser.oz
      • Variables And Helper Functions
      • MakeNode
      • ParsePredicate
    • 5.5.6 DG.oz
    • 5.5.7 DTreeFrame.oz
• 6 Constraint Programming Bestiary
  • 6.1 Constraint Store
  • 6.2 Constraint Variables
    • 6.2.1 FD Variables
    • 6.2.2 FS variables
  • 6.3 Constraints And Propagators
  • 6.4 Encapsulation And Computation Spaces
  • 6.5 Search
  • 6.6 Search Predicates
  • 6.7 Disjunctive Propagator
  • 6.8 Reified Constraints
  • 6.9 Selection Constraints
    • 6.9.1 Select Package
    • 6.9.2 FD Selection Constraint
    • 6.9.3 FS Selection Constraint
    • 6.9.4 FS Selection Union Constraint
• A Code Files
  • A.1 Encode.oz
  • A.2 SmallLexicon.oz
  • A.3 SmallTest.oz
  • A.4 SmallPartial.oz
  • A.5 SmallPartialTest.oz
  • A.6 Dominance.oz
  • A.7 DomDemo.oz
  • A.8 Entry.oz
  • A.9 Lexicon.oz
  • A.10 Gamma.oz
  • A.11 Parser.oz
  • A.12 DG.oz
  • A.13 DTreeFrame.oz
• Bibliography