Piecewise Testable Tree Languages
Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing · Proceedings - Symposium on Logic in Computer Science · 2008
This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma1formulas. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma1formulas if and only if its syntactic monoid is J-trivial.