Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1360
URN: urn:nbn:de:0030-drops-13602
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1360/
Kaiser, Lukasz ; Rubin, Sasha ; Bárány, Vince
Cardinality and counting quantifiers on omega-automatic structures
| pdf-format: |
|
Abstract
We investigate structures that can be represented byomega-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.
BibTeX - Entry
@InProceedings{kaiser_et_al:LIPIcs:2008:1360,
author = {Lukasz Kaiser and Sasha Rubin and Vince B{\'a}r{\'a}ny},
title = {{Cardinality and counting quantifiers on omega-automatic structures}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {385--396},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-06-4},
ISSN = {1868-8969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1360},
URN = {urn:nbn:de:0030-drops-13602},
doi = {10.4230/LIPIcs.STACS.2008.1360},
annote = {Keywords: $omega$-automatic presentations, $omega$-semigroups, $omega$-automata}
}
| Keywords: | $omega$-automatic presentations, $omega$-semigroups, $omega$-automata | |
| Seminar: | 25th International Symposium on Theoretical Aspects of Computer Science | |
| Issue date: | 2008 | |
| Date of publication: | 06.02.2008 |
