A decidable characterization of locally testable tree languages

DOI10.2168/LMCS-7(4:3)2011zbMATH Open1237.68119OpenAlexW1967613919MaRDI QIDQ3224693FDOQ3224693

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

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

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)

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)