The Half-Levels of the FO2 Alternation Hierarchy

作者：Fleischer Lukas; Kufleitner Manfred^*; Lauser Alexander

来源：Theory of Computing Systems, 2017, 61(2): 352-370.

DOI：10.1007/s00224-016-9712-2

• Regular language
• Finite monoid
• Positive variety
• First-order logic

The alternation hierarchy in two-variable first-order logic FO2 [<] 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-Therien hierarchy. The fragment Sigma(2)(m) of FO2 is defined by disallowing universal quantifiers and having at most m - 1 nested negations. The Boolean closure of Sigma(2)(m) yields themth level of the FO2- alternation hierarchy. We give an effective characterization of Sigma(2)(m), i. e., for every integer m one can decide whether a given regular language is definable in Sigma(2)(m). Among other techniques, the proof relies on an extension of block products to ordered monoids.

• 出版日期2017-8