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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online)
National Category
Computer Science
Identifiers
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 (print)OAI: oai:DiVA.org:liu-79514DiVA: diva2:543174
Conference
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

Authority records BETA

Wrona, Michal

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf