Decision Problems of Tree Transducers with Origin

DOI10.1007/978-3-662-47666-6_17zbMath1395.68167OpenAlexW1485480035MaRDI QIDQ3449477

Pierre-Alain Reynier, Emmanuel Filiot, Sebastian Maneth, Jean-Marc Talbot

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/21938855/Filiot_et_al_2015_Decision_Problems_of_Tree.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Decision problems of tree transducers with origin ⋮ Look-ahead removal for total deterministic top-down tree transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• The equivalence problem for deterministic MSO tree transducers is decidable
• Tree transducers, L systems, and two-way machines
• Decidability of the finiteness of ranges of tree transductions
• On the equivalence problem for letter-to-letter top-down tree transducers
• Origin tracking
• Typechecking for XML transformers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Transducer-based analysis of cryptographic protocols
• Generalized sequential machine maps
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Tree Transformations and Dependencies
• The Power of Extended Top-Down Tree Transducers
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Composition of functions with accumulating parameters
• Transducers with Origin Information
• Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Mappings and grammars on trees