Manfred Kufleitner ; Pascal Weil - On logical hierarchies within FO^2-definable languages

lmcs:1212 - Logical Methods in Computer Science, August 14, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:11)2012
On logical hierarchies within FO^2-definable languagesArticle

Authors: Manfred Kufleitner ORCID; Pascal Weil

    We consider the class of languages defined in the 2-variable fragment of the first-order logic of the linear order. Many interesting characterizations of this class are known, as well as the fact that restricting the number of quantifier alternations yields an infinite hierarchy whose levels are varieties of languages (and hence admit an algebraic characterization). Using this algebraic approach, we show that the quantifier alternation hierarchy inside FO^{2}[<] is decidable within one unit. For this purpose, we relate each level of the hierarchy with decidable varieties of languages, which can be defined in terms of iterated deterministic and co-deterministic products. A crucial notion in this process is that of condensed rankers, a refinement of the rankers of Weis and Immerman and the turtle languages of Schwentick, Thérien and Vollmer.


    Volume: Volume 8, Issue 3
    Published on: August 14, 2012
    Imported on: February 12, 2011
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,F.4.3,F.4.1

    8 Documents citing this article

    Consultation statistics

    This page has been seen 1473 times.
    This article's PDF has been downloaded 661 times.