{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:37Z","timestamp":1725662857531},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108436"},{"type":"electronic","value":"9783540387459"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10843-2_33","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:28:11Z","timestamp":1330190891000},"page":"408-416","source":"Crossref","is-referenced-by-count":4,"title":["On the (generalized) post correspondence problem with lists of length 2"],"prefix":"10.1007","author":[{"given":"A.","family":"Ehrenfeucht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Rozenberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Book, R.V. and Brandenburg, F.J., Equality sets and complexity classes, SIAM J. of Comp., to appear.","DOI":"10.1137\/0209057"},{"key":"33_CR2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/322123.322136","volume":"26","author":"K. Culik II","year":"1979","unstructured":"Culik, K., II, A purely homomorphic characterization of recursively enumerable sets, J. of the ACM26, 345\u2013450, 1979.","journal-title":"J. of the ACM"},{"key":"33_CR3","unstructured":"Claus, V., Die Grenze zwischen Entscheidbarkeit und Nichtentscheidbarkeit, Fernstudienkurs f\u00fcr die Fernuniversit\u00e4t Hagen, Open University Hagen, 1979."},{"key":"33_CR4","unstructured":"Culik, K., II and Karhumaki, J., On the equality sets for homomorphisms on free monoids with two generators, University of Waterloo, Techn.Rep. CS-79-17, 1979."},{"key":"33_CR5","unstructured":"Engelfriet, J. and Rozenberg, G., Fixed point languages, equality languages and representations of recursively enumerable languages, J. of the ACM, to appear."},{"key":"33_CR6","unstructured":"Ehrenfeucht, A., Karhumaki, J. and Rozenberg, G., The (Generalized) Post Correspondence Problem with lists of length 2 is decidable, manuscript."},{"key":"33_CR7","unstructured":"Harrison, M.A., Introduction to formal language theory, Addison-Wesley Publ., 1978."},{"key":"33_CR8","unstructured":"Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publ., 1979."},{"key":"33_CR9","unstructured":"Karhumaki, J. and Simon, I., A note on elementary homomorphisms and the regularity of equality sets, Bulletin of the EATCS 9, 1979."},{"key":"33_CR10","first-page":"2940","volume":"257","author":"Y. Lecerf","year":"1963","unstructured":"Lecerf, Y., Recursive insolubilit\u00e9 de l'equation generale de diagonalisation de deux momomorphisms de monoides libres \u03c9x = \u03c9x, Comptes rendus 257, 2940\u20132943, 1963.","journal-title":"Comptes rendus"},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"E. L. Post","year":"1946","unstructured":"Post, E.L., A variant of a recursively unsolvable problem, Bull. of the Am. Math. Soc., 52, 264\u2013268, 1946.","journal-title":"Bull. of the Am. Math. Soc."},{"key":"33_CR12","unstructured":"Salomaa, A., Formal languages, Academic Press, 1973."},{"key":"33_CR13","first-page":"127","volume":"4","author":"A. Salomaa","year":"1978","unstructured":"Salomaa, A., Equality sets for homomorphisms on free monoids, Acta Cybernetica-4, 127\u2013139, 1978.","journal-title":"Acta Cybernetica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10843-2_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:39:16Z","timestamp":1619555956000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10843-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108436","9783540387459"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-10843-2_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}