{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:43Z","timestamp":1725663103469},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540185352"},{"type":"electronic","value":"9783540480082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3540185356_28","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:36:42Z","timestamp":1330198602000},"page":"26-38","source":"Crossref","is-referenced-by-count":5,"title":["The equivalence of mappings on languages"],"prefix":"10.1007","author":[{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/S0019-9958(82)80028-4","volume":"52","author":"J. Albert","year":"1982","unstructured":"Albert, J., Culik II, K. and Karhum\u00e4ki, J., Test sets for context-free languages and algebraic systems of equations, Inform. Control 52 (1982) 172\u2013186.","journal-title":"Inform. Control"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0304-3975(85)90066-0","volume":"41","author":"M. Albert","year":"1985","unstructured":"Albert, M. and Lawrence, J., A proof of Ehrenfeucht's conjecture, Theoret. Comput. Sci. 41 (1985) 121\u2013123.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(86)90171-4","volume":"43","author":"M. Albert","year":"1986","unstructured":"Albert, M. and Lawrence, J., Test sets for finite substitutions, Theoret. Comput. Sci. 43 (1986) 117\u2013122.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Berstel, J., Transductions and Context-Free Languages (Teubner Stuttgard, 1979).","DOI":"10.1007\/978-3-663-09367-1"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/S0022-0000(73)80045-5","volume":"7","author":"M. Bird","year":"1973","unstructured":"Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. System Sci. 7 (1973) 218\u2013236.","journal-title":"J. Comput. System Sci."},{"key":"2_CR6","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-valued a-transducers, J. Comput. System Sci. 15 (1977) 310\u2013327.","journal-title":"J. Comput. System Sci."},{"key":"2_CR7","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, J. Comput. System Sci. 19 (1979) 45\u201349.","journal-title":"J. Comput. System Sci."},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/S0019-9958(77)90512-5","volume":"35","author":"K. Culik II","year":"1977","unstructured":"Culik II, K. and Fris, I., The decidability of the equivalence problem for DOL-systems, Inform. Control 35 (1977) 20\u201339.","journal-title":"Inform. Control"},{"key":"2_CR9","volume-title":"The Book of L","author":"K. Culik II","year":"1986","unstructured":"Culik II, K. and Karhum\u00e4ki, J., A new proof for the DOL sequence equivalence problem and its implications, in A. Salomaa and G. Rozenberg (eds): The Book of L (Springer, Berlin, 1986)."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Culik II, K. and Karhum\u00e4ki, J., The equivalence problem for single-valued two-way transducers (on NPDTOL languages) is decidable, SIAM J. of Comput. (to appear).","DOI":"10.1137\/0216018"},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(86)90134-9","volume":"47","author":"K. Culik II","year":"1986","unstructured":"Culik II, K. and Karhum\u00e4ki, J., The equivalence of finite valued transducers (on HDTOL languages) is decidable, Proceedings of MFCS 86, Theoret. Comput. Sci. 47 (1986) 71\u201384.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0022-0000(78)90002-8","volume":"17","author":"K. Culik II","year":"1978","unstructured":"Culik II, K. and Salomaa, A., On the decidability of morphic equivalence for languages, J. Comput. System Sci. 17 (1978) 163\u2013175.","journal-title":"J. Comput. System Sci."},{"key":"2_CR13","volume-title":"Automata, Languages and Machines, vol. A","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S., Automata, Languages and Machines, vol. A (Academic Press, New York, 1974)."},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/S0019-9958(71)90483-9","volume":"18","author":"R. Ehrich","year":"1971","unstructured":"Ehrich, R. and Yau, S., Two-way sequential transductions and stack automata, Inform. Control 18 (1971) 404\u2013446.","journal-title":"Inform. Control"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(68)80006-6","volume":"2","author":"P. Fischer","year":"1968","unstructured":"Fischer, P. and Rosenberg, A., Multitape one-way nonwriting automata, J. Comput. System Sci. 2 (1968) 88\u2013101.","journal-title":"J. Comput. System Sci."},{"key":"2_CR16","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 \u025b-free nondeterministic generalized machines, J. Assoc. Comput. Mach. 15 (1968) 409\u2013413.","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/0211035","volume":"11","author":"E. Gurari","year":"1982","unstructured":"Gurari, E., The equivalence problem for deterministic two-way transducers is decidable, SIAM J. Comput. 11 (1982) 448\u2013452.","journal-title":"SIAM J. Comput."},{"key":"2_CR18","first-page":"229","volume":"17","author":"E. Gurari","year":"1985","unstructured":"Gurari, E., Two-way counter machines and finite-state transducers, J. Comput. Math. 17 (1985) 229\u2013236.","journal-title":"J. Comput. Math."},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"E. Gurari","year":"1983","unstructured":"Gurari, E. and Ibarra, O., A note on finite-valued and finitely ambiguous transducers, Math. Systems Theory 16 (1983) 61\u201366.","journal-title":"Math. Systems Theory"},{"key":"2_CR20","volume-title":"Introduction to Formal Languages","author":"M. Harrison","year":"1978","unstructured":"Harrison, M., Introduction to Formal Languages (Addison-Wesley, Reading, MA, 1978)."},{"key":"2_CR21","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 \u025b-free NGSM's with unary input (output) alphabet and applications, SIAM J. Comput. 4 (1978) 524\u2013532.","journal-title":"SIAM J. Comput."},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0304-3975(82)90061-5","volume":"19","author":"O. Ibarra","year":"1982","unstructured":"Ibarra, O., 2DST mappings on languages and related problems, Theoret. Comput. Sci. 19 (1982) 219\u2013227.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"Jones, N. and Laaser, W., Complete problems for deterministic polynomial time, Theoret. Comput. Sci. 3 (1977) 105\u2013117.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR24","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0304-3975(84)90004-5","volume":"29","author":"J. Karhum\u00e4ki","year":"1984","unstructured":"Karhum\u00e4ki, J., The Ehrenfeucht Conjecture: A compactness claim for finitely generated free monoids, Theoret. Comput. Sci. 29 (1984) 285\u2013308.","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1051\/ita\/1985190302031","volume":"19","author":"J. Karhum\u00e4ki","year":"1985","unstructured":"Karhum\u00e4ki, J. and Kleijn, H.C.M., 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."},{"key":"2_CR26","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90045-8","volume":"5","author":"J. Karhum\u00e4ki","year":"1983","unstructured":"Karhum\u00e4ki, J. and Linna, M., A note on morphic characterization of languages, Discrete Appl. Math. 5 (1983) 243\u2013246.","journal-title":"Discrete Appl. Math."},{"key":"2_CR27","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0022-0000(86)90032-2","volume":"32","author":"J. Karhum\u00e4ki","year":"1986","unstructured":"Karhum\u00e4ki, J. and Maon, Y., A simple undecidable problem: Existential egreement of inverses of two morphisms on a regular language, J. Comput. System Sci. 32 (1986) 315\u2013322.","journal-title":"J. Comput. System Sci."},{"key":"2_CR28","first-page":"34","volume":"28","author":"J. Lawrence","year":"1986","unstructured":"Lawrence, J., The non-existence of finite test sets for set-equivalence of finite substitutions, EATCS Bull. 28 (1986) 34\u201337.","journal-title":"EATCS Bull."},{"key":"2_CR29","unstructured":"Lisovik, L.P., Finite coverings of regular events by strong sets, Doklady of Ukrainian Academy of Sciences (1979) N 5."},{"key":"2_CR30","unstructured":"Lisovik, L.P., On solvable problems for Converters with Finite Rotary Counters, Kibernetika (1985) N 3 1\u20138."},{"key":"2_CR31","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S., The problem of solvability of equations in a free semigroup, Mat. Sb. 103 (1977) 147\u2013236.","journal-title":"Mat. Sb."},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Maon, Y., On the equivalence of some transductions involving letter to letter morphisms on regular languages, manuscript (1985).","DOI":"10.1007\/BF00288471"},{"key":"2_CR33","unstructured":"Maon, Y., Decision problems concerning equivalence of transductions on languages, Ph.D. Thesis, Tel Aviv University (1985)."},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Maon, Y., On the equivalence problem of composition of morphisms and inverse morphisms on context-free languages, manuscript (1984).","DOI":"10.1016\/0304-3975(85)90063-5"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Moore, E.F., Gedanken-experiments on sequential machines, in: Automata Studies (Princeton University Press, 1956).","DOI":"10.1515\/9781400882618-006"},{"key":"2_CR36","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF00263589","volume":"3","author":"M. Nielsen","year":"1974","unstructured":"Nielsen, M., Rozenberg, G., Salomaa, A. and Skyum, S., Nonterminals, homorphisms and codings in different variations of OL systems. I and II, Acta Inform. 3 (1974) 357\u2013364 and 4 (1974) 87\u2013106.","journal-title":"Acta Inform."},{"key":"2_CR37","volume-title":"The Mathematical Theory of L Systems","author":"G. Rozenberg","year":"1980","unstructured":"Rozenberg, G. and Salomaa, A., The Mathematical Theory of L Systems (Academic Press, New York 1980)."},{"key":"2_CR38","first-page":"209","volume-title":"Lecture Notes in Computer Science 33","author":"M.P. Sch\u00fctzenberger","year":"1975","unstructured":"Sch\u00fctzenberger, M.P., Sur les relations rationelles in: Lecture Notes in Computer Science 33 (Springer, Berlin 1975) 209\u2013213."},{"key":"2_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A. Salomaa","year":"1978","unstructured":"Salomaa, A. and Soittola, M., Automata-Theoretic Aspects of Formal Power Series (Springer, Berlin 1978)."}],"container-title":["Lecture Notes in Computer Science","Trends, Techniques, and Problems in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3540185356_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:15:05Z","timestamp":1605644105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3540185356_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540185352","9783540480082"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3540185356_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}