2026-07-22T08:35:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1360 2024-03-06T10:33:00Z ddc:004 open_access

Cardinality and counting quantifiers on omega-automatic structures Kaiser, Lukasz Rubin, Sasha Bárány, Vince $omega$-automatic presentations $omega$-semigroups $omega$-automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukasz Kaiser and Sasha Rubin and Vince Bárány 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1360 urn:nbn:de:0030-drops-13602 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1360 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode