negalg.tocs-submission2.pdf (558.76 kB)
0/0

The half-levels of the FO2 alternation hierarchy

Download (558.76 kB)
journal contribution
posted on 22.02.2018 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

Published in

Theory of Computing Systems

Volume

61

Issue

2

Pages

352 - 370

Citation

FLEISCHER, L., KUFLEITNER, M. and LAUSER, A., 2017. The Half-Levels of the FO2 Alternation Hierarchy. Theory of Computing Systems, 61(2), pp. 352-370.

Publisher

© Springer

Version

AM (Accepted Manuscript)

Publisher statement

This 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/

Acceptance date

17/09/2016

Publication date

2017

Notes

This 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

ISSN

1432-4350

eISSN

1433-0490

Language

en

Exports