On the steps of Emil Post: from normal systems to the correspondence decision problem

DOI10.14232/ACTACYB.284625MaRDI QIDQ5855841zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Tero Harju

Publication date 20 March 2021

Published in Acta Cybernetica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.14232/actacyb.284625

zbMATH Keywords

undecidabilityPost correspondence problemnormal systemsassertion problem

Mathematics Subject Classification ID

History of mathematics in the 20th century (01A60) History of mathematical logic and foundations (03-03) Thue and Post systems, etc. (03D03) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Publication:4729772
• Remarks on generalized Post Correspondence Problem
• Binary (generalized) Post Correspondence Problem
• New proof for the undecidability of the circular PCP
• On some variants of Post's correspondence problem

Cited in

(3)

• scientific article; zbMATH DE number 1860694 (Why is no real title available?)
• Verification of PCP-related computational reductions in Coq
• scientific article; zbMATH DE number 4156422 (Why is no real title available?)

This page was built for publication: On the steps of Emil Post: from normal systems to the correspondence decision problem

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