A note on Post's correspondence problem

DOI10.1016/0020-0190(81)90020-XzbMath0485.03018OpenAlexW1970280218MaRDI QIDQ1164045

Jean-Jacques Pansiot

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90020-x

zbMATH Keywords

undecidability5-rule semi-Thue systemMatiyasevich's 3-rule Thue system with undecidable word problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Thue and Post systems, etc. (03D03)

Related Items

When is a pair of matrices mortal?, Successful visual human-computer interaction is undecidable, Flatwords and Post Correspondence Problem, Representations of language families by homomorphic equality operations and generalized equality sets, Unsolvable algorithmic problems for semigroups, groups and rings, An undecidable problem for countable markov chains, Some undecidable termination problems for semi-Thue systems, Word problem for deterministic and reversible semi-Thue systems, Frontier between decidability and undecidability: A survey, On some variants of Post's correspondence problem

Cites Work

• Unnamed Item
• Unnamed Item