Journal article icon

Journal article

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns

Abstract:

Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbid- ding patterns (generic sub-instances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances,...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.23638/LMCS-13(4:26)2017

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Zivny, S
Publisher:
IfCoLog (International Federation of Computational Logic) Publisher's website
Journal:
Logical Methods in Computer Science Journal website
Volume:
13
Issue:
4
Pages:
1-32
Publication date:
2017-12-27
Acceptance date:
2017-11-06
DOI:
EISSN:
1860-5974
ISSN:
1860-5974
Pubs id:
pubs:743546
URN:
uri:a983682c-3cd0-40b7-83d1-49e30d731d61
UUID:
uuid:a983682c-3cd0-40b7-83d1-49e30d731d61
Local pid:
pubs:743546
Paper number:
4

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP