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

Publications

Has review
  • 1 zbMATH Open

11 Documents citing this article

Share and export

Consultation statistics

This page has been seen 3240 times.
This article's PDF has been downloaded 459 times.