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

locally testableregular tree languages

Mathematics Subject Classification ID

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

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

(12)

• Automata on finite trees
• Algebra for trees
• The alphabetic complexity in homomorphic definitions of word, tree and picture languages
• Homomorphic characterization of tree languages based on comma-free encoding
• Piecewise testable tree languages
• The mu-calculus and Model Checking
• A Decidable Characterization of Locally Testable Tree Languages
• scientific article; zbMATH DE number 512866 (Why is no real title available?)
• scientific article; zbMATH DE number 1455624 (Why is no real title available?)
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• An algebraic characterization of frontier testable tree languages
• Homomorphic definitions of tree languages via comma-free tree codes

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)