أوتوماتون ω

في نظرية الأوتوماتا ، وهي فرع من علوم الحاسوب النظرية ، تُعدّ الأوتوماتا ω (أو أوتوماتا التدفق ) نوعًا من الأوتوماتا المحدودة التي تعمل على سلاسل لا نهائية كمدخلات، بدلًا من سلاسل محدودة. ولأن الأوتوماتا ω لا تتوقف، فإن لها شروط قبول متنوعة بدلًا من مجموعة محددة من حالات القبول.

تُعدّ آلات ω مفيدةً لتحديد سلوك الأنظمة التي لا يُتوقع أن تنتهي، مثل الأجهزة وأنظمة التشغيل وأنظمة التحكم . بالنسبة لهذه الأنظمة، قد يرغب المرء في تحديد خاصية مثل "لكل طلب، يتبعه في النهاية تأكيد استلام"، أو نفيها "يوجد طلب لا يتبعه تأكيد استلام". الخاصية الأولى هي خاصية للكلمات غير المحدودة: لا يمكن القول عن متتالية محدودة أنها تُحقق هذه الخاصية.

تشمل فئات آلات ω-automata آلات بوشي ، وآلات رابين، وآلات ستريت، وآلات التكافؤ، وآلات مولر ، وكل منها حتمية أو غير حتمية. تختلف هذه الفئات من آلات ω-automata فقط في شرط القبول . جميعها تتعرف بدقة على لغات ω- automata المنتظمة باستثناء آلة بوشي الحتمية، التي تُعد أضعف من جميع الأنواع الأخرى. على الرغم من أن جميع هذه الأنواع من الآلات تتعرف على نفس مجموعة لغات ω-automata ، إلا أنها تختلف في مدى اختصار تمثيلها للغة ω-automata معينة.

بصورة رسمية، فإن الأوتوماتون الحتمي من نوع ω هو مجموعة مرتبة${\textstyle A=(Q,\Sigma ,\delta ,q_{0},A_{acc})}$، والتي تتكون من المكونات التالية:

• ${\textstyle Q}$، هي مجموعة منتهية . عناصر${\textstyle Q}$تُسمى ولايات​${\textstyle A}$.
• ${\textstyle \Sigma }$، هي مجموعة منتهية تسمى أبجدية${\textstyle A}$.
• ${\textstyle \delta \colon Q\times \Sigma \rightarrow Q}$هي دالة تسمى دالة الانتقال لـ${\textstyle A}$.
• ${\textstyle Q_{0}}$هو عنصر من${\textstyle Q}$، وتسمى الحالة الأولية.
• ${\textstyle A_{acc}}$هي مجموعة من حالات القبول لـ${\textstyle A}$، رسمياً مجموعة فرعية من${\textstyle Q^{\omega }}$.

مدخل لـ​${\textstyle A}$هي سلسلة لا نهائية على الأبجدية${\textstyle \Sigma }$أي أنها سلسلة لا نهائية${\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )}$جري​​${\textstyle A}$على مثل هذا المدخل يكون تسلسلًا لانهائيًا${\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )}$من الدول، والتي تُعرَّف على النحو التالي:

• ${\textstyle r_{0}=q_{0}}$.
• ${\textstyle r_{1}=\delta (r_{0},a_{1})}$.
• ${\textstyle r_{2}=\delta (r_{1},a_{2})}$.

...

• أي لكل${\textstyle i}$:${\textstyle r_{i}=\delta (r_{i-1},a_{i})}$.

يتمثل الغرض الرئيسي من آلة ω-automaton في تحديد مجموعة فرعية من مجموعة جميع المدخلات: مجموعة المدخلات المقبولة . بينما في حالة آلة الأوتوماتون المحدودة العادية، تنتهي كل دورة بحالة${\textstyle r_{n}}$ويتم قبول المدخلات إذا وفقط إذا${\textstyle r_{n}}$في حالة القبول، يكون تعريف مجموعة المدخلات المقبولة أكثر تعقيدًا بالنسبة لآلات ω. هنا يجب أن ننظر إلى التشغيل بأكمله.${\textstyle \rho }$يتم قبول المدخلات إذا كان التشغيل المقابل موجودًا في${\textstyle {\text{Acc}}}$تُسمى مجموعة كلمات ω المدخلة المقبولة لغة ω المُعترف بها بواسطة الآلة، والتي يُشار إليها بـ${\textstyle L(A)}$.

تعريف${\textstyle {\text{Acc}}}$كجزء من${\textstyle Q^{\omega }}$هو شكلي بحت وغير مناسب للتطبيق العملي لأن هذه المجموعات عادةً ما تكون لانهائية. ويكمن الاختلاف بين أنواع مختلفة من آلات ω-automata (مثل Büchi وRabin وغيرها) في كيفية ترميزها لمجموعات فرعية معينة.${\textstyle {\text{Acc}}}$ل${\textstyle Q^{\omega }}$باعتبارها مجموعات محدودة، وبالتالي يمكنها ترميز هذه المجموعات الفرعية.

بصورة رسمية، فإن الأوتوماتون ω غير الحتمي هو مجموعة مرتبة${\textstyle A=(Q,\Sigma ,\Delta ,Q_{0},{\text{Acc}})}$والتي تتكون من المكونات التالية:

• ${\textstyle Q}$هي مجموعة منتهية . عناصر${\textstyle Q}$تُسمى ولايات​${\textstyle A}$.
• ${\textstyle \Sigma }$هي مجموعة منتهية تسمى أبجدية${\textstyle A}$.
• ${\textstyle \Delta }$هي مجموعة فرعية من${\textstyle Q\times \Sigma \times Q}$وتسمى علاقة الانتقال لـ${\textstyle A}$.
• ${\textstyle Q_{0}}$هي مجموعة فرعية من${\textstyle Q}$، والتي تسمى المجموعة الأولية من الحالات.
• ${\textstyle {\text{Acc}}}$هو شرط القبول ، وهو مجموعة فرعية من${\textstyle Q^{\omega }}$.

بخلاف الأوتوماتون الحتمي ω، الذي يمتلك دالة انتقال${\textstyle \delta }$، النسخة غير الحتمية لها علاقة انتقالية${\textstyle \Delta }$. لاحظ أن${\textstyle \Delta }$يمكن اعتبارها دالة${\textstyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$من${\textstyle Q\times \Sigma }$إلى مجموعة الطاقة${\textstyle {\mathcal {P}}(س)}$وبالتالي، بالنظر إلى حالة معينة${\textstyle q_{n}}$ورمز${\textstyle a_{n}}$الولاية التالية${\textstyle q_{n+1}}$لا يتم تحديدها بالضرورة بشكل فريد، بل هناك مجموعة من الحالات التالية المحتملة.

سلسلة من​${\textstyle A}$عند الإدخال${\textstyle \alpha =(a_{1},a_{2},a_{3},\ldots )}$أي متتالية لانهائية${\textstyle \rho =(r_{0},r_{1},r_{2},\ldots )}$من بين الولايات التي تستوفي الشروط التالية:

• ${\textstyle r_{0}}$هو عنصر من${\textstyle Q_{0}}$.
• ${\textstyle r_{1}}$هو عنصر من${\textstyle \Delta (r_{0},a_{1})}$.
• ${\textstyle r_{2}}$هو عنصر من${\textstyle \Delta (r_{1},a_{2})}$.

...

• أي لكل${\textstyle i}$:${\textstyle r_{i}}$هو عنصر من${\textstyle \Delta (r_{i-1},a_{i})}$.

قد يقبل جهاز ω-automaton غير الحتمي العديد من العمليات المختلفة على أي مدخلات معينة، أو لا يقبل أيًا منها على الإطلاق. تُقبل المدخلات إذا كانت إحدى العمليات الممكنة على الأقل مقبولة. ويعتمد قبول العملية على${\textstyle {\text{Acc}}}$أما بالنسبة للآلات ω-الحتمية، فيمكن اعتبار كل آلة ω-حتمية آلة ω-غير حتمية من خلال أخذ${\textstyle \Delta }$أن يكون الرسم البياني لـ${\textstyle \delta }$. إن تعريفات التشغيل والقبول لآلات ω الحتمية هي حالات خاصة من الحالات غير الحتمية.

قد تكون شروط القبول عبارة عن مجموعات لا نهائية من الكلمات ω. ومع ذلك، يركز الباحثون في الغالب على دراسة شروط القبول التي يمكن تمثيلها بشكل محدود. فيما يلي قائمة بمجموعة متنوعة من شروط القبول الشائعة.

قبل مناقشة القائمة، دعونا نلاحظ الملاحظة التالية. في حالة الأنظمة التي تعمل بلا حدود، غالبًا ما نهتم بمعرفة ما إذا كان سلوك معين يتكرر بلا حدود. على سبيل المثال، إذا استقبلت بطاقة الشبكة عددًا لا نهائيًا من طلبات اختبار الاتصال (ping)، فقد لا تستجيب لبعض هذه الطلبات، ولكن يجب أن تستجيب لمجموعة فرعية لا نهائية منها. وهذا ما يحفز التعريف التالي: لأي عملية تشغيل${\textstyle \rho }$، يترك${\textstyle {\text{Inf}}(\rho )}$لتكن مجموعة الحالات التي تحدث بشكل متكرر لا نهائي في${\textstyle \rho }$إن مفهوم زيارة حالات معينة بشكل متكرر إلى ما لا نهاية سيكون مفيدًا في تحديد شروط القبول التالية.

• آلة بوشي هي آلة ω${\textstyle A}$والتي تستخدم شرط القبول التالي، لمجموعة فرعية معينة${\textstyle F}$ل${\textstyle Q}$:

حالة الكتاب

${\textstyle A}$يقبل تلك الجولات تحديدًا${\textstyle \rho }$والتي${\textstyle {\text{Inf}}(\rho )\cap F\neq \emptyset }$أي أن هناك حالة قبول تحدث بشكل متكرر لا نهائي في${\textstyle \rho }$.

• أإنسان رابين الآلي هو إنسان آلي${\textstyle A}$والتي تستخدم شرط القبول التالي، لمجموعة معينة$أوميغا$أزواج${\textstyle (B_{i},G_{i})}$من مجموعات الحالات:

حالة رابين

${\textstyle A}$يقبل تلك الجولات تحديدًا${\textstyle \rho }$والتي يوجد لها زوج${\textstyle (B_{i},G_{i})}$في$أوميغا$بحيث${\textstyle B_{i}\cap {\text{Inf}}(\rho )=\emptyset }$و${\textstyle G_{i}\cap {\text{Inf}}(\rho )\neq \emptyset }$.

• آلة ستريت هي آلة ω${\textstyle A}$والتي تستخدم شرط القبول التالي، لمجموعة معينة$أوميغا$أزواج${\textstyle (B_{i},G_{i})}$من مجموعات الحالات:

حالة الشارع

${\textstyle A}$يقبل تلك الجولات تحديدًا${\textstyle \rho }$بحيث يكون ذلك لجميع الأزواج${\textstyle (B_{i},G_{i})}$في$أوميغا$،${\textstyle B_{i}\cap {\text{Inf}}(\rho )\neq \emptyset }$أو${\textstyle G_{i}\cap {\text{Inf}}(\rho )=\emptyset }$.

• الآلة المتكافئة هي آلة${\textstyle A}$مجموعة الحالات التي هي${\textstyle Q=\{0,1,2,\ldots ,k\}}$لبعض الأعداد الطبيعية${\textstyle k}$وهذا يتضمن شرط القبول التالي:

شرط التكافؤ

${\textstyle A}$يقبل${\textstyle \rho }$إذا وفقط إذا كان أصغر عدد في${\textstyle {\text{Inf}}(\rho )}$متساوٍ.

• آلة مولر هي آلة ω${\textstyle A}$والتي تستخدم شرط القبول التالي، لمجموعة فرعية${\textstyle \mathbf {F} }$ل${\textstyle {\mathcal {P}}(س)}$( مجموعة القوى لـ${\textstyle Q}$):

حالة مولر

${\textstyle A}$يقبل تلك الجولات تحديدًا${\textstyle \rho }$والتي${\textstyle {\text{Inf}}(\rho )\in \mathbf {F} }$.

يمكن اعتبار كل آلة بوشي آلة مولر. يكفي استبدالها${\textstyle F}$بواسطة${\textstyle \mathbf {F} '}$يتألف من جميع المجموعات الفرعية من${\textstyle Q}$التي تحتوي على عنصر واحد على الأقل من${\textstyle F}$وبالمثل، يمكن اعتبار كل آلة رابين أو ستريت أو آلة التكافؤ بمثابة آلة مولر.

لغة ω التالية${\textstyle L}$على الأبجدية${\textstyle \Sigma =\{0,1\}}$والتي يمكن التعرف عليها بواسطة آلة بوشي غير الحتمية: ${\textstyle L}$يتألف من جميع الكلمات التي تبدأ بـ ω في${\textstyle \سيجما ^{\أوميغا }}$حيث يظهر الرقم 1 عددًا محدودًا من المرات فقط. آلة بوشي غير حتمية تتعرف على${\textstyle L}$لا نحتاج إلا إلى ولايتين${\textstyle q_{0}}$(الحالة الأولية) و${\textstyle q_{1}}$.${\textstyle \Delta }$يتكون من الثلاثيات${\textstyle (q_{0},0,q_{0})}$،${\textstyle (q_{0},1,q_{0})}$،${\textstyle (q_{0},0,q_{1})}$و${\textstyle (q_{1},0,q_{1})}$. ${\textstyle F=\{q_{1}\}}$لأي استفسار أو مساعدة${\textstyle \alpha }$في الحالات التي يظهر فيها الرقم 1 عددًا محدودًا من المرات، يوجد تسلسل يبقى في الحالة${\textstyle q_{0}}$طالما أن هناك 1 للقراءة، وينتقل إلى الولاية${\textstyle q_{1}}$بعد ذلك. هذه العملية ناجحة. إذا كان هناك عدد لا نهائي من الآحاد، فلن يكون هناك سوى عملية واحدة ممكنة: وهي العملية التي تبقى دائمًا في الحالة.${\textstyle q_{0}}$(بمجرد مغادرة الآلة)${\textstyle q_{0}}$ووصل${\textstyle q_{1}}$لا يمكنه العودة. إذا تمت قراءة 1 آخر، فلن تكون هناك حالة لاحقة.

لاحظ أن اللغة المذكورة أعلاه لا يمكن التعرف عليها بواسطة آلة بوشي الحتمية ، والتي تعتبر أقل تعبيرًا من نظيرتها غير الحتمية.

لغة ω على أبجدية منتهية${\textstyle \Sigma }$هي مجموعة من الكلمات ω على${\textstyle \Sigma }$أي أنها مجموعة فرعية من${\textstyle \Sigma ^{\omega }}$لغة ω فوق${\textstyle \Sigma }$يقال إنه يتم التعرف عليه بواسطة آلة أوميغا${\textstyle A}$(بنفس الأبجدية) إذا كانت مجموعة جميع الكلمات ω المقبولة بواسطة${\textstyle A}$. يتم قياس القدرة التعبيرية لفئة من آلات ω من خلال فئة جميع لغات ω التي يمكن التعرف عليها بواسطة آلة ما في تلك الفئة.

تُقرّ جميع آلات الأوتوماتا غير الحتمية من نوع بوشي، والتكافؤ، ورابين، وستريت، ومولر، على التوالي، بنفس فئة لغات ω تمامًا. ^{[ 1 ]} تُعرف هذه اللغات باسم إغلاق ω-كلين للغات المنتظمة أو لغات ω المنتظمة . وباستخدام براهين مختلفة، يمكن أيضًا إثبات أن آلات الأوتوماتا الحتمية من نوع التكافؤ، ورابين، وستريت، ومولر تُقرّ جميعها بلغات ω المنتظمة. ويترتب على ذلك أن فئة لغات ω المنتظمة مغلقة تحت التتميم. ومع ذلك، يُظهر المثال أعلاه أن فئة آلات الأوتوماتا الحتمية من نوع بوشي أضعف من حيث المبدأ.

نظرًا لأن آلات مولر، ورابين، وستريت، والتكافؤ، وبوشي غير الحتمية متساوية في التعبير، فإنه يمكن ترجمتها إلى بعضها البعض. لنستخدم الاختصار التالي.${\displaystyle \{N,D\}\times \{M,R,S,P,B\}}$على سبيل المثال، يرمز NB إلى آلة بوشي ω غير الحتمية، بينما يرمز DP إلى آلة التكافؤ ω الحتمية. وبالتالي، ينطبق ما يلي.

• من الواضح أنه يمكن اعتبار أي آلة حتمية آلة غير حتمية.
• ${\displaystyle NB\rightarrow NR/NS/NP}$دون حدوث انفجار في فضاء الحالة.
• ${\displaystyle NR\rightarrow NB}$مع تضخم متعدد الحدود في فضاء الحالة، أي أن عدد الحالات في NB الناتج هو${\displaystyle 2nm+1}$، أين${\displaystyle n}$يمثل عدد الولايات في منطقة نيو برونزويك و${\displaystyle m}$يمثل عدد أزواج قبول رابين (انظر، على سبيل المثال، ^{[ 2 ]} ).
• ${\displaystyle NS/NM/NP\rightarrow NB}$مع تضخم أُسّي في فضاء الحالة.
• ${\displaystyle NB\rightarrow DR/DP}$مع تضخم أُسّي في فضاء الحالة. تستخدم نتيجة التحديد هذه بناء صفرا .

يمكن الاطلاع على نظرة عامة شاملة للترجمات على المصدر الإلكتروني المشار إليه. ^{[ 3 ]}

يمكن استخدام آلات ω-automata لإثبات قابلية تقرير S1S، وهي نظرية الأعداد الطبيعية أحادية الرتبة من الدرجة الثانية (MSO) في ظل نظام الخلفاء. وتُوسّع آلات الأشجار اللانهائية آلات ω-automata لتشمل الأشجار اللانهائية، ويمكن استخدامها لإثبات قابلية تقرير S2S ، وهي نظرية MSO ذات خلفين، ويمكن تعميم ذلك على نظرية MSO للرسوم البيانية ذات عرض الشجرة المحدود (مع وجود حد ثابت) .

• فاروير، بيرندت (2002)، “ω-Automata”، في جراديل، إريك؛ توماس، وولفغانغ. ويلك ، توماس (محرران)، Automata، Logics، and Infinite Games ، ملاحظات محاضرة في علوم الكمبيوتر ، سبرينغر، الصفحات من 3 إلى 21، ISBN  978-3-540-00388-5.
• بيرين، دومينيك؛ بين، جان إريك (2004)، الكلمات اللانهائية: الأوتوماتا، أنصاف المجموعات، المنطق والألعاب ، إلسيفير ، ISBN 978-0-12-532111-2
• توماس، وولفغانغ (1990)، "الأوتوماتا على الكائنات اللانهائية"، في فان ليوين، يان (محرر)، دليل علوم الحاسوب النظرية، المجلد ب ، مطبعة معهد ماساتشوستس للتكنولوجيا ، الصفحات 133-191 ، ISBN  978-0-262-22039-2
• باخادِر خوسينوف؛ أنيل نيرود (6 ديسمبر 2012). نظرية الأوتوماتا وتطبيقاتها . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-1-4612-0171-7.