First-order Fragments with Successor over Infinite Words

Details First-order Fragments with Successor over Infinite Words First-order Fragments with Successor over Infinite Words

2010-12-30

arxiv.org/abs/1101.0115v1

Computer Science

Formal Languages and Automata Theory

Presented at STACS 2011

Scientific paper

We consider fragments of first-order logic and as models we allow finite and infinite words simultaneously. The only binary relations apart from equality are order comparison < and the successor predicate +1. We give characterizations of the fragments Sigma2 = Sigma2[<,+1] and FO2 = FO2[<,+1] in terms of algebraic and topological properties. To this end we introduce the factor topology over infinite words. It turns out that a language L is in the intersection of FO2 and Sigma2 if and only if L is the interior of an FO2 language. Symmetrically, a language is in the intersection of FO2 and Pi2 if and only if it is the topological closure of an FO2 language. The fragment Delta2, which by definition is the intersection of Sigma2 and Pi2 contains exactly the clopen languages in FO2. In particular, over infinite words Delta2 is a strict subclass of FO2. Our characterizations yield decidability of the membership problem for all these fragments over finite and infinite words; and as a corollary we also obtain decidability for infinite words. Moreover, we give a new decidable algebraic characterization of dot-depth 3/2 over finite words. Decidability of dot-depth 3/2 over finite words was first shown by Gla{\ss}er and Schmitz in STACS 2000, and decidability of the membership problem for FO2 over infinite words was shown 1998 by Wilke in his habilitation thesis whereas decidability of Sigma2 over infinite words was not known before.

Affiliated with

Also associated with

No associations

Rating

First-order Fragments with Successor over Infinite Words 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 First-order Fragments with Successor over Infinite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First-order Fragments with Successor over Infinite Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-401309