Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing - Piecewise testable tree languages

lmcs:1216 - Logical Methods in Computer Science, September 29, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:26)2012
Piecewise testable tree languagesArticle

Authors: Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing

    This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its syntactic monoid is J-trivial.

    https://doi.org/10.2168/LMCS-8(3:26)2012
    Source: arXiv.org:1208.5129
    Volume: Volume 8, Issue 3
    Published on: September 29, 2012
    Imported on: November 15, 2011
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3,F.4.1
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • SHF: AF: Small: Algebraic Methods for the Study of Logics on Trees; Funder: National Science Foundation; Code: 0915065

    10 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1131 times.
    This article's PDF has been downloaded 264 times.