Two-way counter machines and finite-state transducers†

DOI10.1080/00207168508803465zbMath0565.68049OpenAlexW2001899823MaRDI QIDQ3680282

Eitan M. Gurari

Publication date: 1985

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168508803465

zbMATH Keywords

decidabilityequivalence problememptiness problembounded-reversal counterdeterministic two-way finite-state automatadeterministic two-way finite-state transducers

Mathematics Subject Classification ID

Related Items

The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Prefix and equality languages of rational functions are co-context-free ⋮ On some transducer equivalence problems for families of languages ⋮ Transducing reversibly with finite state machines ⋮ A note on Parikh maps, abstract languages, and decision problems

Cites Work

• Unnamed Item
• Reversal-bounded multipushdown machines
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• Two-Way Counter Machines and Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Two-way sequential transductions and stack automata