Thomas Place ; Luc Segoufin - A decidable characterization of locally testable tree languages

lmcs:1210 - Logical Methods in Computer Science, November 22, 2011, Volume 7, Issue 4 - https://doi.org/10.2168/LMCS-7(4:3)2011
A decidable characterization of locally testable tree languagesArticle

Authors: Thomas Place ; Luc Segoufin

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.

https://doi.org/10.2168/LMCS-7(4:3)2011
Source: arXiv.org:1109.5851
Volume: Volume 7, Issue 4
Secondary volumes: Selected Papers of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)
Published on: November 22, 2011
Imported on: November 24, 2009
Keywords: Computer Science - Formal Languages and Automata Theory, F.4.3
Licence: arXiv.org - Non-exclusive license to distribute

3 Documents citing this article

Share and export

Consultation statistics

This page has been seen 3049 times.
This article's PDF has been downloaded 629 times.