Bojańczyk, Mikołaj and Segoufin, Luc and Straubing, Howard - Piecewise testable tree languages

lmcs:1216 - Logical Methods in Computer Science, September 29, 2012, Volume 8, Issue 3
Piecewise testable tree languages

Authors: Bojańczyk, Mikołaj and Segoufin, Luc and Straubing, Howard

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.


Source : oai:arXiv.org:1208.5129
DOI : 10.2168/LMCS-8(3:26)2012
Volume: Volume 8, Issue 3
Published on: September 29, 2012
Submitted on: November 15, 2011
Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3,F.4.1


Share

Consultation statistics

This page has been seen 69 times.
This article's PDF has been downloaded 15 times.