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


Extension of the decidability of the marked PCP to instances with unique blocks
Authors:Vesa Halava, Tero Harju, Juhani Karhum  ki,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号