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 4
A 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


Export

Share

Consultation statistics

This page has been seen 65 times.
This article's PDF has been downloaded 92 times.