首页 | 本学科首页   官方微博 | 高级检索  
     


Extension of the decidability of the marked PCP to instances with unique blocks
Authors:Vesa Halava  Tero Harju  Juhani Karhumki  Michel Latteux
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)(h,g) consists of two morphisms hh and gg, and the problem is to determine whether or not there exists a nonempty word ww such that h(w)=g(w)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.
Keywords:Post Correspondence Problem  Infinite Post Correspondence Problem  Marked morphism  Unique continuation  Unique block  Decidability
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号