Cardinality and counting quantifiers on omega-automatic structures
| dc.creator | Kaiser, Lukasz | |
| dc.creator | Rubin, Sasha | |
| dc.creator | Bárány, Vince | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:22:05Z | |
| dc.date.available | 2026-07-07T09:22:05Z | |
| dc.description | 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 $ω$-automatic presentation can be represented using automata on finite words. This also complements a very recent result of Hjörth, Khoussainov, Montalban and Nies showing that there is an omega-automatic structure which has no injective presentation. | |
| dc.identifier | https://arxiv.org/abs/0802.2866 | |
| dc.identifier | http://arxiv.org/abs/0802.2866 | |
| dc.identifier | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155250 | |
| dc.subject | Logic in Computer Science | |
| dc.title | Cardinality and counting quantifiers on omega-automatic structures | |
| dc.type | text |