Equivalence of finite-valued tree transducers is decidable

DOI10.1007/BF01192143zbMath0809.68087OpenAlexW1990282554MaRDI QIDQ4301635

No author found.

Publication date: 10 August 1994

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01192143

zbMATH Keywords

bottom-up finite state tree transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (6)

Branching synchronization grammars with nested tables ⋮ Queries on XML streams with bounded delay and concurrency ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Decomposing a $k$-valued transducer into $k$ unambiguous ones

Cites Work

• Unnamed Item
• Unnamed Item
• Single-valuedness of tree transducers is decidable in polynomial time
• 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 lengths of values in a finite transducer
• On the finite degree of ambiguity of finite tree automata
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence

This page was built for publication: Equivalence of finite-valued tree transducers is decidable