Single-valuedness of tree transducers is decidable in polynomial time

DOI10.1016/0304-3975(92)90281-JzbMATH Open0783.68086MaRDI QIDQ685348FDOQ685348

Authors: Helmut Seidl 

Publication date: 17 October 1993

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

Recommendations

• scientific article; zbMATH DE number 125895
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• Equivalence of finite-valued tree transducers is decidable
• The equivalence problem for letter-to-letter bottom-up tree transducers is solvable
• Determinacy and subsumption for single-valued bottom-up tree transducers

zbMATH Keywords

treestree transducer

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Queries on XML streams with bounded delay and concurrency
• On the equivalence problem for letter-to-letter top-down tree transducers
• Finite tree automata with cost functions
• Earliest normal form and minimization for bottom-up tree transducers
• Determinacy and subsumption for single-valued bottom-up tree transducers
• Automatic structures of bounded degree revisited
• A survey on decidable equivalence problems for tree transducers
• Bounded Delay and Concurrency for Earliest Query Answering
• Title not available (Why is that?)
• Equivalence of finite-valued tree transducers is decidable

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

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