Undecidable properties of deterministic top-down tree transducers

DOI10.1016/0304-3975(94)90241-0zbMath0823.68047OpenAlexW2003270915MaRDI QIDQ1341717

Zoltán Fülöp

Publication date: 9 January 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90241-0

zbMATH Keywords

top-down tree transducerterm rewriting system

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (7)

Linear generalized semi-monadic rewrite systems effectively preserve recognizability ⋮ Polynomial-time inverse computation for accumulative functions with multiple data traversals ⋮ Completion after Program Inversion of Injective Functions ⋮ The Power of Weighted Regularity-Preserving Multi Bottom-Up Tree Transducers ⋮ Alphabetic and synchronized tree transducers ⋮ Classes of Tree Homomorphisms with Decidable Preservation of Regularity ⋮ The HOM Problem is EXPTIME-Complete

Cites Work

• Tree transducers, L systems, and two-way machines
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Bottom-up and top-down tree transformations— a comparison
• Composition of top-down and bottom-up tree transductions
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Undecidable properties of deterministic top-down tree transducers