The half-levels of the FO2 alternation hierarchy
journal contributionposted on 22.02.2018 by Lukas Fleischer, Manfred Kufleitner, Alexander Lauser
Any type of content formally published in an academic journal, usually following a peer-review process.
© 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.
Supported by the German Research Foundation (DFG) under grant DI 435/5-2.
- Computer Science