کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433851 689640 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The sequence of return words of the Fibonacci sequence
ترجمه فارسی عنوان
توالی کلمات بازگشتی دنباله فیبوناچی
کلمات کلیدی
کلمات بازگشت دنباله فیبوناچی، هسته منحصر به فرد، تجزیه تکاملی، طیف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let ω   be a factor of the Fibonacci sequence F∞=x1x2⋯F∞=x1x2⋯, then it occurs in the sequence infinitely many times. Let ωpωp be the p-th occurrence of ω   and rp(ω)rp(ω) be the p-th return word over ω  . In this paper, we study the structure of the sequence of return words {rp(ω)}p≥1{rp(ω)}p≥1. We first introduce the singular kernel word sk(ω)sk(ω) for any factor ω   of F∞F∞ and give a decomposition of ω   with respect to sk(ω)sk(ω). Using the singular kernel and the decomposition, we prove that the sequence of return words over the alphabet {r1(ω),r2(ω)}{r1(ω),r2(ω)} is still a Fibonacci sequence. We also determine the expressions of return words completely for each factor. Finally we introduce the spectrum for studying some combinatorial properties, such as power, overlap and separate of factors.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 106–116
نویسندگان
, ,