The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups

Autor:	Jean-Camille Birget, Alexey L. Talambutsa
Rok vydání:	2022
Předmět:	General Mathematics
Zdroj:	International Journal of Algebra and Computation. 32:1261-1274
ISSN:	1793-6500 0218-1967
DOI:	10.1142/s0218196722500540
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::87e1115b21fbfc18ef1d67271a28fb92 https://doi.org/10.1142/s0218196722500540 Zobrazit plný text záznamu