文章基本信息

标题：Cardinality and counting quantifiers on omega-automatic structures
本地全文：下载
作者：Lukasz Kaiser ; Sasha Rubin ; Vince B{\'a}r{\'a}ny 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：385-396
DOI：10.4230/LIPIcs.STACS.2008.1360
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：$omega$-automatic presentations; $omega$-semigroups; $omega$-automata