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 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 : Wednesday, July 15, 2020 - 2:09:37 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

555

Files downloads

511