Cardinality and counting quantifiers on omega-automatic structures

Cardinality and counting quantifiers on omega-automatic structures
复制标题

欧米伽自动结构上的基数和计数量词

DOI：
--
复制
发表时间：
2008
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
通讯作者：
V. Bárány
V. Bárány
中科院分区：
--
文献类型：
--
作者：
Lukasz Kaiser;S. Rubin;V. Bárány

文献摘要

被引文献

相似文献

我们研究可以表示为的结构 欧米伽自动机，所谓的欧米伽自动结构，并证明 以一阶逻辑在此类结构上定义的关系 由一阶量词展开`最多存在 $aleph_0$ 许多”、“存在有限多个”和“存在 $k$” modulo $m$ much' 是 omega-regular。该证明确定了某些 欧米伽半群的代数性质。 因此，可数的欧米伽正则等价关系 索引有一组 omega-regular 代表。这意味着 布卢门萨斯猜想：可数结构具有 $omega$-自动演示可以使用自动机来表示 在有限的词语上。这也补充了最近的结果 Hj"orth、Khoussainov、Montalban 和 Nies 表明存在 欧米伽自动结构，没有单射表示。
We investigate structures that can be represented by omega-automata, so called omega-automatic structures, and prove that relations defined over such structures in first-order logic expanded by the first-order quantifiers `there exist at most $aleph_0$ many', 'there exist finitely many' and 'there exist $k$ modulo $m$ many' are omega-regular. The proof identifies certain algebraic properties of omega-semigroups. As a consequence an omega-regular equivalence relation of countable index has an omega-regular set of representatives. This implies Blumensath's conjecture that a countable structure with an $omega$-automatic presentation can be represented using automata on finite words. This also complements a very recent result of Hj"orth, Khoussainov, Montalban and Nies showing that there is an omega-automatic structure which has no injective presentation.