zbMATH — the first resource for mathematics

A note on finite-valued and finitely ambiguous transducers. (English) Zbl 0502.68022

68Q45 Formal languages and automata
Full Text: DOI
[1] Blattner, M., and Head, T. The decidability of equivalence for deterministic finite transducers,Journal of Computer and System Sciences 19 (1979), 45–49. · Zbl 0416.68073
[2] Blattner, M., and Head, T. Single-valueda-transducers,Journal of Computer and System Sciences 15 (1977), 310–327. · Zbl 0367.94071
[3] Chan, T. and Ibarra, O. On the finite-valuedness problem for sequential machines, to appear inTheoretical Computer Science. · Zbl 0503.68037
[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). · Zbl 0497.68050
[5] Garey, M., and Johnson, D. ”Computers and Intractability: A Guide to the Theory of NP-Completeness,” H. Freeman, San Francisco, 1978. · Zbl 0411.68039
[6] Griffiths, T. The unsolvability of the equivalence problem for {\(\epsilon\)}-free nondeterministic generalized machines,Journal of the Association for Computing Machinery, 15, 409–413 (1968). · Zbl 0162.02302
[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. · Zbl 0458.68011
[10] Hopcroft, J., and Ullman, J. ”Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[11] Ibarra, O. The unsolvability of the equivalence problem for {\(\epsilon\)}-free NGSM’s with unary input (output) alphabet and applications,SIAM Journal on Computing 4 (1978), 524–532. · Zbl 0386.68054
[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. · Zbl 0577.68074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.