Piecewise testable tree languages
arXiv:1208.5129 · doi:10.2168/LMCS-8(3:26)2012
Abstract
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.
References in corpus (2)
Cited by in corpus (9)
- The height of piecewise-testable languages and the complexity of the logic of subwords
- A Characterization for Decidable Separability by Piecewise Testable Languages
- Partially Ordered Automata and Piecewise Testability
- Piecewise Testable Languages and Nondeterministic Automata
- Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
- On the State Complexity of the Reverse of R- and J-trivial Regular Languages
- Wreath Products of Distributive Forest Algebras
- Deciding definability in FO2(<h,<v) on trees
- EF+EX Forest Algebras