{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:33Z","timestamp":1725455433944},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167839"},{"type":"electronic","value":"9783540399094"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/bfb0016250","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"264-272","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The equivalence of finite valued transducers (on HDTOL languages) is decidable"],"prefix":"10.1007","author":[{"suffix":"II","given":"Karel","family":"Culik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/S0019-9958(82)80028-4","volume":"52","author":"J. Albert","year":"1982","unstructured":"J. Albert, K. Culik II and J. Karhum\u00e4ki, Test sets for context-free languages and algebraic systems of equations, Inform. Control 52(1982) 172\u2013186.","journal-title":"Inform. Control"},{"unstructured":"M.H. Albert and J. Lawrence, A proof of Ehrenfeucht's Conjecture, Theoret. Comput. Sci. (to appear).","key":"21_CR2"},{"doi-asserted-by":"crossref","unstructured":"M.H. Albert and J. Lawrence, Test sets for finite substitutions, manuscript (1985).","key":"21_CR3","DOI":"10.1016\/0304-3975(86)90171-4"},{"key":"21_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-free Language","author":"J. Berstel","year":"1979","unstructured":"J. Berstel, Transductions and Context-free Language (Teubner, Stuttgart, 1979)."},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/S0022-0000(73)80045-5","volume":"7","author":"M. Bird","year":"1973","unstructured":"M. Bird, The equivalence problem for deterministic two-tape automata, J. Comput. System Sci. 7(1973) 218\u2013236.","journal-title":"J. Comput. System Sci."},{"key":"21_CR6","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/S0022-0000(77)80033-0","volume":"15","author":"M. Blattner","year":"1977","unstructured":"M. Blattner and T. Head, Single-valued a-transducers, J. Comput. System Sci. 15(1977) 310\u2013327.","journal-title":"J. Comput. System Sci."},{"key":"21_CR7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0022-0000(79)90012-6","volume":"19","author":"M. Blattner","year":"1979","unstructured":"M. Blattner and T. Head, The decidability of equivalence for deterministic finite transducers, J. Comput. System Sci. 19(1979) 45\u201349.","journal-title":"J. Comput. System Sci."},{"key":"21_CR8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(79)90080-2","volume":"8","author":"K. Culik II","year":"1979","unstructured":"K. Culik II, Some decidability results about regular and pushdown translations, Inform. Process. lett. 8(1979) 5\u20138.","journal-title":"Inform. Process. lett."},{"key":"21_CR9","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/S0019-9958(77)90512-5","volume":"35","author":"K. Culik II","year":"1977","unstructured":"K. Culik II and I. Fris, The decidability of the equivalence problem for DOL-systems, Inform. Control 35(1977) 20\u201339.","journal-title":"Inform. Control"},{"key":"21_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0012-365X(83)90152-8","volume":"43","author":"K. Culik II","year":"1983","unstructured":"K. Culik II and J. Karhum\u00e4ki, Systems of equations over a free monoid and Ehrenfeucht's Conjecture, Discrete Math. 43(1983) 139\u2013153.","journal-title":"Discrete Math."},{"unstructured":"K. Culik II and J. Karhum\u00e4ki, The decidability of the DTOL sequence equivalence problem and related decision problems, University of Waterloo, Department of Computer Science, Research Report CS-85-05 (1985).","key":"21_CR11"},{"unstructured":"K. Culik and J. Karhum\u00e4ki, The equivalence problem for single-valued two-way transducers is decidable, University of Waterloo, Department of Computer Science, Research Report CS-85-24 (1985).","key":"21_CR12"},{"key":"21_CR13","first-page":"30","volume":"27","author":"K. Culik II","year":"1985","unstructured":"K. Culik II and J. Karhum\u00e4ki, Decision problems solved with the help of the Ehrenfeucht Conjecture, EATCS Bull. 27 (1985) 30\u201335.","journal-title":"EATCS Bull."},{"doi-asserted-by":"crossref","unstructured":"K. Culik II and J. Karhum\u00e4ki, The equivalence of finite valued transducers (on HDTOL languages) is decidable, University of Waterloo, Department of Computer Science, Research Report CS-86-01 (1986).","key":"21_CR14","DOI":"10.1016\/0304-3975(86)90134-9"},{"key":"21_CR15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0022-0000(78)90002-8","volume":"17","author":"K. Culik II","year":"1978","unstructured":"K. Culik II and A. Salomaa, On the decidability of morphic equivalence for languages, J. Comput. System Sci. 17(1978) 163\u2013175.","journal-title":"J. Comput. System Sci."},{"key":"21_CR16","first-page":"375","volume":"15","author":"K. Culik II","year":"1980","unstructured":"K. Culik II and A. Salomaa, Test sets and cfecking words hor homomorphism equivalence, J. Comput. System Sci. 15(1980) 375\u2013395.","journal-title":"J. Comput. System Sci."},{"key":"21_CR17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(68)80006-6","volume":"2","author":"P.C. Fischer","year":"1968","unstructured":"P.C. Fischer and A.L. Rosenberg, Multi-tape one-way nonwriting automata, J. Comput. System Sci. 2(1968) 88\u2013101.","journal-title":"J. Comput. System Sci."},{"unstructured":"V.S. Guba, personal communication (1985).","key":"21_CR18"},{"key":"21_CR19","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/0211035","volume":"11","author":"E. Gurani","year":"1982","unstructured":"E. Gurani, The equivalence problem for deterministic two-way transducers is decidable, SIAM J. Comput. 11(1982) 448\u2013452.","journal-title":"SIAM J. Comput."},{"key":"21_CR20","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1080\/00207168508803465","volume":"17","author":"E. Gurani","year":"1985","unstructured":"E. Gurani, Two-way counter machines and finite-state transducers, Intern. J. Comput. Math. 17(1985) 229\u2013236.","journal-title":"Intern. J. Comput. Math."},{"key":"21_CR21","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"E. Gurani","year":"1983","unstructured":"E. Gurani and O. Ibarra, A note on finite-valued and finitely ambiguous transducers, Math. Systems Theory 16(1983) 61\u201366.","journal-title":"Math. Systems Theory"},{"key":"21_CR22","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T. Griffiths","year":"1968","unstructured":"T. Griffiths, The unsolvability of the equivalence problem for \u2208-free nondeterministic generalized machines, J. Assoc. Comput. Mach. 15(1968) 409\u2013413.","journal-title":"J. Assoc. Comput. Mach."},{"key":"21_CR23","volume-title":"Introduction to Formal Language Theory","author":"M.A. Harrison","year":"1982","unstructured":"M.A. Harrison, Introduction to Formal Language Theory (Addison-Wesley, Reading, MA, 1982)."},{"key":"21_CR24","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1137\/0207042","volume":"4","author":"O. Ibarra","year":"1978","unstructured":"O. Ibarra, The unsolvability of the equivalence problem for \u2208-free NGSM's with unary input (output) alphabet and applications, SIAM J. Comput. 4(1978) 524\u2013532.","journal-title":"SIAM J. Comput."},{"key":"21_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0304-3975(82)90061-5","volume":"19","author":"O. Ibarra","year":"1982","unstructured":"O. Ibarra, 2DST mappings on languages and related problems, Theoret. Comput. Sci. 19(1982) 219\u2013227.","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"N. Jones and W. Laaser, Complete problems for deterministic polynomial time, Theoret. Comput. Sci. 3(1977) 105\u2013117.","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR27","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0304-3975(84)90004-5","volume":"29","author":"J. Karhum\u00e4ki","year":"1984","unstructured":"J. Karhum\u00e4ki, The Ehrenfeucht Conjecture: A compactness claim for finitely generated free monoids, Theoret. Comput. Sci. 29(1984) 285\u2013308.","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR28","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1051\/ita\/1985190302031","volume":"19","author":"J. Karhum\u00e4ki","year":"1985","unstructured":"J. Karhum\u00e4ki and H.C.M. Kleijn, On the equivalence problem of compositions of morphisms and inverse morphisms, RAIRO Inform. Th\u00e9or 19(1985) 203\u2013211.","journal-title":"RAIRO Inform. Th\u00e9or"},{"unstructured":"J. Lawrence, The non-existence of finite test sets for set-equivalence of finite substitutions, manuscript (1985).","key":"21_CR29"},{"unstructured":"Y. Maon, Decision problems concerning equivalence of transductions on languages, Ph.D. Thesis, Tel Aviv University (1985).","key":"21_CR30"},{"unstructured":"R. McNaughton, A proof of the Ehrenfeucht Conjecture, Informal Memorandum (1985).","key":"21_CR31"},{"doi-asserted-by":"crossref","unstructured":"E.F. Moore, Gedanken-experiments on sequential machines, in: Automata Studies (Princeton University Press, 1956).","key":"21_CR32","DOI":"10.1515\/9781400882618-006"},{"key":"21_CR33","first-page":"68","volume":"27","author":"D. Perrin","year":"1985","unstructured":"D. Perrin, On the solution of Ehrenfeucht's Conjecture, EATCS Bull. 27(1985) 68\u201370.","journal-title":"EATCS Bull."},{"key":"21_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0022-0000(84)90026-6","volume":"22","author":"A. Restivo","year":"1984","unstructured":"A. Restivo and C. Reutenauer, On cancellation properties of languages which are supports of rational formal power series, J. Comput. System Sci. 22(1984) 153\u2013159.","journal-title":"J. Comput. System Sci."},{"key":"21_CR35","volume-title":"The Mathematical Theory of L Systems","author":"G. Rozenberg","year":"1980","unstructured":"G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems (Academic Press, New York, 1980)."},{"unstructured":"K. Ruohomen, Test sets for iterated morphisms, manuscript (1984).","key":"21_CR36"},{"key":"21_CR37","first-page":"71","volume":"27","author":"A. Salomaa","year":"1985","unstructured":"A. Salomaa, The Ehrenfeucht Conjecture: A proof for language theorists, EATCS Bull. 27(1985) 71\u201382.","journal-title":"EATCS Bull."},{"key":"21_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-07407-4_22","volume-title":"Sur les relations rationnelles","author":"M.P. Sch\u00fctzenberger","year":"1975","unstructured":"M.P. Sch\u00fctzenberger, Sur les relations rationnelles, in: Lecture Notes in Computer Science 33 (Springer, Berlin, 1975) 209\u2013213."},{"doi-asserted-by":"crossref","unstructured":"J.R. Stallings, Finiteness properties of matrix representations, manuscript (1985).","key":"21_CR39","DOI":"10.2307\/1971282"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T23:07:57Z","timestamp":1580339277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167839","9783540399094"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/bfb0016250","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}