{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T16:04:19Z","timestamp":1750089859494},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540205456"},{"type":"electronic","value":"9783540400318"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-40031-8_22","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T19:03:50Z","timestamp":1283713430000},"page":"326-344","source":"Crossref","is-referenced-by-count":1,"title":["Tackling Post\u2019s Correspondence Problem"],"prefix":"10.1007","author":[{"given":"Ling","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"53","author":"E. Post","year":"1946","unstructured":"Post, E.: A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society\u00a053, 264\u2013268 (1946)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"22_CR2","volume-title":"Introduction to Automata Theory, Language, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading (1979)"},{"key":"22_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. Freeman, New York (1979)"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0304-3975(89)90080-7","volume":"21","author":"A. Ehrenfeucht","year":"1982","unstructured":"Ehrenfeucht, A., Karhumaki, J., Rozenberg, G.: The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoretical Computer Science\u00a021, 119\u2013144 (1982)","journal-title":"Theoretical Computer Science"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Halava, V., Harju, T., Hirvensalo, M.: Binary generalized Post correspondence problem. Technical Report 357, TUCS (2000)","DOI":"10.1142\/S0218196700000376"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1109\/LICS.1996.561469","volume-title":"Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science","author":"Y. Matiyasevich","year":"1996","unstructured":"Matiyasevich, Y., S\u00e9nizergues, G.: Decision problems for semi-thue systems with a few rules. In: Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, pp. 523\u2013531. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","first-page":"145","volume-title":"Computers and Games","author":"R. Lorentz","year":"2002","unstructured":"Lorentz, R.: Creating difficult instances of the Post correspondence problem. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol.\u00a02063, pp. 145\u2013159. Springer, Heidelberg (2002)"},{"key":"22_CR8","unstructured":"Schmidt, M., Stamer, H., Waldmann, J.: Busy beaver PCPs. In: Fifth international workshop on termination, WST 2001 (2001)"},{"key":"22_CR9","unstructured":"Zhao, L.: Solving and creating difficult instances of Post\u2019s correspondence problem. Master\u2019s thesis, Department of Computing Science, University of Alberta (2002)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"R. Korf","year":"1985","unstructured":"Korf, R.: Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence\u00a027, 97\u2013109 (1985)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"22_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"SSC-4","author":"P.E. Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics\u00a0SSC-4(2), 100\u2013107 (1968)","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/3-540-61291-2_68","volume-title":"Advances in Artificial Intelligence","author":"J. Culberson","year":"1996","unstructured":"Culberson, J., Schaeffer, J.: Searching with pattern databases. In: McCalla, G.I. (ed.) Canadian AI 1996. LNCS, vol.\u00a01081, pp. 402\u2013416. Springer, Heidelberg (1996)"},{"key":"22_CR13","unstructured":"Stamer, H.: PCP at home (2000-2002), http:\/\/www.informatik.uni-leipzig.de\/~pcp"},{"key":"22_CR14","unstructured":"Zhao, L.: PCP homepage (2001-2002), http:\/\/www.cs.ualberta.ca\/~zhao\/PCP"},{"key":"22_CR15","unstructured":"Rahn, M.: PCP12 has no solution (unpublished manuscript) (2002), http:\/\/www.stud.uni-karlsruhe.de\/~uyp0\/last\/last.ps"}],"container-title":["Lecture Notes in Computer Science","Computers and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-40031-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T17:16:55Z","timestamp":1559582215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-40031-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540205456","9783540400318"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-40031-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}