A decidable characterization of locally testable tree languages

DOI10.2168/LMCS-7(4:3)2011MaRDI QIDQ3224693zbMATH OpenOpenAlexFDO

Authors Thomas Place, Luc Segoufin

Publication date 2 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-7(4:3)2011

zbMATH Keywords

regular tree languageslocally testable

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Recommendations

• A Decidable Characterization of Locally Testable Tree Languages
• Piecewise testable tree languages
• scientific article; zbMATH DE number 4108163
• STACS 2005
• Deciding piecewise testable separability for regular tree languages

Cited in

(8)

• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• The alphabetic complexity in homomorphic definitions of word, tree and picture languages
• A Decidable Characterization of Locally Testable Tree Languages
• Automata on finite trees
• Homomorphic characterization of tree languages based on comma-free encoding
• The mu-calculus and Model Checking
• Piecewise testable tree languages
• Algebra for trees

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 Q3224693)