A decidable characterization of locally testable tree languagesArticle
Authors: Thomas Place ; Luc Segoufin
NULL##NULL
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.