negalg.tocs-submission2.pdf (558.76 kB)
Download fileThe half-levels of the FO2 alternation hierarchy
journal contribution
posted on 2018-02-22, 13:37 authored by Lukas Fleischer, Manfred Kufleitner, Alexander Lauser© 2016, Springer Science+Business Media New York. The alternation hierarchy in two-variable first-order logic FO 2 [ < ] over words was shown to be decidable by Kufleitner and Weil, and independently by Krebs and Straubing. We consider a similar hierarchy, reminiscent of the half levels of the dot-depth hierarchy or the Straubing-Thérien hierarchy. The fragment Σm2 of FO 2 is defined by disallowing universal quantifiers and having at most m−1 nested negations. The Boolean closure of Σm2 yields the m th level of the FO 2 -alternation hierarchy. We give an effective characterization of Σm2, i.e., for every integer m one can decide whether a given regular language is definable in Σm2. Among other techniques, the proof relies on an extension of block products to ordered monoids.
Funding
Supported by the German Research Foundation (DFG) under grant DI 435/5-2.
History
School
- Science
Department
- Computer Science