On the Decidability of the Equivalence for k-Valued Transducers

DOI10.1007/978-3-540-85780-8_20zbMath1161.68556MaRDI QIDQ3533016

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

68Q45: Formal languages and automata

Related Items

Algorithmic aspects of decomposition and equivalence of finite-valued transducers, Lexicographic decomposition of \(k\)-valued transducers, Equivalence Checking Problem for Finite State Transducers over Semigroups, Nondeterministic Streaming String Transducers, On the Decidability of the Equivalence for a Certain Class of Transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On the valuedness of finite transducers
• The complexity of decision problems for finite-turn multicounter machines
• Single-valued a-transducers
• A construction on finite automata that has remained hidden
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Multitape one-way nonwriting automata
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• On the Decidability of Bounded Valuedness for Transducers
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines