Skip to Main content Skip to Navigation
New interface
Journal articles

Piecewise testable tree languages

Mikołaj Bojańczyk 1 Luc Segoufin 2 Howard Straubing 3 
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
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 : Friday, November 18, 2022 - 9:26:13 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, 2012, 8 (3), pp.29. ⟨hal-01160458⟩



Record views


Files downloads