Title: Constraint propagation for first-order logic and inductive definitions
Authors: Wittocx, Johan
Denecker, Marc ×
Bruynooghe, Maurice #
Issue Date: 2013
Publisher: Association for Computing Machinery
Series Title: ACM Transactions on Computational Logic vol:14 issue:3 pages:1-45
Article number: 17
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
(\foid) and aggregates (\foagg). 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 {\em
symbolic structures}, symbolic representations of classes of
structures. The third part of the paper is an overview of existing
and potential applications of constraint propagation for model
generation, grounding, interactive search problems, approximate
methods for exists/forall Second Order problems, and approximate query
answering in incomplete databases.
ISSN: 1529-3785
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
final.pdf Published 535KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science