نظرية كروهن-رودس

في الرياضيات وعلوم الحاسوب ، تُعدّ نظرية كروهن-رودس (أو نظرية الأوتوماتا الجبرية ) منهجًا لدراسة أنصاف الزمر والأوتوماتا المنتهية ، ويسعى إلى تحليلها إلى مكونات أولية. تتوافق هذه المكونات مع أنصاف الزمر غير الدورية المنتهية والزمر البسيطة المنتهية التي تُدمج بطريقة لا تعتمد على التغذية الراجعة (وتُسمى " الضرب الإكليلي " أو "التتالي").

توصل كروهن ورودز إلى تحليل عام للأوتوماتا المحدودة . اكتشف الباحثان وأثبتا نتيجةً رئيسيةً غير متوقعة في نظرية أنصاف الزمر المحدودة، كاشفين عن صلة وثيقة بين الأوتوماتا المحدودة وأنصاف الزمر. لطالما حفزت قابلية حسم تعقيد كروهن-رودز الكثير من الأبحاث في نظرية أنصاف الزمر. في يونيو 2024، أعلن ستيوارت مارغوليس وجون رودز وآن شيلينغ عن برهان على أن هذا التعقيد قابل للحسم. ^{[ 1 ]}

يترك${\displaystyle T}$أن تكون شبه مجموعة. شبه مجموعة${\displaystyle S}$هذا هو صورة متماثلة لشبه مجموعة فرعية من${\displaystyle T}$ويُقال إنه قاسم لـ${\displaystyle T}$.

تنص نظرية كروهن -رودس للمجموعات النصفية المنتهية على أن كل مجموعة نصفية منتهية${\displaystyle S}$هو قاسم لضرب إكليل متناوب منتهٍ لمجموعات بسيطة منتهية ، كل منها قاسم لـ${\displaystyle S}$ومجموعات شبه دورية محدودة (التي لا تحتوي على مجموعات فرعية غير تافهة ). ^{[ 2 ]}

في صياغة الأوتوماتا، تنص نظرية كروهن-رودس للأوتوماتا المحدودة على أنه بالنظر إلى أوتوماتا محدودة${\displaystyle A}$مع الولايات${\displaystyle Q}$وأدخل الأبجدية${\displaystyle I}$إخراج الأبجدية${\displaystyle U}$ثم يمكن توسيع نطاق الولايات إلى${\displaystyle Q'}$ بحيث يكون الأوتوماتون الجديد${\displaystyle A'}$تندمج في سلسلة من الآلات "البسيطة" وغير القابلة للاختزال: على وجه الخصوص،${\displaystyle A}$يتم محاكاتها بواسطة سلسلة تغذية أمامية من (1) آلات ذاتية التشغيل تكون مجموعات تحويلها شبه مجموعات بسيطة منتهية، و(2) آلات ذاتية التشغيل عبارة عن مجموعات من القلابات تعمل بالتوازي. ^{[ ملاحظة 1 ]} الآلة الذاتية التشغيل الجديدة${\displaystyle A'}$يحتوي على نفس رموز الإدخال والإخراج مثل${\displaystyle A}$هنا، تتمتع كل من حالات ومدخلات الأوتوماتا المتتالية بشكل إحداثيات هرمي خاص للغاية.

علاوة على ذلك، فإن كل زمرة بسيطة ( أولية ) أو شبه زمرة غير قابلة للاختزال (شبه زمرة فرعية من شبه زمرة القلاب ) التي تقسم شبه زمرة التحويل لـ${\displaystyle A}$يجب أن يقسم شبه زمرة التحويل لأحد مكونات السلسلة، والأعداد الأولية فقط التي يجب أن تظهر كقواسم للمكونات هي تلك التي تقسم${\displaystyle A}$شبه المجموعة التحويلية ' s.

إن تعقيد كروهن-رودس (يسمى أيضًا تعقيد المجموعة أو ببساطة التعقيد ) لشبه مجموعة منتهية S هو أقل عدد من المجموعات في حاصل ضرب إكليل من المجموعات المنتهية وشبه المجموعات غير الدورية المنتهية التي تكون S قاسمًا لها.

جميع أنصاف الزمر غير الدورية المنتهية لها تعقيد صفري، بينما الزمر المنتهية غير التافهة لها تعقيد واحد. في الواقع، توجد أنصاف زمر ذات تعقيد عدد صحيح غير سالب . على سبيل المثال، لأي قيمة n أكبر من 1، فإن نصف الزمرة الضربية لجميع المصفوفات المثلثية العلوية ( n + 1) × ( n + 1) على أي حقل منتهٍ ثابت لها تعقيد n (كامبايتس، 2007).

تُعدّ مسألة قابلية حلّ التعقيد من أهمّ المسائل المفتوحة في نظرية الزمر النصفية المنتهية : هل توجد خوارزمية لحساب تعقيد كروهن-رودس لزمرة نصفية منتهية، بمعلومية جدول الضرب الخاص بها ؟ وقد تمّ التوصل إلى حدود عليا وحدود دنيا أكثر دقة للتعقيد (انظر، على سبيل المثال، رودس وستاينبرغ، 2009). وقد افترض رودس أن المسألة قابلة للحلّ. ^{[ 3 ]} في يونيو 2024، أعلن ستيوارت مارغوليس وجون رودس وآن شيلينغ عن برهان يُثبت صحة هذا الافتراض، إلا أنه حتى عام 2025 لم يتمّ تأكيد النتيجة. ^{[ 1 ]}

في مؤتمر عُقد عام ١٩٦٢، أعلن كينيث كروهن وجون رودس عن طريقة لتحليل آلة الحالة المحدودة (الحتمية) إلى مكونات "بسيطة" تُعدّ بدورها آلات حالة محدودة. هذا العمل المشترك، الذي له آثار على الفلسفة ، شمل أطروحة الدكتوراه لكل من كروهن في جامعة هارفارد ورودس في معهد ماساتشوستس للتكنولوجيا . ^{[ ٤ ]} ومنذ ذلك الحين، نُشرت براهين أبسط وتعميمات للنظرية لتشمل البنى اللانهائية (انظر الفصل الرابع من كتاب رودس وستاينبرغ الصادر عام ٢٠٠٩ بعنوان " نظرية q لأنصاف الزمر المحدودة " للاطلاع على نظرة عامة).

في ورقة بحثية نُشرت عام ١٩٦٥ من قِبل كروهن ورودس، اعتمد برهان نظرية تفكيك الأوتوماتا المحدودة (أو ما يُكافئها من آلات متسلسلة ) بشكل كبير على بنية شبه المجموعة الجبرية . وتضمنت البراهين اللاحقة تبسيطات جوهرية باستخدام جداءات الإكليل المحدودة لشبه مجموعات التحويل المحدودة. تُعمم النظرية تفكيك جوردان-هولدر للمجموعات المحدودة (حيث تكون الأعداد الأولية هي المجموعات البسيطة المحدودة) ليشمل جميع شبه مجموعات التحويل المحدودة (حيث تكون الأعداد الأولية هي المجموعات البسيطة المحدودة بالإضافة إلى جميع شبه المجموعات الفرعية لـ "القلاب" (انظر أعلاه)). يتطلب كل من تفكيك المجموعة وتفكيك الأوتوماتا المحدودة الأكثر عمومية توسيع مجموعة حالات التفكيك العام، ولكنهما يسمحان بنفس عدد رموز الإدخال. في الحالة العامة، تُدمج هذه الرموز في بنية أكبر ذات "نظام إحداثيات" هرمي.

يجب توخي الحذر عند فهم مفهوم "الأولي"، إذ يشير كروهن ورودز صراحةً إلى نظريتهما على أنها "نظرية تفكيك أولي" للآلات. مع ذلك، فإن مكونات التفكيك ليست آلات أولية (حيث يُعرَّف الأولي تعريفًا بسيطًا)؛ بل إن مفهوم الأولي أكثر تعقيدًا وجبريًا: فالمجموعات الجزئية والمجموعات المرتبطة بالآلات المكونة للتفكيك هي أولية (أو غير قابلة للاختزال) بمعنى جبري دقيق وطبيعي بالنسبة إلى جداء الإكليل ( إيلنبرغ ، 1976). كذلك، وخلافًا لنظريات التفكيك السابقة، تتطلب تفكيكات كروهن-رودز عادةً توسيع مجموعة الحالات، بحيث تغطي الآلة الموسعة (تحاكي) الآلة التي يتم تفكيكها. وقد جعلت هذه الحقائق النظرية صعبة الفهم وصعبة التطبيق بطريقة عملية - حتى وقت قريب، عندما أصبحت التطبيقات الحسابية متاحة (Egri-Nagy & Nehaniv 2005، 2008).

أثبت إتش بي زيغر (1967) وجود صيغة مهمة تُسمى تحليل الهولوونومي (إيلنبرغ 1976). ^{[ ملاحظة 2 ]} يبدو أن طريقة الهولوونومي فعالة نسبيًا، وقد تم تطبيقها حسابيًا بواسطة أ. إغري-ناغي (إغري-ناغي ونهانيف 2005).

يقدم ماير وتومسون (1969) نسخة من تحليل كروهن-رودس للآلات المحدودة التي تعادل التحليل الذي طوره هارتمانيس وستيرنز سابقًا، ولكن بالنسبة للتحليلات المفيدة، فإن مفهوم توسيع مجموعة حالات الآلة الأصلية أمر ضروري (في حالة الآلات غير التبديلية).

توجد الآن العديد من البراهين والتركيبات لتفكيكات كروهن-رودس (مثل [Krohn, Rhodes & Tilson 1968]، [Ésik 2000]، [Diekert et al. 2012])، وتُعدّ طريقة الهولوونوميا الأكثر شيوعًا وكفاءة بشكل عام (وإن لم تكن كذلك في جميع الحالات). [Zimmermann 2010] ^{[ 5 ]} يُقدّم برهانًا أوليًا للنظرية. نظرًا للعلاقة الوثيقة بين المونويدات والفئات ، فإنّ صيغة من نظرية كروهن-رودس قابلة للتطبيق على نظرية الفئات . وقد قدّم ويلز (1980) هذه الملاحظة وبرهانًا لنتيجة مماثلة. ^{[ ملاحظة 3 ]}

تُعدّ نظرية كروهن-رودس لأنصاف الزمر/المونويدات نظيرًا لنظرية جوردان-هولدر للزمر المنتهية (لأنصاف الزمر/المونويدات بدلًا من الزمر). وبذلك، تُعتبر هذه النظرية نتيجةً عميقةً وهامةً في نظرية أنصاف الزمر/المونويدات. وقد أثارت هذه النظرية دهشة العديد من علماء الرياضيات وعلوم الحاسوب ^{[ ملاحظة 4 ]} ، إذ كان يُعتقد سابقًا على نطاق واسع أن بديهيات أنصاف الزمر/المونويدات ضعيفةٌ جدًا بحيث لا تسمح بصياغة نظرية بنية ذات قوة تُذكر، وأن الدراسات السابقة (هارتمانيس وستيرنز) لم تتمكن إلا من إظهار نتائج تفكيك أكثر صرامةً وأقل عموميةً للآلات المنتهية.

يستمر العمل الذي قام به إيغري ناجي ونيهانيف (2005، 2008–) في أتمتة نسخة الهولوونومي من تحليل كروهن-رودس الممتد مع التحليل ذي الصلة للمجموعات المنتهية (ما يسمى بإحداثيات فروبينيوس-لاغرانج ) باستخدام نظام الجبر الحاسوبي GAP .

أصبحت التطبيقات خارج نطاق نظريات شبه المجموعة والمونويد ممكنة حسابيًا الآن. وتشمل هذه التطبيقات الحسابات في علم الأحياء والأنظمة الكيميائية الحيوية (على سبيل المثال، Egri-Nagy & Nehaniv 2008)، والذكاء الاصطناعي ، وفيزياء الحالة المحدودة ، وعلم النفس ، ونظرية الألعاب (انظر، على سبيل المثال، Rhodes 2009).

• عمل شبه جماعي
• شبه مجموعة التحويل
• علاقات غرين

ملحوظات

مراجع

• رودس (2010)
• رودز وستاينبرغ (2008)
• ستراوبينغ (1994)

• صفحة البروفيسور جون ل. رودس، جامعة كاليفورنيا في بيركلي
• SgpDec: التركيب والتفكيك الهرمي لمجموعات التبديل ومجموعات التحويل شبهية ، من تطوير أ. إغري-ناغي وسي إل نيهانيف . حزمة برمجية مفتوحة المصدر لنظام الجبر الحاسوبي GAP .
• مقدمة لنظرية كروهن-رودس (القسم 5)؛ جزء من دورة سانتا في إنستيتيوت إكسبلورس الإلكترونية المفتوحة حول مقدمة إعادة التطبيع ، بقلم سيمون ديديو.