10.4230/LIPICS.STACS.2008.1360
Kaiser, Lukasz
Lukasz
Kaiser
Rubin, Sasha
Sasha
Rubin
Bárány, Vince
Vince
Bárány
Cardinality and counting quantifiers on omega-automatic structures
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
$omega$-automatic presentations
$omega$-semigroups
$omega$-automata
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13602
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
34
385
396
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
191463 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 385-396