Single-valuedness of tree transducers is decidable in polynomial time

DOI10.1016/0304-3975(92)90281-JMaRDI QIDQ685348zbMATH OpenFDO

Authors 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

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

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

Cites work

• scientific article; zbMATH DE number 4060732 (Why is no real title available?)
• scientific article; zbMATH DE number 3714978 (Why is no real title available?)
• scientific article; zbMATH DE number 17828 (Why is no real title available?)
• scientific article; zbMATH DE number 125895 (Why is no real title available?)
• scientific article; zbMATH DE number 176145 (Why is no real title available?)
• scientific article; zbMATH DE number 3594649 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 3622977 (Why is no real title available?)
• Attribute grammars and recursive program schemes. I. II
• Deciding Equivalence of Finite Tree Automata
• On the degree of ambiguity of finite automata
• On the finite degree of ambiguity of finite tree automata
• On the valuedness of finite transducers
• Sur les rélations rationnelles entre monoides libres
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Variations on the Common Subexpression Problem

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
• scientific article; zbMATH DE number 125895 (Why is no real title available?)
• 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)