A Decidable Characterization of Locally Testable Tree Languages

DOI10.1007/978-3-642-02930-1_24MaRDI QIDQ3638101zbMATH OpenOpenAlexFDO

Authors Thomas Place, Luc Segoufin

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.5851

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• A decidable characterization of locally testable tree languages
• Piecewise testable tree languages
• scientific article; zbMATH DE number 4108163
• An algebraic characterization of frontier testable tree languages
• STACS 2005

Cited in

(6)

• Piecewise testable tree languages
• A decidable characterization of locally testable tree languages
• scientific article; zbMATH DE number 4108163 (Why is no real title available?)
• scientific article; zbMATH DE number 512866 (Why is no real title available?)
• scientific article; zbMATH DE number 1455624 (Why is no real title available?)
• An algebraic characterization of frontier testable tree languages

This page was built for publication: A Decidable Characterization of Locally Testable Tree Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638101)