On the equivalence problem for letter-to-letter top-down tree transducers

DOI10.1016/S0304-3975(97)00080-7zbMath0913.68118MaRDI QIDQ1275081

Francis Bossut, Yves André

Publication date: 12 January 1999

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

zbMATH Keywords

tree automatatop-down transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Decision Problems of Tree Transducers with Origin ⋮ Decision problems of tree transducers with origin ⋮ The equivalence problem for letter-to-letter bottom-up tree transducers is solvable ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers

Cites Work

• Single-valuedness of tree transducers is decidable in polynomial time
• Generalized sequential machine maps
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Bottom-up and top-down tree transformations— a comparison
• Decidability of equivalence for a class of non-deterministic tree transducers
• Encompassment properties and automata with constraints
• The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
• Equality and disequality constraints on direct subterms in tree automata
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item