A note on finite-valued and finitely ambiguous transducers

1. Blattner, M., and Head, T. The decidability of equivalence for deterministic finite transducers,Journal of Computer and System Sciences 19 (1979), 45–49.

   Google Scholar 

2. Blattner, M., and Head, T. Single-valueda-transducers,Journal of Computer and System Sciences 15 (1977), 310–327.

   Google Scholar 

3. Chan, T. and Ibarra, O. On the finite-valuedness problem for sequential machines, to appear inTheoretical Computer Science.

4. Friedman, E., and Greibach, S. A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors,SIAM Journal on Computing 11, 166–183 (1982).

   Google Scholar 

5. Garey, M., and Johnson, D. “Computers and Intractability: A Guide to the Theory of NP-Completeness,” H. Freeman, San Francisco, 1978.

   Google Scholar 

6. Griffiths, T. The unsolvability of the equivalence problem for ε-free nondeterministic generalized machines,Journal of the Association for Computing Machinery, 15, 409–413 (1968).

   Google Scholar 

7. Gurari, E. Transducers with decidable equivalence problem, TR-CS-79–4, University of Wiscon-sin-Milwaukee (1979). Revised, TR-CS-81-182 SUNY, at Buffalo (1981).

8. Gurari, E. The equivalence problem for deterministic two-way sequential transducers is decidable,Proceedings of the 21st Symposium on Foundations of Computer Science (1980), 83–85.

9. Gurari, E., and Ibarra, O. The complexity of decision problems for finite-turn multicounter machines,Journal of Computer and System Sciences 22 (1981), 220–229.

   Google Scholar 

10. Hopcroft, J., and Ullman, J. “Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, Reading, MA, 1979.

    Google Scholar 

11. Ibarra, O. The unsolvability of the equivalence problem for ε-free NGSM's with unary input (output) alphabet and applications,SIAM Journal on Computing 4 (1978), 524–532.

    Google Scholar 

12. Stearns, R., and Hunt III, H. On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata,Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (1981), 74–81.

Download references