The FO^2 alternation hierarchy is decidable

Details The FO^2 alternation hierarchy is decidable The FO^2 alternation hierarchy is decidable

2012-03-28

arxiv.org/abs/1203.6152v1

Computer Science

Logic in Computer Science

Scientific paper

We consider the two-variable fragment FO^2[<] of first-order logic over finite words. Numerous characterizations of this class are known. Th\'erien and Wilke have shown that it is decidable whether a given regular language is definable in FO^2[<]. From a practical point of view, as shown by Weis, FO^2[<] is interesting since its satisfiability problem is in NP. Restricting the number of quantifier alternations yields an infinite hierarchy inside the class of FO^2[<]-definable languages. We show that each level of this hierarchy is decidable. For this purpose, we relate each level of the hierarchy with a decidable variety of finite monoids. Our result implies that there are many different ways of climbing up the FO^2[<]-quantifier alternation hierarchy: deterministic and co-deterministic products, Mal'cev products with definite and reverse definite semigroups, iterated block products with J-trivial monoids, and some inductively defined omega-term identities. A combinatorial tool in the process of ascension is that of condensed rankers, a refinement of the rankers of Weis and Immerman and the turtle programs of Schwentick, Th\'erien, and Vollmer.

Affiliated with

Also associated with

No associations

Rating

The FO^2 alternation hierarchy is decidable 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 The FO^2 alternation hierarchy is decidable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The FO^2 alternation hierarchy is decidable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-271809