Classes of Tree Homomorphisms with Decidable Preservation of Regularity

DOI10.1007/978-3-540-78499-9_10MaRDI QIDQ5458355zbMATH OpenOpenAlexFDO

Authors Guillem Godoy, Sebastian Maneth, Sophie Tison

Publication date 11 April 2008

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78499-9_10

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On degree-preserving homeomorphisms between trees in computable topology
• scientific article; zbMATH DE number 475426
• scientific article; zbMATH DE number 223548
• Decidability of irreducible tree shifts of finite type
• Decidability of Conjugacy of Tree-Shifts of Finite Type
• Decidability and Invariant Classes for Degree Structures
• On the preservation of combinatorial types for maps on trees.
• Complexity of tree homomorphisms
• On the classification of automorphisms of trees
• Tree homomorphisms for unranked trees

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1330134 (Why is no real title available?)
• scientific article; zbMATH DE number 1523000 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Bottom-up and top-down tree transformations— a comparison
• Decidability of regularity and related properties of ground normal form languages
• Equational formulae with membership constraints
• Explicit representation of terms defined by counter examples
• Foundations of XML processing. The tree-automata approach.
• On the complexity of typechecking top-down XML transformations
• Translations on a context free grammar
• Undecidable properties of deterministic top-down tree transducers

Cited in

(5)

• The HOM problem is decidable
• The HOM problem is decidable
• scientific article; zbMATH DE number 1390088 (Why is no real title available?)
• The HOM problem is EXPTIME-complete
• Tree homomorphisms for unranked trees

This page was built for publication: Classes of Tree Homomorphisms with Decidable Preservation of Regularity

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