{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T07:40:35Z","timestamp":1661499635605},"reference-count":7,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p> In this paper, we define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application, we show that the original proof of undecidability of the freeness problem for [Formula: see text] integer matrix semigroups works for the symmetric PCP, but not for the PCP in general. <\/jats:p>","DOI":"10.1142\/s0218196722500540","type":"journal-article","created":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T07:35:55Z","timestamp":1655364955000},"page":"1261-1274","source":"Crossref","is-referenced-by-count":0,"title":["The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups"],"prefix":"10.1142","volume":"32","author":[{"given":"Jean-Camille","family":"Birget","sequence":"first","affiliation":[{"name":"Rutgers University, Camden (Emeritus), Camden, New Jersey 08102, USA"}]},{"given":"Alexey L.","family":"Talambutsa","sequence":"additional","affiliation":[{"name":"Steklov Mathematical Institute of the Russian Academy of Sciences, Gubkina Str. 8 119991, Moscow, Russia"}]}],"member":"219","published-online":{"date-parts":[[2022,7,30]]},"reference":[{"key":"S0218196722500540BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196799000199"},{"key":"S0218196722500540BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71115-7"},{"key":"S0218196722500540BIB003","volume-title":"Computability, Complexity, and Languages","author":"Davis M.","year":"1983"},{"key":"S0218196722500540BIB005","volume-title":"The Language of Machines: An Introduction to Computability and Formal Languages","author":"Floyd R. W.","year":"1994"},{"key":"S0218196722500540BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000146"},{"key":"S0218196722500540BIB008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"S0218196722500540BIB009","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196722500540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T07:08:06Z","timestamp":1661497686000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196722500540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,30]]},"references-count":7,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1142\/S0218196722500540"],"URL":"https:\/\/doi.org\/10.1142\/s0218196722500540","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,30]]}}}