liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Syntactically Characterizing Local-to-Global Consistency in ORD-Horn
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
2012 (English)Conference paper (Other academic)
Abstract [en]

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)
National Category
Computer Science
URN: 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: diva2:543174
18th International Conference on Principles and Practice of Constraint Programming (CP-2012), 8-12 October, Québec City, Canada
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2014-11-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Wrona, Michal
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link