Skip to Main content Skip to Navigation
Journal articles

Piecewise testable tree languages

Abstract : This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Σ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 Σ1 sentences if and only if its syntactic monoid is J-trivial.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Friday, June 5, 2015 - 2:38:53 PM
Last modification on : Monday, February 15, 2021 - 10:49:25 AM
Long-term archiving on: : Tuesday, September 15, 2015 - 11:35:40 AM


Files produced by the author(s)


  • HAL Id : hal-01160458, version 1


Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing. Piecewise testable tree languages. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2012, 8 (3), pp.29. ⟨hal-01160458⟩



Record views


Files downloads