The half-levels of the FO2 alternation hierarchy
journal contributionposted 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.
Supported by the German Research Foundation (DFG) under grant DI 435/5-2.
- Computer Science
Published inTheory of Computing Systems
Pages352 - 370
CitationFLEISCHER, L., KUFLEITNER, M. and LAUSER, A., 2017. The Half-Levels of the FO2 Alternation Hierarchy. Theory of Computing Systems, 61(2), pp. 352-370.
- AM (Accepted Manuscript)
Publisher statementThis work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/
NotesThis is a post-peer-review, pre-copyedit version of an article published in Theory of Computing Systems. The final authenticated version is available online at:https://doi.org/10.1007/s00224-016-9712-2