## Paper: Piecewise Testable Tree Languages (at LICS 2008)

**Mikołaj Bojańczyk Luc Segoufin Howard Straubing**

### Abstract

This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of $\Sigma_1$ formulas. 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$ formulas if and only if its syntactic monoid is $J$-trivial.

### BibTeX

@InProceedings{BojaczykSegoufinStr-PiecewiseTestableTr, author = {Mikołaj Bojańczyk and Luc Segoufin and Howard Straubing}, title = {Piecewise Testable Tree Languages}, booktitle = {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)}, year = {2008}, month = {June}, pages = {442--451}, location = {Pittsburgh, PA, USA}, publisher = {IEEE Computer Society Press} }