Some new results on Post correspondence problem and its modifications
The authors of the paper study the Post Correspondence Problem (PCP) and its modification. The PCP offers many interesting questions related to undecidability that the authors consider. More specifically the authors consider the proof of Halava, Hirvensalo and De Wolf that a marked PCP is decidable for all alphabet sizes. Then, the authors study the generalized PCP and consider briefly the ideas behind the proof of Halave, Harju and Hirvensalo that the marked generalized PCP is decidable regardless of the size of the domain alphabet.
- Verification of PCP-related computational reductions in Coq
- Binary equality sets are generated by two words
- scientific article; zbMATH DE number 1304321 (Why is no real title available?)
- Remarks on generalized Post Correspondence Problem
- scientific article; zbMATH DE number 1390073 (Why is no real title available?)
- On bi-infinite and conjugate post correspondence problems
- On some variants of Post's correspondence problem
This page was built for publication: Some new results on Post correspondence problem and its modifications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2729239)
