Rankers over Infinite Words

Details Rankers over Infinite Words Rankers over Infinite Words

2010-05-04

arxiv.org/abs/1005.0505v1

Computer Science

Formal Languages and Automata Theory

To be presented at the 14th Int. Conference on Developments in Language Theory (DLT 2010).

Scientific paper

We consider the four fragments FO2, the intersection of Sigma2 and FO2, the intersection of Pi2 and FO2, and Delta2 of first-order logic FO[<] over finite and infinite words. For all four fragments, we give characterizations in terms of rankers. In particular, we generalize the notion of a ranker to infinite words in two possible ways. Both extensions are natural in the sense that over finite words, they coincide with classical rankers and over infinite words, they both have the full expressive power of FO2. Moreover, the first extension of rankers admits a characterization of the intersection of Sigma2 and FO2 while the other leads to a characterization of the intersection of Pi2 and FO2. Both versions of rankers yield characterizations of the fragment Delta2. As a byproduct, we also obtain characterizations based on unambiguous temporal logic and unambiguous interval temporal logic.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532160