Paper Info
Title
Constraint Propagation for First-Order Logic and Inductive Definitions
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 Wittocx11099.37
Marc Denecker21626106.40
Maurice Bruynooghe32767226.05