State Complexity of Shifts of the Fibonacci Word

إليك ملخص تقني مفصل لورقة البحث بعنوان "التعقيد الحالاتي لإزاحات كلمة فيبوناتشي" (State Complexity of Shifts of the Fibonacci Word) من تأليف ديلارام مورادي، بيير بوبولي، جيفري شاليت، وإنغريد فوكوسيك.

1. بيان المشكلة

تتقصى الورقة البحثية التعقيد الحالاتي (state complexity) لتوليد النسخ المزاحة من كلمة فيبوناتشي $f = (f_i)_{i \ge 0}$.

• السياق: تُعد كلمة فيبوناتشي مثالاً نموذجياً لتسلسل تلقائي (تحديداً تسلسل تلقائي فيبوناتشي)، ويتم توليده بواسطة آلة ذات حالات محدودة ذات مخرجات (DFAO).
• العملية: يدرس المؤلفون التسلسل المزاح $(f_{i+c})_{i \ge 0}$ لقيمة إزاحة ثابتة $c \ge 0$.
• السؤال: بالنظر إلى أن التسلسل الأصلي $f$ يتم توليده بواسطة DFAO صغير (5 حالات للتمثيل من الخانة الأقل أهمية أولاً، أو lsd-first، وحالتين للتمثيل من الخانة الأكثر أهمية أولاً، أو msd-first، في تمثيل زيكندورف)، فما هو التعقيد الحالاتي لـ DFAO الأدنى المطلوب لتوليد التسلسل المزاح $(f_{i+c})_{i \ge 0}$؟
• الدوافع: في أنظمة الأساس $k$ القياسية، تتطلب إزاحة تسلسل بمقدار $c$ عادةً $O(m \log c)$ حالة لمدخلات lsd-first. ومع ذلك، في تمثيل زيكندورف (أساس فيبوناتشي)، لا توجد أدوات تحويل جمع قياسية لأن الجمع لا يمكن إجراؤه في تمريرة واحدة. وعلاوة على ذلك، بالنسبة لتسلسلات أخرى مثل تسلسل ثو-مور (Thue-Morse)، قد تتطلب إزاحات msd-first عدد حالات يصل إلى $O(c)$. يهدف المؤلفون إلى تحديد ما إذا كانت كلمة فيبوناتشي تظهر تعقيداً أكثر كفاءة للإزاحات.

2. المنهجية

يستخدم المؤلفون نهجاً هجيناً يجمع بين نظرية الآلات الذاتية (automata theory)، والتقريب الديوفانتي (Diophantine approximation)، والمنطق الصوري (formal logic).

أ. التوصيف الرياضي لكلمة فيبوناتشي

يعتمد جوهر البرهان على التوصيف الهندسي لكلمة فيبوناتشي باستخدام الأجزاء الكسرية لمضاعفات النسبة الذهبية $\phi = \frac{1+\sqrt{5}}{2}$.

• التمهيدية 1: $f(i) = 1$ إذا وفقط إذا كان $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$.
• التمهيدية 2 (المزاحة): $f(i+c) = 1$ إذا وفقط إذا كان $\{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$.
  هذا يحول مشكلة توليد التسلسل إلى مشكلة تحديد الجزء (الفاصل الزمني) الذي يقع فيه القيمة $\{i\phi\}$ ضمن الوحدة (modulo 1).

ب. تقسيم وحدة الفترة

يبني المؤلفون تقسيمات محددة للفترة $[0, 1)$ بناءً على تمثيل المدخلات (تمثيل زيكندورف).

• بالنسبة لـ lsd-first: يعرّفون تقسيماً $I_d(m)$ ناتجاً عن أول $d$ من خانات تمثيل زيكندورف. ويثبتون أن البتات منخفضة الرتبة للعدد الصحيح $n$ تحدد الفترة التي يقع فيها $\{n\phi\}$. وترتبط نهايات هذه الفترات بالقيم $\{-k\phi\}$.
• بالنسبة لـ msd-first: يعرّفون تقسيماً $P(r)$ بناءً على تسلسل الأعداد الصحيحة الناتجة عن "إزاحة" تمثيل عدد صحيح سالب (حذف الخانة الأكثر أهمية). ويُظهر هذا التقسيم أنه متسق (consistent) مع تمثيل فيبوناتشي msd-first، مما يعني أن قراءة خانة ما تنقل الآلة من فترة في التقسيم إلى فترة محددة أخرى داخل نفس التقسيم.

ج. إثبات النظريات المؤتمت (Automated Theorem Proving)

يتم التحقق من جزء كبير من البراهين التقنية، خاصة فيما يتعلق باتساق التقسيمات وسلوك الفترات تحت عمليات إضافة/حذف الخانات، باستخدام Walnut، وهو برنامج مؤتمت لإثبات النظريات للتسلسلات التلقائية. يقوم المؤلفون بترميز خصائص كلمة فيبوناتشي وخرائط الفترات في المنطق من الدرجة الأولى ويستخدمون Walnut للتحقق بصرامة من صحة التمهيديات.

3. المساهمات والنتائج الرئيسية

أ. النظرية الرئيسية: التعقيد الحالاتي اللوغاريتمي

النتيجة الأساسية للورقة هي أن التعقيد الحالاتي لكلمة فيبوناتشي المزاحة هو $O(\log c)$ لكل من مدخلات lsd-first و msd-first.

• النظرية 1 (lsd-first): يوجد DFAO من نوع lsd-first لـ $(f_{i+c})$ بـ $O(\log c)$ من الحالات.
• النظرية 3 (msd-first): يوجد DFAO من نوع msd-first لـ $(f_{i+c})$ بـ $O(\log c)$ من الحالات.

هذه نتيجة هامة لأنها:

1. تتباين مع تسلسل ثو-مور، حيث يمكن أن تتطلب إزاحات msd-first عدد حالات يصل إلى $O(c)$.
2. قريبة من الحد الأدنى للمعلومات النظرية للتسلسلات غير الدورية، وهو $\Omega(\frac{\log c}{\log \log c})$.

ب. الصيغة الدقيقة للتعقيد الحالاتي (lsd-first)

يقدم المؤلفون صيغة دقيقة لأدنى عدد من الحالات المطلوبة لحالة lsd-first (النظرية 2):
$$\text{States} = 2(|(c)_F| + 1) + 1 - g(c)$$
حيث أن:

• $|(c)_F|$ هو طول تمثيل زيكندورف لـ $c$.
• $g(c) = 1$ إذا كان $f(c-1) = f(c-2) = 0$، و $0$ خلاف ذلك.
  وهذا يؤكد أن حد $O(\log c)$ هو أمثل، حيث ينمو عدد الحالات خطياً مع طول تمثيل زيكندورف لـ $c$.

ج. تقنيات البناء

• بناء lsd-first: تتبع الآلة الفترة $I_d(m)$ التي تحتوي على $\{n\phi\}$. وبمجرد أن يصبح طول المدخل $d$ كافياً بحيث تكون الفترة $I_d(m)$ محتواة بالكامل داخل الفترة المستهدفة $J_c = (-(c+1)\phi, -(c+2)\phi)$ (أو متممتها)، تنتقل الآلة إلى حالة "الامتصاص" (sink state). ويتم حصر عدد هذه الحالات "الوسطية" بعدد خانات $c$.
• بناء msd-first: يبني المؤلفون تقسيماً $P$ عبر دمج نهايات التقسيمات $P(-(c+1))$ و $P(-(c+2))$. ولأن هذا التقسيم متسق مع تمثيل msd-first، فإن حالات الآلة تتوافق مباشرة مع الفترات في $P$. ويتناسب عدد النهايات مع عدد أعداد فيبوناتشي الأقل من $c$، مما يعطي $O(\log c)$ من الحالات.

4. الأهمية

1. حل حالة محددة: تحل الورقة مسألة التعقيد الحالاتي لأشهر كلمة غير دورية (كلمة فيبوناتشي) تحت عملية الإزاحة، وتُظهر أنها تسلك سلوكاً "أمثل" مقارنة بالتسلسلات التلقائية الأخرى.
2. ابتكار منهجي: تُظهر قوة الجمع بين التقريب الديوفانتي (خصائص $\{n\phi\}$) ونظرية الآلات الذاتية. إن استخدام الأجزاء الكسرية لتعريف حالات الآلة هو تقنية مبتكرة وقوية لتسلسلات فيبوناتشي التلقائية.
3. التحقق من الأدوات: يعزز الاستخدام الناجح لـ Walnut لإثبات الخصائص الهندسية المعقدة للفترات من فائدة إثبات النظريات المؤتمت في التراكيب اللغوية (combinatorics on words).
4. إمكانية التعميم: يشير المؤلفون إلى أن هذه التقنيات قد تمتد إلى الأعداد غير النسبية التربيعية الأخرى وربما كلمة تريبوناتشي (Tribonacci word)، مما يفتح آفاقاً لأبحاث مستقبلية في التعقيد الحالاتي للإزاحات في أنظمة تعداد أخرى.

ملخص

تثبت الورقة أن إزاحة كلمة فيبوناتشي بمقدار $c$ من المواضع ينتج عنها تسلسل يمكن التعرف عليه بواسطة آلة ذات حالات محدودة بـ $O(\log c)$ فقط من الحالات، بغض النظر عما إذا كان المدخل يُقرأ من الخانة الأكثر أهمية أو الأقل أهمية. ويتحقق ذلك من خلال ربط المشكلة بهندسة الأجزاء الكسرية لمضاعفات النسبة الذهبية وبناء تقسيمات فترية محددة تحترم بنية تمثيل زيكندورف. تسلط النتائج الضوء على الكفاءة الهيكلية الفريدة لكلمة فيبوناتشي مقارنة بالتسلسلات التلقائية الأخرى.