A note on Post's correspondence problem

DOI10.1016/0020-0190(81)90020-XMaRDI QIDQ1164045zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(10)

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

This page was built for publication: A note on Post's correspondence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1164045)