A note on Post's correspondence problem
From MaRDI portal
Publication:1164045
DOI10.1016/0020-0190(81)90020-XzbMath0485.03018MaRDI QIDQ1164045
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
undecidability; 5-rule semi-Thue system; Matiyasevich's 3-rule Thue system with undecidable word problem
Related Items
Some undecidable termination problems for semi-Thue systems, On some variants of Post's correspondence problem, Representations of language families by homomorphic equality operations and generalized equality sets, Unsolvable algorithmic problems for semigroups, groups and rings, Flatwords and Post Correspondence Problem, Frontier between decidability and undecidability: A survey, An undecidable problem for countable markov chains
Cites Work