The Conjugate Post Correspondence Problem

11/08/2021

∙

by   Vesa Halava, et al.

∙

0

∙

share

We introduce a modification to the Post Correspondence Problem where (in the formulation using morphisms) we require the images to be conjugate words. This problem is then shown to be undecidable by reducing it to the word problem for a special type of semi-Thue systems.