论文标题
关于有限界均匀二元芯的一阶扩展的关系宽度，严格宽度
On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width
论文作者
论文摘要
有限结构的关系宽度始终是（1,1）或（2,3）。在本文中，我们研究了有限界限均质二元核的一阶扩展的关系宽度，其中二元核是具有平等性和某些反射性二进制关系的结构，因此，对于任何两个不同的元素a，b，在域中的b中，完全存在与（a，b）的二元关系。 我们的主要结果是，具有界限严格宽度的自由有限界均匀的均相二进制核心的一阶扩展具有关系宽度（2，MaxBound），其中MaxBound是最大的禁忌子结构的大小，但不少于3，而自由架的结构则是没有禁止某些小规模的有限有限的结构的结构。该结果建立在一种新方法基础上，并涉及一类广泛的结构，包括尚未获得CSP复杂性分类的均匀挖掘物的减少。
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.
