کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875481 1441957 2018 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On fixed points of rational transductions
ترجمه فارسی عنوان
در نقاط ثابت انتقالهای منطقی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , ,