Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914871583440896 |
|---|---|
| author | Mottet, Antoine Nagy, Tomáš Pinsker, Michael Wrona, Michał |
| author_facet | Mottet, Antoine Nagy, Tomáš Pinsker, Michael Wrona, Michał |
| contents | We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities $n \geq 3$) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu, ten Cate, Lutz, and Wolter. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures, and show the applicability of infinite-domain CSPs to other fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_07531 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough Mottet, Antoine Nagy, Tomáš Pinsker, Michael Wrona, Michał Logic in Computer Science We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities $n \geq 3$) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu, ten Cate, Lutz, and Wolter. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures, and show the applicability of infinite-domain CSPs to other fields. |
| title | Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2102.07531 |