Cardinality and counting quantifiers on omega−automatic structures

Conference item

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 omeg...

Expand abstract

Authors: Kaiser, L; Rubin, S; Barany, V

• Host title: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science‚ STACS 2008
• Publication date: 2008-01-01