Undecidable properties of deterministic top-down tree transducers

DOI10.1016/0304-3975(94)90241-0MaRDI QIDQ1341717zbMATH OpenOpenAlexFDO

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

Recommendations

• Deterministic bottom-up tree transducers and ground term rewrite systems
• scientific article; zbMATH DE number 3858448
• Determinacy and subsumption for single-valued bottom-up tree transducers
• Definability results for top-down tree transducers
• scientific article; zbMATH DE number 176501

Cites work

• scientific article; zbMATH DE number 4016218 (Why is no real title available?)
• scientific article; zbMATH DE number 176501 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1995182 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Bottom-up and top-down tree transformations— a comparison
• Composition of top-down and bottom-up tree transductions
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Mappings and grammars on trees
• Tree transducers, L systems, and two-way machines

Cited in

(18)

• Definability Results for Top-Down Tree Transducers
• scientific article; zbMATH DE number 176501 (Why is no real title available?)
• scientific article; zbMATH DE number 3858448 (Why is no real title available?)
• It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
• Linear generalized semi-monadic rewrite systems effectively preserve recognizability
• The power of weighted regularity-preserving multi bottom-up tree transducers
• Undecidable properties of flat term rewrite systems
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• scientific article; zbMATH DE number 3911709 (Why is no real title available?)
• scientific article; zbMATH DE number 1390067 (Why is no real title available?)
• scientific article; zbMATH DE number 3858451 (Why is no real title available?)
• The emptiness problem is undecidable for domains of partial monadic 2- modular tree transformations
• Alphabetic and synchronized tree transducers
• scientific article; zbMATH DE number 1953124 (Why is no real title available?)
• The HOM problem is EXPTIME-complete
• Some decidability results on one-pass reductions
• Completion after program inversion of injective functions
• Polynomial-time inverse computation for accumulative functions with multiple data traversals

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

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