The equivalence problem for deterministic two-way sequential transducers is a long time open problem which is known to be decidable for some restricted cases. Here, the problem is shown to be decidable also for the general case. In fact, the result holds even when the devices are allowed to make some finite number of nondeterministic moves.
No takes yet. Share an insight, caveat, or question.
Eitan M. Gurari (1982) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: