On the containment and equivalence problems for two-way transducers

DOI10.1016/j.tcs.2011.12.034zbMath1238.68077OpenAlexW2084335565MaRDI QIDQ418777

Oscar H. Ibarra, Hsu-Chun Yen

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.034

zbMATH Keywords

equivalence problemcontainment problemtwo-way transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On the Density of Context-Free and Counter Languages ⋮ On the complexity of decision problems for counter machines with applications to coding theory ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the Density of Context-Free and Counter Languages ⋮ Further remarks on DNA overlap assembly ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Reversible pushdown transducers ⋮ Transducing reversibly with finite state machines

Cites Work

• Unnamed Item
• Unnamed Item
• On the universe, disjointness, and containment problems for simple machines
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The complexity of decision problems for finite-turn multicounter machines
• Expressiveness of Streaming String Transducers
• Nondeterministic Streaming String Transducers
• 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
• 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