Conference item
Galois connections for patterns: an algebra of labelled graphs
- Abstract:
- A pattern is a generic instance of a binary constraint satisfaction problem (CSP) in which the compatibility of certain pairs of variable-value assignments may be unspecified. The notion of forbidden pattern has led to the discovery of several novel tractable classes for the CSP. However, for this field to come of age it is time for a theoretical study of the algebra of patterns. We present a Galois connection between lattices composed of sets of forbidden patterns and sets of generic instances, and investigate its consequences. We then extend patterns to augmented patterns and exhibit a similar Galois connection. Augmented patterns are a more powerful language than flat (i.e. non-augmented) patterns, as we demonstrate by showing that, for any k≥ 1, instances with tree-width bounded by k cannot be specified by forbidding a finite set of flat patterns but can be specified by a finite set of augmented patterns. A single finite set of augmented patterns can also describe the class of instances such that each instance has a weak near-unanimity polymorphism of arity k (thus covering all tractable language classes).We investigate the power of forbidding augmented patterns and discuss their potential for describing new tractable classes.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 698.9KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-030-72308-8_9
Authors
Contributors
+ Cochez, M
- Role:
- Editor
+ Croitoru, M
- Role:
- Editor
+ Marquis, P
- Role:
- Editor
+ Rudolph, S
- Role:
- Editor
- Publisher:
- Springer
- Host title:
- Proceedings of the International Workshop on Graph Structures for Knowledge Representation and Reasoning
- Volume:
- 12640
- Issue:
- 2020
- Pages:
- 125-150
- Series:
- Lecture Notes in Computer Science
- Publication date:
- 2021-03-16
- Acceptance date:
- 2021-01-15
- Event title:
- International Workshop on Graph Structures for Knowledge Representation and Reasoning (GKR 2020)
- Event location:
- Online
- Event website:
- https://graphkr.github.io/
- Event start date:
- 2020-09-05
- Event end date:
- 2020-09-05
- DOI:
- EISSN:
-
1611-3349
- ISSN:
-
0302-9743
- ISBN:
- 9783030723071
- Language:
-
English
- Keywords:
- Pubs id:
-
1171073
- Local pid:
-
pubs:1171073
- Deposit date:
-
2021-04-26
Terms of use
- Copyright holder:
- Cohen et al.
- Copyright date:
- 2021
- Rights statement:
- © The Author(s) 2021. This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Notes:
- This paper was presented at the 6th International Workshop, Graph Structures for Knowledge Representation and Reasoning (GKR 2020), 5th September 2020.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record