On the containment and equivalence problems for two-way transducers
From MaRDI portal
Publication:418777
DOI10.1016/j.tcs.2011.12.034zbMath1238.68077OpenAlexW2084335565MaRDI QIDQ418777
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
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