On the decidability of the valuedness problem for two-way finite transducers

DOI10.1016/j.ic.2022.104870zbMath1504.68120OpenAlexW4210828076MaRDI QIDQ2672252

Di-De Yen, Hsu-Chun Yen

Publication date: 8 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104870

zbMATH Keywords

finite transducercrossing sequencevaluedness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Algorithmic aspects of decomposition and equivalence of finite-valued transducers
• The decidability of equivalence for deterministic finite transducers
• 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
• On the lengths of values in a finite transducer
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Lexicographic decomposition of \(k\)-valued transducers
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• On the Decidability of the Equivalence for k-Valued Transducers
• On the Decidability of Bounded Valuedness for Transducers
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• MSO definable string transductions and two-way finite-state transducers
• Uniformisation of Two-Way Transducers
• From Two-Way to One-Way Finite State Transducers
• One-way Definability of Sweeping Transducer.
• On Relations Defined by Generalized Finite Automata
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the decidability of the valuedness problem for two-way finite transducers