کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874263 | 686948 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The exact complexity of the infinite Post Correspondence Problem
ترجمه فارسی عنوان
پیچیدگی دقیق از مسائل مربوط به متن پست نامتناهی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نظریه محاسبات، زبان رسمی، پیچیدگی محاسباتی، مشکلات تصمیم گیری، مسائل مربوط به پست الکترونیکی بی نهایت، پیچیدگی دقیق، Î 10 کامل،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this short note, we give the exact complexity of the infinite Post Correspondence Problem, showing that it is Î 10-complete. Surprisingly, it turns out that the infinite Post Correspondence Problem is not “more complex” than the Post Correspondence Problem, which is known to be Σ10-complete, but has the exact dual complexity. This gives an answer to a question of Simonnet [15].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 609-611
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 609-611
نویسندگان
Olivier Finkel,