Abstract | ||
---|---|---|
In Constraint Programming, constraint propagation is a basic component of constraint satisfaction solvers. Here we study constraint propagation as a basic form of inference in the context of first-order logic (FO) and extensions with inductive definitions (FO(ID)) and aggregates (FO(AGG)). In a first, semantic approach, a theory of propagators and constraint propagation is developed for theories in the context of three-valued interpretations. We present an algorithm with polynomial-time data complexity. We show that constraint propagation in this manner can be represented by a datalog program. In a second, symbolic approach, the semantic algorithm is lifted to a constraint propagation algorithm in symbolic structures, symbolic representations of classes of structures. The third part of the article is an overview of existing and potential applications of constraint propagation for model generation, grounding, interactive search problems, approximate methods for ∃∀SO problems, and approximate query answering in incomplete databases. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2499937.2499938 | ACM Trans. Comput. Log. |
Keywords | Field | DocType |
approximate query answering,symbolic representation,symbolic approach,basic component,semantic algorithm,constraint propagation,symbolic structure,first-order logic,inductive definitions,approximate method,constraint satisfaction solvers,constraint propagation algorithm,artificial intelligent,first order logic,algorithms,polynomial time | Discrete mathematics,Constraint satisfaction,Local consistency,Constraint programming,Constraint graph,Constraint satisfaction problem,Theoretical computer science,Concurrent constraint logic programming,Constraint logic programming,Mathematics,Binary constraint | Journal |
Volume | Issue | ISSN |
14 | 3 | 1529-3785 |
Citations | PageRank | References |
3 | 0.37 | 67 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Johan Wittocx | 1 | 109 | 9.37 |
Marc Denecker | 2 | 1626 | 106.40 |
Maurice Bruynooghe | 3 | 2767 | 226.05 |