Decision problems of tree transducers with origin

DOI10.1007/978-3-662-47666-6_17MaRDI QIDQ3449477zbMATH OpenOpenAlexFDO

Authors Emmanuel Filiot, Sebastian Maneth, Pierre-Alain Reynier, 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

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

Recommendations

• Decision problems of tree transducers with origin
• scientific article; zbMATH DE number 522841
• A survey on decidable equivalence problems for tree transducers
• Equivalence problems for tree transducers: a brief survey
• Equivalence of deterministic top-down tree-to-string transducers is decidable

Cites work

• Composition of functions with accumulating parameters
• Decidability of the finiteness of ranges of tree transductions
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins
• Equivalence problems for tree transducers: a brief survey
• Generalized sequential machine maps
• scientific article; zbMATH DE number 3714978 (Why is no real title available?)
• scientific article; zbMATH DE number 1200800 (Why is no real title available?)
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Mappings and grammars on trees
• On the equivalence problem for letter-to-letter top-down tree transducers
• Origin tracking
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• The equivalence problem for deterministic MSO tree transducers is decidable
• The Power of Extended Top-Down Tree Transducers
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Transducer-based analysis of cryptographic protocols
• Transducers with Origin Information
• Tree transducers, L systems, and two-way machines
• Tree transformations and dependencies
• Typechecking for XML transformers

Cited in

(5)

• Decision problems of tree transducers with origin
• Deciding origin equivalence of weakly self-nesting macro tree transducers
• Origin-equivalence of two-way word transducers is in PSPACE
• Which classes of origin graphs are generated by transducers
• Look-ahead removal for total deterministic top-down tree transducers

This page was built for publication: Decision problems of tree transducers with origin

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