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], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01160458
Contributor : Luc Segoufin <>
Submitted on : Friday, June 5, 2015 - 2:38:53 PM
Last modification on : Thursday, July 4, 2019 - 3:56:24 PM
Long-term archiving on : Tuesday, September 15, 2015 - 11:35:40 AM

File

simon.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01160458, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

516

Files downloads

298