{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:03Z","timestamp":1725664503201},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:41Z","timestamp":1330290281000},"page":"37-48","source":"Crossref","is-referenced-by-count":3,"title":["Remarks on generalized Post Correspondence Problem"],"prefix":"10.1007","author":[{"given":"T.","family":"Harju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Krob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0166-218X(85)90063-0","volume":"12","author":"C. Choffrut","year":"1985","unstructured":"C. Choffrut and J. Karhum\u00e4ki, Test sets for morphisms with bounded delay, Discrete Appl. Math.\n12 (1985), 93\u2013101.","journal-title":"Discrete Appl. Math."},{"key":"4_CR2","first-page":"54","volume":"12","author":"V. Claus","year":"1980","unstructured":"V. Claus, Some remarks on PCP(k) and related problems, Bull. EATCS\n12 (1980), 54\u201361.","journal-title":"Bull. EATCS"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1051\/ita\/1980140403491","volume":"14","author":"K. Culik II","year":"1980","unstructured":"K. Culik II and J. Karhum\u00e4ki, On the equality sets for homomorphisms on free monoids with two generators, RAIRO Theoret. Informatics\n14 (1980), 349\u2013369.","journal-title":"RAIRO Theoret. Informatics"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0304-3975(89)90080-7","volume":"21","author":"A. Ehrenfeucht","year":"1982","unstructured":"A. Ehrenfeucht, J. Karhum\u00e4ki and G. Rozenberg, The (generalized) Post Correspondence Problem with lists consisting of two words is decidable, Theoret. Comput. Sci.\n21 (1982), 119\u2013144.","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0021-8693(83)90119-9","volume":"85","author":"A. Ehrenfeucht","year":"1983","unstructured":"A. Ehrenfeucht, J. Karhum\u00e4ki and G. Rozenberg, On binary equality languages and a solution to the test set conjecture in the binary case, J. Algebra\n85 (1983), 76\u201385.","journal-title":"J. Algebra"},{"key":"4_CR6","volume-title":"Automata, Languages, and Machines, Vol. A","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"M. Jantzen, \u201cConfluent String Rewriting\u201d, Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-61549-8"},{"key":"4_CR8","first-page":"353","volume":"55","author":"A.A. Markov","year":"1947","unstructured":"A.A. Markov, On the impossibility of certain algorithms in the theory of associative systems, Dokl. Acad. Nauk.\n55 (1947), 353\u2013356 (Russian).","journal-title":"Dokl. Acad. Nauk."},{"key":"4_CR9","first-page":"1264","volume":"173","author":"J. Matijacevic","year":"1967","unstructured":"J. Matijacevic, Simple examples of usolvable associative calculi, Dokl. Akad. Nauk\n173 (1967), 1264\u20131266 (Russian).","journal-title":"Dokl. Akad. Nauk"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(81)90020-X","volume":"12","author":"J.J. Pansiot","year":"1981","unstructured":"J.J. Pansiot, A note on Post's Correspondence Problem, Inform. proc. Lett.\n12 (1981), 233.","journal-title":"Inform. proc. Lett."},{"key":"4_CR11","unstructured":"V.A. Pavlenko, Post combinatorial problem with two pairs of words, Dokl. Akad. Nauk. Ukr. SSR (1981), 9\u201311."},{"key":"4_CR12","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"E. Post","year":"1946","unstructured":"E. Post, A variant of a recursively unsolvable problem, Bulletin of Amer. Math. Soc.\n52 (1946), 264\u2013268.","journal-title":"Bulletin of Amer. Math. Soc."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. Post","year":"1947","unstructured":"E. Post, Recursive unsolvability of a problem of Thue, J. Symb. Logic\n12 (1947), 1\u201311.","journal-title":"J. Symb. Logic"},{"key":"4_CR14","first-page":"579","volume":"21","author":"K. Ruohonen","year":"1985","unstructured":"K. Ruohonen, Reversible machines and Post's correspondence problem for biprefix morphisms, J. Inform. Process. Cybernet. EIK\n21 (1985), 579\u2013595.","journal-title":"J. Inform. Process. Cybernet. EIK"},{"key":"4_CR15","first-page":"172","volume":"52","author":"G.C. Tzeitin","year":"1958","unstructured":"G.C. Tzeitin, Associative calculus with an unsolvable equivalence problem, Tr. Mat. Inst. Akad. Nauk\n52 (1958), 172\u2013189 (Russian).","journal-title":"Tr. Mat. Inst. Akad. Nauk"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:28:10Z","timestamp":1619573290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}