کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649568 | 1342460 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial-time algorithm for fixed points of nontrivial morphisms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Polynomial-time algorithm for fixed points of nontrivial morphisms Polynomial-time algorithm for fixed points of nontrivial morphisms](/preview/png/4649568.png)
چکیده انگلیسی
A word ww is a fixed point of a nontrivial morphism hh if w=h(w)w=h(w) and hh is not the identity on the alphabet of ww. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 16, 28 August 2009, Pages 5069–5076
Journal: Discrete Mathematics - Volume 309, Issue 16, 28 August 2009, Pages 5069–5076
نویسندگان
Štěpán Holub,