On the Decidability of the Equivalence for k-Valued Transducers

DOI10.1007/978-3-540-85780-8_20MaRDI QIDQ3533016zbMATHOpenAlexFDO

Authors Rodrigo de Souza

Publication date 30 October 2008

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

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_20

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the Decidability of the Equivalence for a Certain Class of Transducers
• On the Decidability of Bounded Valuedness for Transducers
• scientific article; zbMATH DE number 4003554
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• Equivalence of finite-valued tree transducers is decidable

Cites work

• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3523154 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A construction on finite automata that has remained hidden
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• Multitape one-way nonwriting automata
• On the Decidability of Bounded Valuedness for Transducers
• On the decomposition of \(k\)-valued rational relations
• On the valuedness of finite transducers
• Single-valued a-transducers
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The complexity of decision problems for finite-turn multicounter machines
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

Cited in

(13)

• On the Decidability of the Equivalence for a Certain Class of Transducers
• On the Decidability of Bounded Valuedness for Transducers
• Lexicographic decomposition of \(k\)-valued transducers
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)
• scientific article; zbMATH DE number 4003554 (Why is no real title available?)
• On the decomposition of \(k\)-valued rational relations
• Nondeterministic Streaming String Transducers
• Balance of many-valued transductions and equivalence problems
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• Equivalence checking problem for finite state transducers over semigroups
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• On the decidability of the valuedness problem for two-way finite transducers
• Algorithmic aspects of decomposition and equivalence of finite-valued transducers

This page was built for publication: On the Decidability of the Equivalence for k-Valued Transducers

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