Affiliation: | aDepartment of Mathematics and Turku Centre for Computer Science, University of Turku, FIN-20014 Turku, Finland bUniversité des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d’Ascq Cédex, France |
Abstract: | In the Post Correspondence Problem (PCP) an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w)=g(w). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances. |