The equivalence problem for letter-to-letter bottom-up tree transducers is solvable

DOI10.1007/3-540-59293-8_193MaRDI QIDQ5096729zbMATH OpenOpenAlexFDO

Authors Yves André, Francis Bossut

Publication date 18 August 2022

Published in TAPSOFT '95: Theory and Practice of Software Development (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59293-8_193

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the equivalence problem for letter-to-letter top-down tree transducers
• scientific article; zbMATH DE number 522841
• Equivalence problems for tree transducers: a brief survey
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• scientific article; zbMATH DE number 125895
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• A survey on decidable equivalence problems for tree transducers
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• The equivalence problem for deterministic MSO tree transducers is decidable
• scientific article; zbMATH DE number 3894494

Cites work

• Alphabetic tree relations
• Bottom-up and top-down tree transformations— a comparison
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Decidability of equivalence for a class of non-deterministic tree transducers
• Generalized sequential machine maps
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3714978 (Why is no real title available?)
• scientific article; zbMATH DE number 125895 (Why is no real title available?)
• scientific article; zbMATH DE number 3622977 (Why is no real title available?)
• scientific article; zbMATH DE number 522841 (Why is no real title available?)
• Macro tree transducers
• Modular tree transducers
• On the equivalence problem for letter-to-letter top-down tree transducers
• Top-down tree transducers with regular look-ahead
• Variants of top-down tree transducers with look-ahead

Cited in

(8)

• On the equivalence problem for letter-to-letter top-down tree transducers
• scientific article; zbMATH DE number 3972225 (Why is no real title available?)
• scientific article; zbMATH DE number 125895 (Why is no real title available?)
• scientific article; zbMATH DE number 522841 (Why is no real title available?)
• Decidability of equivalence for a class of non-deterministic tree transducers
• Equivalence problems for tree transducers: a brief survey
• scientific article; zbMATH DE number 3894494 (Why is no real title available?)
• Single-valuedness of tree transducers is decidable in polynomial time

This page was built for publication: The equivalence problem for letter-to-letter bottom-up tree transducers is solvable

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