paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width

论具有有界严格宽度的有限有界齐次二元核的一阶扩张的关系宽度
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 0/10 · 该论文属于逻辑与自动机方向，研究约束满足中关系宽度与同质二元核的分类，未涉及程序分析、静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析，与用户研究画像无明显交集。引用 0 inbox
Michał Wrona
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：研究具有有界严格宽度的有限有界齐次二元核的一阶扩张的关系宽度，推进关系宽度有界性分类。

论文研究有限有界齐次二元核的一阶扩张的关系宽度。已知有限结构的关系宽度若有界，则只能为 (1,1) 或 (2,3)。本文聚焦的二元核带有相等关系及若干反自反二元关系，且任意两个不同元素之间恰有一个二元关系成立；作者在这些核具有有界严格宽度的条件下，考察其一阶扩张的关系宽度会受到何种限制。工作属于模型论与约束满足理论的交叉，通过分析核的齐次性、有限有界性与严格宽度等结构性质，推进对关系宽度有界性的理解。

问题
确定有限有界齐次二元核的一阶扩张在核具有有界严格宽度时的关系宽度，并将其置于已知的 (1,1) 或 (2,3) 有界关系宽度分类下。
方法
采用模型论与约束满足理论中的结构方法，分析二元核及其一阶扩张的齐次性、有限有界性和严格宽度等性质。
评估
以理论证明与分类分析为主，不涉及实验评估。
原文摘要（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) ϵ R.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5512,
  title = {On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width},
  author = {Michał Wrona},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394781}
}