{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T09:59:45Z","timestamp":1773655185357,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642392115","type":"print"},{"value":"9783642392122","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_38","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:09:19Z","timestamp":1372770559000},"page":"422-433","source":"Crossref","is-referenced-by-count":7,"title":["Revisiting the Equivalence Problem for Finite Multitape Automata"],"prefix":"10.1007","author":[{"given":"James","family":"Worrell","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1090\/S0002-9939-1950-0036751-9","volume":"1","author":"S.A. Amitsur","year":"1950","unstructured":"Amitsur, S.A., Levitzki, J.: Minimal identities for algebras. Proceedings of the American Mathematical Society\u00a01, 449\u2013463 (1950)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"38_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-85363-3_23","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Mukhopadhyay, P.: Derandomizing the isolation lemma and lower bounds for circuit size. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 276\u2013289. Springer, Heidelberg (2008)"},{"key":"38_CR3","unstructured":"Bogdanov, A., Wee, H.: More on noncommutative polynomial identity testing. In: IEEE Conference on Computational Complexity, pp. 92\u201399. IEEE Computer Society (2005)"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Cohn, P.M.: Further Algebra and Applications. Springer (2003)","DOI":"10.1007\/978-1-4471-0039-3"},{"key":"38_CR5","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A. Academic Press (1974)"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Elgot, C.C., Mezei, J.E.: Two-sided finite-state transductions (abbreviated version). In: SWCT (FOCS), pp. 17\u201322. IEEE Computer Society (1963)","DOI":"10.1109\/SWCT.1963.16"},{"issue":"1","key":"38_CR7","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0211013","volume":"11","author":"E.P. Friedman","year":"1982","unstructured":"Friedman, E.P., Greibach, S.A.: A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors. SIAM J. Comput.\u00a011(1), 166\u2013183 (1982)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"38_CR8","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T.V. Griffiths","year":"1968","unstructured":"Griffiths, T.V.: The unsolvability of the equivalence problem for \u03b5-free nondeterministic generalized machines. J. ACM\u00a015(3), 409\u2013413 (1968)","journal-title":"J. ACM"},{"issue":"2","key":"38_CR9","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-3975(91)90356-7","volume":"78","author":"T. Harju","year":"1991","unstructured":"Harju, T., Karhum\u00e4ki, J.: The equivalence problem of multitape finite automata. Theor. Comput. Sci.\u00a078(2), 347\u2013355 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Kiefer, S., Murawski, A., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of equivalence and minimisation for Q-weighted automata. Logical Methods in Computer Science\u00a09 (2013)","DOI":"10.2168\/LMCS-9(1:8)2013"},{"key":"38_CR11","first-page":"1409","volume":"60","author":"A.I. Malcev","year":"1948","unstructured":"Malcev, A.I.: On the embedding of group algebras in division algebras. Dokl. Akad. Nauk\u00a060, 1409\u20131501 (1948)","journal-title":"Dokl. Akad. Nauk"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: STOC, pp. 345\u2013354 (1987)","DOI":"10.1145\/28395.383347"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2372087","volume":"71","author":"B.H. Neumann","year":"1949","unstructured":"Neumann, B.H.: On ordered groups. Amer. J. Math.\u00a071, 1\u201318 (1949)","journal-title":"Amer. J. Math."},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1090\/S0002-9947-1949-0032593-5","volume":"66","author":"B.H. Neumann","year":"1949","unstructured":"Neumann, B.H.: On ordered division rings. Trans. Amer. Math. Soc.\u00a066, 202\u2013252 (1949)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2","key":"38_CR15","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development\u00a03(2), 114\u2013125 (1959)","journal-title":"IBM Journal of Research and Development"},{"key":"38_CR16","unstructured":"Sakarovich, J.: Elements of Automata Theory. Cambridge University Press (2003)"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"Saltman, D.: Lectures on Division Algebras. American Math. Soc. (1999)","DOI":"10.1090\/cbms\/094"},{"key":"38_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M.-P. Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.-P.: On the definition of a family of automata. Inf. and Control\u00a04, 245\u2013270 (1961)","journal-title":"Inf. and Control"},{"issue":"2","key":"38_CR19","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0221017","volume":"21","author":"W. Tzeng","year":"1992","unstructured":"Tzeng, W.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM Journal on Computing\u00a021(2), 216\u2013227 (1992)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39212-2_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:21:07Z","timestamp":1557912067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}