When symmetries are enough: collapsing the bounded width hierarchy for infinite-domain CSPs

Autor:	Mottet, Antoine, Nagy, Tomáš, Pinsker, Michael, Wrona, Michał
Jazyk:	angličtina
Rok vydání:	2021
Předmět:	FOS: Computer and information sciences Computer Science - Logic in Computer Science Computer Science::Computational Complexity Logic in Computer Science (cs.LO)
Popis:	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. journal version (26 pages)
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51e24cefc620fd2ba0321cf0f52c64fd http://arxiv.org/abs/2102.07531 Zobrazit plný text záznamu