Cardinality and counting quantifiers on omega-automatic structures

Details Cardinality and counting quantifiers on omega-automatic structures Cardinality and counting quantifiers on omega-automatic structures

2008-02-20

arxiv.org/abs/0802.2866v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Logic in Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cardinality and counting quantifiers on omega-automatic structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cardinality and counting quantifiers on omega-automatic structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cardinality and counting quantifiers on omega-automatic structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647938