کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438374 690265 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extension of the decidability of the marked PCP to instances with unique blocks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Extension of the decidability of the marked PCP to instances with unique blocks
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 380, Issue 3, 28 June 2007, Pages 355-362