Single-valuedness of tree transducers is decidable in polynomial time

DOI10.1016/0304-3975(92)90281-JzbMath0783.68086MaRDI QIDQ685348

Helmut Seidl

Publication date: 17 October 1993

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

zbMATH Keywords

treestree transducer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (8)

Finite tree automata with cost functions ⋮ EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS ⋮ Equivalence of finite-valued tree transducers is decidable ⋮ Queries on XML streams with bounded delay and concurrency ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Bounded Delay and Concurrency for Earliest Query Answering ⋮ On the equivalence problem for letter-to-letter top-down tree transducers ⋮ Automatic structures of bounded degree revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On the valuedness of finite transducers
• Attribute grammars and recursive program schemes. I. II
• On the degree of ambiguity of finite automata
• Sur les rélations rationnelles entre monoides libres
• On the finite degree of ambiguity of finite tree automata
• Deciding Equivalence of Finite Tree Automata
• Variations on the Common Subexpression Problem

This page was built for publication: Single-valuedness of tree transducers is decidable in polynomial time