کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875481 | 1441957 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On fixed points of rational transductions
ترجمه فارسی عنوان
در نقاط ثابت انتقالهای منطقی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f:AââAâ has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a corollary we obtain that the existence of a fixed point of injective computable functions is undecidable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 85-88
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 85-88
نویسندگان
Vesa Halava, Tero Harju, Esa Sahla,