论文标题
单词逻辑的存在片段在单词上具有固定Arity的数值谓词的二元片段
Duality for the existential fragment of first-order logic on words with numerical predicates of a fixed arity
论文作者
论文摘要
本文符合研究研究拓扑二重性方法在理论计算机科学中出现的问题中的应用。这种方法的最终目标之一是通过研究表征它们的适当拓扑对象来得出计算复杂性理论的结果。与这两个看似分开的字段相关的链接是逻辑，更确切地说是有限模型理论的子域，称为单词上的逻辑。它允许将复杂性类别描述为某些有限字母上的语言家族，可能是不规则的。关于二元性逻辑片段的二元性理论在不在普通语言范围之外的二阶逻辑上。我们工作的贡献是对这种碎片的详细研究。修复整数$ k \ geq 1 $，我们考虑了布尔代数$ \ mathcal {b}σ_1[\ Mathcal {n}^{u} {u} _K] $。它对应于逻辑的片段上的单词，这些单词是由使用最多$ k $存在量化符，字母谓词和均匀数字谓词$ l \ in \ in \ in \ in \ in \ in \ in \ {1，...，...，k \} $的句子定义的句子组合。我们对任何$ k \ geq 1 $ $ a，对其观点进行了一些特征，详细研究了该布尔代数的双重空间。在$ k = 1 $的特殊情况下，我们能够构建一个特征布尔代数$ \ mathcal {b}σ_1[\ Mathcal {n}^{u} _1 _1] $的UltraFilter方程系列。我们使用拓扑方法来证明这些方程相对于我们提到的布尔代数是合理的和完整的。
This article fits in the area of research that investigates the application of topological duality methods to problems that appear in theoretical computer science. One of the eventual goals of this approach is to derive results in computational complexity theory by studying appropriate topological objects which characterize them. The link which relates these two seemingly separated fields is logic, more precisely a subdomain of finite model theory known as logic on words. It allows for a description of complexity classes as certain families of languages, possibly non-regular, on a finite alphabet. Very few is known about the duality theory relative to fragments of first-order logic on words which lie outside of the scope of regular languages. The contribution of our work is a detailed study of such a fragment. Fixing an integer $k \geq 1$, we consider the Boolean algebra $\mathcal{B}Σ_1[\mathcal{N}^{u}_k]$. It corresponds to the fragment of logic on words consisting in Boolean combinations of sentences defined by using a block of at most $k$ existential quantifiers, letter predicates and uniform numerical predicates of arity $l \in \{1,...,k\}$. We give a detailed study of the dual space of this Boolean algebra, for any $k \geq 1$, and provide several characterizations of its points. In the particular case where $k=1$, we are able to construct a family of ultrafilter equations which characterize the Boolean algebra $\mathcal{B} Σ_1[\mathcal{N}^{u}_1]$. We use topological methods in order to prove that these equations are sound and complete with respect to the Boolean algebra we mentioned.
