توالی k منظم

در ریاضیات و علوم نظری رایانه یک توالی Kمنظم یک دنباله نامحدود از اصطلاحات مشخص شده توسط ماشین حالات متناهی است. این توالی‌ها یک تعمیم از توالی‌های kاتوماتیک با حروف الفبایی با اندازه بی‌نهایت هستند.

تاریخچه

اولین تحقیقات در این زمینه توسط برستل و روتنا در زمینه سری‌های منطقی انجام شدکه بسیار مربوط به توالی‌های k-منظم است. سپس توالی‌های k-اتوماتیک تعریف شدند. به یک توالی k-اتوماتیک گفته می‌شود، اگر جمله nام این دنباله توسط یک ماشین حالت متناهی با ورودی n در پایه k تولید شود. Allouche و Shallit اولین بار توالی k-regular را به عنوان یک تعمیم طبیعی از توالی‌های k-اتوماتیک تعریف می‌کنند. با مطالعه مقادیری که دری یک توالی k-منظم به دست می‌آید و مجموعه‌های مختلف توالی‌های k-منظم می‌توان مجموعه‌هایی با ویژگی‌های خاص را مشخص کرد که هر توالی k-regular که مقادیر آن در این مجموعه قرار می‌گیرد، لزوماً k اتوماتیک نیز هست. به‌طور خاص، می‌توان نشان داد که یک توالی منظم نامحدود باید بی‌نهایت مقادیر ترکیبی داشته باشد.

تعریف

می‌گوییم{S(n)}|n>0}} توالی(R,k)-منظم است، اگر تعداد محدودی از توالی‌های (S(1)، S(2)، S(j وجود داشته باشد، که با مقادیر R، هر دنباله در k-هسته (S(n یک ترکیب R-خطی از (S(i است. k-توالی‌های منظم تعاریف ریاضی و غیر ریاضی مخنلفی دارند، که همه این تعاریف معادل یکدیگر هستند. این تعاریف بر مبنای خصوصیات مختلفی است که توالی‌های k-منظم دارند. بعضی از خصوصیات رایج این توالی‌ها به شرح زیر است: در هر یک از موارد زیر،'R را یک حلقه نوتری جابجایی پذیر و R را یک حلقه (ریاضی) حاوی'R فرض خواهیم کرد.

هسته k

فرض کنید: k ≥ ۲. هسته k توالی (S(n مجموعه ای از زیرتوالی‌هایی است که:

$K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.$

به توالی (s(n، توالی R',k)-regular) (اغلب به اختصار "k-regular")گفته می‌شود اگر (K_k (s یک زیرماژول از یک 'R-ماژول متناهی تولید شده باشد.

ترکیب‌های خطی

توالی (s(n یک توالی k-منظم است اگر عدد صحیحی مانند E وجود داشته باشد، که به ازای جمیع مقادیر e_j> E and 0 ≤ r_j ≤ k^e_j − ۱, بتوان هر زیرتوالی از s به فرم (s(k^e_jn + r_j را به عنوان یک ترکیب خطی از 'R به شکل $\sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})$, نوشت جایی که c_ij یک عدد صحیح است و f_ij ≤ E, و ۰ ≤ b_ij ≤ k^f_ij.

به صورت جایگزین، توالی (s(n یک توالی k-منظم است اگر عدد r و زیرتوالی‌های (s₁(n), … , s_r(n وجود داشته باشند به طوری که برای هر ۱ ≤ r ≥ i و ۰ ≤ k − ۱ ≥ a, هر توالی (si(kn + a در هسته k مربوط به (Kk(s یک ترکیب خطی 'R از زیرتوالی‌ها (si(n است.

سری‌های توانی

فرض کنیدx₀, … , x_{k − 1} مجموعه ای از k متغیر غیرقابل جایگزینی باشند و فرض کنید τ یک متغیر مپ باشد که تعدادی عدد طبیعی مانند n را به رشته x_a0 … x_{ae − 1}, ارسال می‌کند و پیوند می‌دهد. به صورتی که نمایش پایه k برای رشتهٔ x به صورت a_{e − 1}...a₀. خواهد بود. سپس توالی (s(n یک توالی k-منظم است اگر و تنها اگر سری توانی صوری $\sum _{n\geq 0}s(n)\tau (n)$ با منطق اعداد صحیح سازگار باشد.

نظریه آتوماتا

تعریف سری توانی یک توالی k-regular منجر به کشف خصوصیات یک ماشین آتوماتا مشابه با ماشین ماتریس شوتزنبرگر خواهد شد.

مثال‌ها

توالی ثو-مورس

دنبالهٔ ثو-مورس ((t(n) در حقیقت نقطه ثابت مورفیسم ۰۱ → ۰، ۰۱ → ۱ است. ثابت شده است که توالی ی ثو-مورس به ۲-خودکار است؛ بنابراین، این توالی ۲-منظم نیز هست و ۲-هسته آن یعنی:

$\{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}$

شامل زیرتوالی‌های $t(n)_{n\geq 0}$ و $t(2n+1)_{n\geq 0}$ خواهد شد.

توالی رولر

فرض کنید (h(n) = ν₂(n + 1 یک ارزش گذاری ۲-ادیک از n + 1 باشد. توالی رولر ((h(n) یک توالی ۲-منظم است و ۲-هسته ان یعنی:

$\{h(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}$

در فضای برداری دوبعدی ساخته شده توسط (h(n و توالی ثابت $1,1,1,\dots$ قرار می‌گیرد. این عناصر پایه ای منجر به رسیدن به روابط بازگشتی زیر خواهد شد.

${\begin{aligned}h(2n)&=0,\\h(4n+1)&=h(2n+1)-s(n),\\h(4n+3)&=2h(2n+1)-s(n),\end{aligned}}$

که در کنار شرایط اولیه h(0) = 0 and h(۱) = ۱، توالی را به صورت یکتا می‌یابند.

اعداد کانتور

توالی مجموعه کانتور یا اعداد کانتور ((c(n) از اعدادی تشکیل شده است که بسط ترنری آن‌ها شامل عدد یک نمی‌شود. بسیار ساده است که نشان دهیم:

${\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}$

و بنابراین توالی اعداد کانتور ۲-منظم است.

مرتب‌سازی ادغامی

یک کاربرد جالب از مفهوم k-منظم درحین مطالعه گسترده‌تر مبحث الگوریتم هادر تجزیه و تحلیل مرتب‌سازی ادغامی بافت شده است. باداشتن لیستی از n مقدار مختلف تعداد مقایسه‌هایی که توسط الگوریتم مرتب‌سازی ادغامی انجام می‌شود از روابط بازگشتی زیر به دست می‌آید.

${\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}$

در نتیجه توالی تعریف شده توسط روابط بازگشتی برای مرتب‌سازی ادغامی، یعنی (T(n یک توالی ۲-منظم را تشکیل می‌دهد.

تعداد بیشتری مثال در دیگر کتاب‌ها موجود است که نام برخی از این کتاب‌ها در قسمت منابع آورده شده‌است.

خواص

توالی‌های k-منظم تعدادی ویژگی جالب دارند. فهرستی کوتاه از این ویژگی‌ها در زیر ارائه شده‌است.

• هر توالی اتوماتیک یک توالی k-منظم است.
• یک توالی k-منظم تعداد متناهی از مقادیر را می‌پذیرد، اگر و تنها اگر k-اتوماتیک باشد. این یک نتیجه فوری از این موضوع است که کلاس توالی‌های k-منظم از کلاس توالی‌های k-اتوماتیک درست شده‌اند.
• کلاس توالی‌های k-regular نسبت به عملیات بسته به زمان جمع و ضرب کلمه به کلمه(termwise) و کانولوشن بسته است. کلاس توالی‌های k-regular، همچنین تحت مقیاس دهی و جابجایی هر عضو از توالی با یک عدد صحیح λ نیز بسته است.

در استقلال چندوجهی، جایی که k, l ≥ ۲، اگر یک توالی هم k-منظم و هم l-منظم باشد، توالی از شرایط بازگشت خطی برخوردار خواهد شد. این مبحث یک تعمیم به نتایج گرفته شده توسط Cobahm مربوط به توالی‌هایی است که هم k-اتوماتیک و هم l-اتومانیک هستند.

منابع

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98: 163–197, doi:10.1016/0304-3975(92)90001-v.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoret. Comput. Sci., 307: 3–29, doi:10.1016/s0304-3975(03)00090-2.
• P.Bell, Jason (2005), "Advances in Applied Mathematics", On the values attained by a k-regular sequence, 10: 634–643.
• Hnasen, Helle Hvid; Kupke, Clemens; Rutten, Jan; Winter, Joost (2014), A final coalgebra for k-regular sequences, vol. 21, pp. 1–21.
• نویسندگان ویکی‌پدیا، K-Regular Sequence