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

DOI10.1145/3373718.3394781zbMATH Open1498.03071arXiv2005.04145OpenAlexW3032135130MaRDI QIDQ5145694FDOQ5145694

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)

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.

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

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

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)

Cited In (4)

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

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)