Paper: Piecewise Testable Tree Languages (at LICS 2008)

Authors: 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}
  }