The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
- 1 April 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (2) , 221-230
- https://doi.org/10.1137/0216018
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- On the finite-valuedness problem for sequential machinesTheoretical Computer Science, 1988
- A proof of Ehrenfeucht's ConjectureTheoretical Computer Science, 1985
- A note on finite-valued and finitely ambiguous transducersTheory of Computing Systems, 1983
- Systems of equations over a free monoid and Ehrenfeucht's conjectureDiscrete Mathematics, 1983
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is DecidableSIAM Journal on Computing, 1982
- Test sets and checking words for homomorphism equivalenceJournal of Computer and System Sciences, 1980
- Some decidability results about regular and pushdown translationsInformation Processing Letters, 1979
- The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and ApplicationsSIAM Journal on Computing, 1978
- Single-valued a-transducersJournal of Computer and System Sciences, 1977
- Two-way sequential transductions and stack automataInformation and Control, 1971