Syntactically Characterizing Local-to-Global Consistency in ORD-Horn
2012 (English)Conference paper (Other academic)
Establishing local consistency is one of the most frequently used algorithmic techniques in constraint satisfaction in general and in spatial and temporal reasoning in particular. A collection of constraints is globally consistent if it is completely explicit, that is, every partial solution may be extended to a full solution by greedily assigning values to variables one at a time. We will say that a structure B has local-to-global consistency if establishing local-consistency yields a globally consistent instance of CSP(B) .
This paper studies local-to-global consistency for ORD-Horn languages, that is, structures definable over the ordered rationals (ℚ; < ) within the formalism of ORD-Horn clauses. This formalism has attracted a lot of attention and is of crucial importance to spatial and temporal reasoning. We provide a syntactic characterization (in terms of first-order definability) of all ORD-Horn languages enjoying local-to-global consistency.
Place, publisher, year, edition, pages
Springer Berlin Heidelberg , 2012. 704-719 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online)
IdentifiersURN: urn:nbn:se:liu:diva-79514DOI: 10.1007/978-3-642-33558-7_51ISBN: 978-3-642-33557-0 (print)ISBN: 978-3-642-33558-7 (online)OAI: oai:DiVA.org:liu-79514DiVA: diva2:543174
18th International Conference on Principles and Practice of Constraint Programming (CP-2012), 8-12 October, Québec City, Canada