Mikolaj Bojanczyk ; Luc Segoufin - Tree Languages Defined in First-Order Logic with One Quantifier Alternation

lmcs:699 - Logical Methods in Computer Science, October 20, 2010, Volume 6, Issue 4 - https://doi.org/10.2168/LMCS-6(4:1)2010
Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Authors: Mikolaj Bojanczyk ; Luc Segoufin

    We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the descendant relation alone or together with the lexicographical order relation on nodes. We provide an effective characterization of tree and forest languages definable in \Delta_2 . This characterization is in terms of algebraic equations. Over words, the class of word languages definable in \Delta_2 forms a robust class, which was given an effective algebraic characterization by Pin and Weil.


    Volume: Volume 6, Issue 4
    Published on: October 20, 2010
    Accepted on: June 25, 2015
    Submitted on: September 17, 2010
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science,cs.LO

    Linked data

    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icalp.2021.127
    • 10.4230/lipics.icalp.2021.127
    A Complexity Approach to Tree Algebras: the Bounded Case
    Colcombet, Thomas ; Jaquard, Arthur ;

    3 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 379 times.
    This article's PDF has been downloaded 275 times.