paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Defining algorithmically presented structures in first order logic

在一阶逻辑中定义算法呈现的结构
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 该论文属于一阶逻辑、可计算性与模型论的基础理论研究，讨论算法呈现结构的同构型，与用户关注的静态分析、Agentic 程序、浮点程序分析、贝叶斯程序分析及 LLM 交叉方向没有直接关联。引用 1 inbox
Nadim Kasymov, Nadira Karimova, Bakh Khoussainov
逻辑与自动机
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话：提出准可公理化概念，用一阶扩展语言中的∃/∀/∃∀/∀∃句刻画两类算法呈现结构的同构型。

论文旨在用一阶逻辑描述无限结构的同构型，这一问题与模型论、描述复杂性及可计算性基础密切相关。作者引入“准可公理化”（quasi-axiomatizability）概念，用于描述结构的同构类型，并聚焦两类算法呈现的结构：正原子图可计算枚举的“正结构”，以及负原子图可计算枚举的“负结构”。方法上，作者在语言扩张中使用存在句、全称句、存在-全称句和全称-存在句，研究这两类结构的准可公理化性质。该工作属于一阶逻辑表达力、可计算性与模型论相互交叉方向的理论贡献。

问题
如何用一阶逻辑刻画算法呈现的无限结构的同构型，并研究其准可公理化与描述复杂性。
方法
引入准可公理化概念，在语言扩张中利用∃、∀、∃∀、∀∃句分析正结构与负结构。
评估
通过可计算性与模型论的理论分析，考察两类算法呈现结构在一阶扩展语言中的准可公理化性质。
原文摘要（Abstract）

We aim to describe the isomorphism types of infinite structures in the language of first-order logic. This pursuit holds importance in logic in computer science, encompassing model theory, descriptional complexity, and the foundations of computability. We introduce the notion of quasi-axiomatizability aimed at describing the isomorphism types of structures. Our focus centers on two classes of algorithmically presented structures. The first is the class of structures for which the positive atomic diagrams are computably enumerable. We call these structures positive structures. The second is the class of structures for which the negative atomic diagrams are computably enumerable. We call these structures negative structures. We study quasi-axiomatizability of structures from these classes by ∃, ∀, ∃∀, and ∀∃-sentences in expansions of languages. Our work is a contribution to the interplay between expressive power of first-order logic, computability, and model theory.

链接与引用

DOI 原文 · DBLP

BibTeX 
@inproceedings{KasymovKK24,
  title = {Defining algorithmically presented structures in first order logic},
  author = {Nadim Kasymov and Nadira Karimova and Bakh Khoussainov},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662120}
}