A decidable characterization of locally testable tree languages
arXiv:1109.5851 · doi:10.2168/LMCS-7(4:3)2011
Abstract
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.
References in corpus (1)
Cited by in corpus (5)
- On Separation by Locally Testable and Locally Threshold Testable Languages
- Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
- Forest languages defined by counting maximal paths
- Proving that a Tree Language is not First-Order Definable
- Deciding definability in FO2(<h,<v) on trees