{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:29:16Z","timestamp":1725697756584},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1983,12,1]],"date-time":"1983-12-01T00:00:00Z","timestamp":439084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1983,12]]},"DOI":"10.1007\/bf01744569","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T08:56:39Z","timestamp":1118912199000},"page":"61-66","source":"Crossref","is-referenced-by-count":61,"title":["A note on finite-valued and finitely ambiguous transducers"],"prefix":"10.1007","volume":"16","author":[{"given":"Eitan M.","family":"Gurari","sequence":"first","affiliation":[]},{"given":"Oscar H.","family":"Ibarra","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01744569_CR1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0022-0000(79)90012-6","volume":"19","author":"M. Blattner","year":"1979","unstructured":"Blattner, M., and Head, T. The decidability of equivalence for deterministic finite transducers,Journal of Computer and System Sciences 19 (1979), 45\u201349.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01744569_CR2","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/S0022-0000(77)80033-0","volume":"15","author":"M. Blattner","year":"1977","unstructured":"Blattner, M., and Head, T. Single-valueda-transducers,Journal of Computer and System Sciences 15 (1977), 310\u2013327.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01744569_CR3","unstructured":"Chan, T. and Ibarra, O. On the finite-valuedness problem for sequential machines, to appear inTheoretical Computer Science."},{"key":"BF01744569_CR4","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0211013","volume":"11","author":"E. Friedman","year":"1982","unstructured":"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\u2013183 (1982).","journal-title":"SIAM Journal on Computing"},{"key":"BF01744569_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1978","unstructured":"Garey, M., and Johnson, D. \u201cComputers and Intractability: A Guide to the Theory of NP-Completeness,\u201d H. Freeman, San Francisco, 1978."},{"key":"BF01744569_CR6","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T. Griffiths","year":"1968","unstructured":"Griffiths, T. The unsolvability of the equivalence problem for \u03b5-free nondeterministic generalized machines,Journal of the Association for Computing Machinery, 15, 409\u2013413 (1968).","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01744569_CR7","unstructured":"Gurari, E. Transducers with decidable equivalence problem, TR-CS-79\u20134, University of Wiscon-sin-Milwaukee (1979). Revised, TR-CS-81-182 SUNY, at Buffalo (1981)."},{"key":"BF01744569_CR8","doi-asserted-by":"crossref","unstructured":"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\u201385.","DOI":"10.1109\/SFCS.1980.46"},{"key":"BF01744569_CR9","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(81)90028-3","volume":"22","author":"E. Gurari","year":"1981","unstructured":"Gurari, E., and Ibarra, O. The complexity of decision problems for finite-turn multicounter machines,Journal of Computer and System Sciences 22 (1981), 220\u2013229.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01744569_CR10","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., and Ullman, J. \u201cIntroduction to Automata Theory, Languages, and Computation,\u201d Addison-Wesley, Reading, MA, 1979."},{"key":"BF01744569_CR11","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1137\/0207042","volume":"4","author":"O. Ibarra","year":"1978","unstructured":"Ibarra, O. The unsolvability of the equivalence problem for \u03b5-free NGSM's with unary input (output) alphabet and applications,SIAM Journal on Computing 4 (1978), 524\u2013532.","journal-title":"SIAM Journal on Computing"},{"key":"BF01744569_CR12","doi-asserted-by":"crossref","unstructured":"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\u201381.","DOI":"10.1109\/SFCS.1981.29"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744569.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01744569\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01744569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T15:00:34Z","timestamp":1557327634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01744569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["BF01744569"],"URL":"https:\/\/doi.org\/10.1007\/bf01744569","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}