README.md

chr_book

Valuable code and exercises about the book "Constraint Handling Rules (2009)" by Thom Frühwirth.

Note that most of the examples in this book cannot work directly in SWI-Prolog (e.g. incomplete code, lacking necessary rules and built-ins, not compatible with Prolog flattening style, using different operation semantics, bugs, etc). The major purpose of this repository is to make them work, followed by some experiments and extensions.

Selected Examples

• Chapter 2: My first CHR programs
  • Greatest common divisor
  • Prime numbers Sieve of Eratosthenes
  • Exchange sort
  • CYK algorithm
  • Merge sort
  • Hamming’s problem
• Chapter 6: Rule-based and graph-based formalisms in CHR
  • Production rule systems
  • Event condition action rules
  • Term rewriting systems
• Chapter 8: Finite domain constraint solvers
  • Boolean algebra and propositional logic
    • Boolean cardinality
    • Resolution
      • Davis–Putnam procedure
  • Consistency techniques
    • Arc consistency
      • Finite domain
        • Interval domains
        • Enumeration_domain
        • N-Queen
    • Path consistency
      • Temporal reasoning
        • PA network
        • Simple-Temporal-Network (STN)
  • Sudoku (try-most-constrained-field-first)
• Chapter 9: Infinite domain constraint solvers
  • Linear polynomial equation solving
    • Variable elimination
    • Gaussian elimination
    • Fourier’s algorithm
  • Description logic
  • Rational trees
  • Feature terms
• Chapter 10: Union-find algorithm
  • Traditional union-find
  • Generalized union-find