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) sentences. 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) sentences if and only if its syntactic monoid is J-trivial.
Year
DOI
Venue
2012
10.2168/LMCS-8(3:26)2012
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
DocType
Volume
First-order logic on trees,algebra
Journal
8
Issue
ISSN
Citations 
3
1860-5974
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Mikolaj Bojanczyk135235.99
Luc Segoufin21453153.14
Howard Straubing352860.92