Computer Science – Logic in Computer Science
Scientific paper
2009-04-19
Mathematical Foundations of Computer Science 2009, slovaque, R\'epublique (2009)
Computer Science
Logic in Computer Science
Scientific paper
We show that each level of the quantifier alternation hierarchy within FO^2[<] -- the 2-variable fragment of the first order logic of order on words -- is a variety of languages. We then use the notion of condensed rankers, a refinement of the rankers defined by Weis and Immerman, to produce a decidable hierarchy of varieties which is interwoven with the quantifier alternation hierarchy -- and conjecturally equal to it. It follows that the latter hierarchy is decidable within one unit: given a formula alpha in FO^2[<], one can effectively compute an integer m such that alpha is equivalent to a formula with at most m+1 alternating blocks of quantifiers, but not to a formula with only m-1 blocks. This is a much more precise result than what is known about the quantifier alternation hierarchy within FO[<], where no decidability result is known beyond the very first levels.
Kufleitner Manfred
Weil Pascal
No associations
LandOfFree
On FO2 quantifier alternation over 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 On FO2 quantifier alternation over words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On FO2 quantifier alternation over words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329423