On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width

DOI10.1145/3373718.3394781MaRDI QIDQ5145694zbMATH OpenOpenAlexFDO

Authors Michał Wrona

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.04145

zbMATH Keywords

constraint satisfaction problemsbounded widthlocal consistencybounded relational widthbounded strict widthfinitely bounded homogeneous structures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Equational classes, universal algebra in model theory (03C05) Applications of universal algebra in computer science (08A70)

Abstract: The relational width of a finite structure, if bounded, is always (1,1) or (2,3). In this paper we study the relational width of first-order expansions of finitely bounded homogeneous binary cores where binary cores are structures with equality and some anti-reflexive binary relations such that for any two different elements a, b in the domain there is exactly one binary relation R with (a, b) in R. Our main result is that first-order expansions of liberal finitely bounded homogeneous binary cores with bounded strict width have relational width (2, MaxBound) where MaxBound is the size of the largest forbidden substructure, but is not less than 3, and liberal stands for structures that do not forbid certain finite structures of small size. This result is built on a new approach and concerns a broad class of structures including reducts of homogeneous digraphs for which the CSP complexity classification has not yet been obtained.

Recommendations

• Graphs of relational structures: restricted types
• The collapse of the bounded width hierarchy
• There are no pure relational width 2 constraint satisfaction problems
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• CSP for binary conservative relational structures

Cited in

(4)

• Relational structures constructible by quantifier free definable operations
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• There are no pure relational width 2 constraint satisfaction problems
• Smooth approximations and CSPs over finitely bounded homogeneous structures

This page was built for publication: On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145694)