On the Decidability of the Equivalence for a Certain Class of Transducers

DOI10.1007/978-3-642-02737-6_39MaRDI QIDQ3637249zbMATH OpenOpenAlexFDO

Authors Rodrigo de Souza

Publication date 7 July 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02737-6_39

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the Decidability of the Equivalence for k-Valued Transducers
• On the Decidability of Bounded Valuedness for Transducers
• Decidability of equivalence for a class of non-deterministic tree transducers
• Equivalence problems for transducers with a bounded number of states
• Equivalence of deterministic top-down tree-to-string transducers is decidable

Cites work

• A construction on finite automata that has remained hidden
• Decomposing a k-valued transducer into k unambiguous ones
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• Multitape one-way nonwriting automata
• On the Decidability of Bounded Valuedness for Transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the decomposition of \(k\)-valued rational relations
• On the lengths of values in a finite transducer
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• The growth ratio of synchronous rational relations is unique
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications

Cited in

(7)

• A description of \(\operatorname{Aut} (d V_n)\) and \(\operatorname{Out} (d V_n)\) using transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the Decidability of Bounded Valuedness for Transducers
• scientific article; zbMATH DE number 4045192 (Why is no real title available?)
• On equivalence and uniformisation problems for finite transducers
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• scientific article; zbMATH DE number 7561353 (Why is no real title available?)

This page was built for publication: On the Decidability of the Equivalence for a Certain Class of Transducers

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