کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436537 690012 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A two-valued recurrent double sequence that is not automatic
ترجمه فارسی عنوان
یک توالی دوبارۀ دوقطبی که به صورت اتوماتیک نیست
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A recurrent 2-dimensional (double) sequence t(m,n) is given by fixing particular sequences t(m,0), t(0,n) as initial conditions and a rule of recurrence t(m,n)=f(t(m,n−1),t(m−1,n−1),t(m−1,n)) for m,n⩾1. We display such a sequence with constant initial conditions and values in the set {0,1} and we show that all rows are periodic and that the minimal period of the n-th row has length 2n. We conclude that this 2-dimensional sequence is not k,l-automatic for any k,l⩾2. Other two-valued recurrent double sequences with constant initial conditions are shortly discussed. They are all automatic, excepting one case, which remains open.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 528, 3 April 2014, Pages 32-39
نویسندگان
,