Paper Info
Title
Piecewise Testable Tree Languages
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.
Year
DOI
Venue
2012
10.1109/LICS.2008.46
Logical Methods in Computer Science
Keywords
DocType
Volume
syntactic monoid,string language,boolean combination,piecewise testable tree languages,tree extension,simon theorem,tree language,decidable characterization,computational linguistics,finite element methods,algebraic logic,formal languages,polynomials,automata,decidability,computer science,logic,boolean functions,algebra
Journal
8
Issue
ISSN
Citations 
3
Logical Methods in Computer Science, Volume 8, Issue 3 (September 29, 2012) lmcs:1216
17
PageRank 
References 
Authors
0.87
6
3
Name
Order
Citations
PageRank
Mikolaj Bojanczyk135235.99
Luc Segoufin21453153.14
Howard Straubing352860.92