×

A decidable characterization of locally testable tree languages. (English) Zbl 1237.68119

Summary: 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.

MSC:

68Q45 Formal languages and automata
03B25 Decidability of theories and sets of sentences
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI