Propositional Encoding of Constraints over Tree-Shaped Data
Alexander Bau, Johannes Waldmann · arXiv (Cornell University) · 2013
We present a functional programming language for specifying constraints over tree-shaped data. The language allows for Haskell-like algebraic data types and pattern matching. Our constraint compiler CO4 translates these programs into satisfiability problems in propositional logic. We present an application from the area of automated analysis of (non-)termination of rewrite systems.