 |
 |
 |
Place, Thomas and Segoufin, Luc - A decidable characterization of locally testable tree languages
lmcs:1210 - Logical Methods in Computer Science, November 22, 2011, Volume 7, Issue 4A decidable characterization of locally testable tree languages
Authors: Place, Thomas and Segoufin, Luc
A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree. In this paper we show that it is decidable whether a regular tree language is locally testable. The decidability is shown for ranked trees and for unranked unordered trees.
Source : oai:arXiv.org:1109.5851
DOI : 10.2168/LMCS-7(4:3)2011
Volume: Volume 7, Issue 4
Published on: November 22, 2011
Submitted on: November 24, 2009
Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3
Consultation statistics
This page has been seen 144 times.
This article's PDF has been downloaded 251 times.