Cardinality and counting quantifiers on omega−automatic structures
Lukasz Kaiser‚ Sasha Rubin and Vince Barany
Abstract
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 ømega-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.
Details
| Book Title |
Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science‚ STACS 2008 |
| Editor |
S. Albers and P. Weil |
| Pages |
385−396 |
| Year |
2008 |
Links
Related pages
|
People |