Piecewise testable tree languages
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 synta...
Main Authors: | Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing |
---|---|
Format: | Article |
Language: | English |
Published: |
Logical Methods in Computer Science e.V.
2012-09-01
|
Series: | Logical Methods in Computer Science |
Subjects: | |
Online Access: | https://lmcs.episciences.org/1216/pdf |
Similar Items
-
A decidable characterization of locally testable tree languages
by: Thomas Place, et al.
Published: (2011-11-01) -
A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
by: Mikołaj Bojańczyk, et al.
Published: (2019-11-01) -
The height of piecewise-testable languages and the complexity of the logic of subwords
by: Prateek Karandikar, et al.
Published: (2019-04-01) -
A Characterization for Decidable Separability by Piecewise Testable Languages
by: Wojciech Czerwiński, et al.
Published: (2017-12-01) -
Wreath Products of Forest Algebras, with Applications to Tree Logics
by: Mikolaj Bojanczyk, et al.
Published: (2012-09-01)