The memory of $\omega$-regular and BC($\Sigma_2^0$) objectives

तकनीकी सारांश: $\omega$-रेगुलर और $BC(\Sigma^0_2)$ उद्देश्यों की स्मृति (Memory)

समस्या विवरण
(संभावित रूप से अनंत) ग्राफ पर 2-खिलाड़ी शून्य-योग (zero-sum) अनंत अवधि वाले खेलों के संदर्भ में, एक उद्देश्य $W$ की स्मृति (memory) को एक न्यूनतम पूर्णांक $k$ के रूप में परिभाषित किया गया है, जिससे यह सुनिश्चित होता है कि किसी भी ऐसे खेल में जहाँ ईव (Eve) के पास जीतने की रणनीति है, उसके पास अधिकतम $k$ मेमोरी अवस्थाओं (memory states) वाले परिमित ऑटोमेटा द्वारा कार्यान्वित की जाने वाली एक जीतने वाली रणनीति है। जबकि $\omega$-रेगुलर उद्देश्यों के लिए स्थितिगतता (positionality, स्मृति $k=1$) की निर्णायकता (decidability) को हाल ही में स्थापित किया गया था, $\omega$-रेगुलर उद्देश्यों की स्मृति को निर्धारित करने की सामान्य समस्या खुली रह गई थी। विशेष रूप से, यह अज्ञात था कि क्या स्मृति का कंप्यूटिंग निर्णायक है, और यह भी ज्ञात नहीं था कि क्या परिमित गेम ग्राफ पर आवश्यक स्मृति, अनिश्चित ग्राफों पर आवश्यक स्मृति के समान है। इसके अलावा, स्मृति की आवश्यकता वाले उद्देश्यों के संघ (union) के तहत व्यवहार (Generalised Kopczyński's conjecture) एक खुला प्रश्न था।

कार्यप्रणाली
लेखक $k$-wise $\varepsilon$-completable automata पर आधारित स्मृति $\le k$ वाले उद्देश्यों का एक नया लक्षण वर्णन प्रस्तुत करते हैं। यह दृष्टिकोण स्थितिगतता (positionality) के लिए उपयोग किए जाने वाले यूनिवर्सल ग्राफ और $\varepsilon$-completable automata की अवधारणा को परिमित स्मृति के परिवेश में विस्तारित करता है।

1. $k$-wise $\varepsilon$-completable Automata: एक ऑटोमेटा $k$-wise $\varepsilon$-complete है यदि उसके राज्यों (जो $k$ मेमोरी श्रृंखलाओं में विभाजित हैं) को $\varepsilon$-ट्रांज़िशन के साथ बढ़ाया जा सकता है ताकि एक ऐसी संरचना बनाई जा सके जहाँ, प्रत्येक सम प्राथमिकता (even priority) $x$ और मेमोरी अवस्था $m$ के लिए, अवस्थाएँ जो मेमोरी $m$ के साथ हैं, पूर्णतः पूर्वक्रमित (totally preordered) हों। विशेष रूप रूप से, किसी भी जोड़ी $(q, m)$ और $(q', m)$ के लिए, या तो $q$ से $q'$ तक प्राथमिकता $x$ के साथ एक $\varepsilon$-ट्रांज़िशन है, या $q'$ से $q$ तक प्राथमिकता $x+1$ के साथ एक ट्रांज़िशन है।
2. एक्सट्रैक्शन लेम्मा (Extraction Lemmas): मुख्य तकनीकी नवाचार अनंत या बड़े परिमित ग्राफों से सजातीय उप-संरचनाओं (homogeneous substructures) को निकालना है।
   • अनंत मामले के लिए (अनुभाग 3.1): लेखक यूनिवर्सल ग्राफ $S_\kappa^d$ (जहाँ $\kappa = 2^{\aleph_0}$) से "सर्वत्र कोफिनल" (everywhere cofinal) पेड़ों को निकालने के लिए एक कॉम्बिनेटोरियल लेम्मा (लेम्मा 12) का उपयोग करते हैं, जो यह सुनिश्चित करता है कि स्तरों के बीच डोमिनेशन संबंध समान हैं।
   • परिमित मामले के लिए (अनुभाग 3.2): वे परिमित ऑटोमेटा के लिए इन एक्सट्रैक्शन तकनीकों को अनुकूलित करते हैं, जिसमें परिमित ब्रांचिंग को संभालने और एक $k$-blowup के अस्तित्व को सुनिश्चित करने के लिए "नियमित शब्दों" (regular words) और सिंक्रोनाइज्ड सबवर्ड्स (लेम्मा 24) का उपयोग किया जाता है।
3. कैस्केड उत्पाद (Cascade Products): प्रमाण अत्यधिक रूप से एक यूनिवर्सल ग्राफ (या सिग्नेचर ट्री) के साथ एक नियत (deterministic) ऑटोमेटा के कैस्केड उत्पाद पर निर्भर करते हैं, जो सभी संभावित स्वीकार्य व्यवहारों को एनकोड करता है, और उसके बाद भाषा को संरक्षित करते हुए और $\varepsilon$-पूर्णता की स्थिति को संतुष्ट करते हुए एक $k$-blowup का निर्माण किया जाता है।

प्रमुख योगदान और परिणाम

1. लक्षण वर्णन प्रमेय (Theorem 7): यह शोध पत्र $BC(\Sigma^0_2)$ उद्देश्य (जिसे संभावित रूप से अनंत नियत पैरिटी ऑटोमेटा द्वारा पहचाना जाता है) के लिए स्मृति $\le k$ होने के लिए एक आवश्यक और पर्याप्त शर्त स्थापित करता है। निम्नलिखित तुल्य हैं:

   • उद्देश्य का आकार $\le 2^{2^{\aleph_0}}$ के खेलों पर स्मृति $\le k$ है।
   • उद्देश्य को पहचानने वाला प्रत्येक ऑटोमेटा एक $k$-blowup को स्वीकार करता है जो $k$-wise $\varepsilon$-complete है।
   • एक नियत $k$-ऑटोमेटा मौजूद है जो $k$-wise $\varepsilon$-completable है और उद्देश्य को पहचानता है।
   • प्रत्येक कार्डीनल $\kappa$ के लिए, एक $(\kappa, W)$-यूनिवर्सल ग्राफ मौजूद है जो वेल-फाउंडेड (well-founded) और $k$-wise $\varepsilon$-complete है।
   • उद्देश्य की मनमाने खेलों पर स्मृति $\le k$ है।

2. NP में निर्णायकता (Corollary 9): $\omega$-रेगुलर उद्देश्यों (परिमित ऑटोमेटा) के लिए, स्मृति (और क्रोमैटिक स्मृति) को NP में कंप्यूट किया जा सकता है। एल्गोरिदम एक संभावित स्मृति आकार $k$, एक आकार $\le kn$ का नियत ऑटोमेटा, और एक $\varepsilon$-पूर्णता का अनुमान लगाता है, और फिर बहुपद समय (polynomial time) में भाषा समावेशन को सत्यापित करता है। इस कार्य से पहले, ओपन $\omega$-रेगुलर उद्देश्यों के लिए स्मृति की निर्णायकता अज्ञात थी।

3. परिमित-से-अनंत लिफ्ट (Corollary 8): यह शोध पत्र सिद्ध करता है कि $\omega$-रेगुलर उद्देश्यों के लिए, परिमित गेम ग्राफों पर आवश्यक स्मृति, मनमाने (अनंत) गेम ग्राफों पर आवश्यक स्मृति के समान है। यह Vandenhove के $\omega$-रेगुलर मामले के लिए एक अनुमान को हल करता है।

4. संघ के तहत क्लोजर (Theorem 10): लेखक $BC(\Sigma^0_2)$ उद्देश्यों के लिए जनरललाइज्ड कोपज़िंस्की अनुमान (Generalised Kopczyński's conjecture) का एक मजबूत रूप सिद्ध करते हैं। यदि $W_1$ और $W_2$ क्रमशः $k_1$ और $k_2$ स्मृति वाले उद्देश्य हैं, और $W_2$ प्रीफिक्स-बढ़ाने वाला (prefix-increasing) है, तो $W_1 \cup W_2$ की स्मृति अधिकतम $k_1 \cdot k_2$ है। यह सीमा सटीक (tight) है।

5. क्रोमैटिक स्मृति (Chromatic Memory): सभी परिणाम क्रोमैटिक स्मृति पर समान रूप से लागू होते हैं, जहाँ रणनीतियाँ केवल देखे गए किनारे (edge) के बजाय देखे गए किनारे के रंग के आधार पर अपनी मेमोरी अवस्था को अपडेट कर सकती हैं।

महत्व और दावे
यह शोध पत्र $\omega$-रेगुलर उद्देश्यों के लिए (क्रोमैटिक) स्मृति का पहला ज्ञात लक्षण वर्णन प्रदान करने का दावा करता है, जो पहले के प्रतिबंधित वर्गों (जैसे मुलर या क्लोज्ड उद्देश्यों) से आगे बढ़ता है। यह स्थापित करके कि स्मृति कंप्यूटेशन NP में है, यह समस्या को एक खुली निर्णायकता प्रश्न से एक सुलभ जटिलता वर्ग (tractable complexity class) में बदल देता है। लेखक जोर देते हैं कि उनकी प्रमाण तकनीकें, जिनमें अनंत ग्राफों से संरचनाओं को निकालना और ऑर्डिनल नंबरों का हेरफेर करना शामिल है, स्थितिगतता (positionality) पर पिछले कार्यों (जो क्रमिक ऑटोमेटा रूपांतरणों पर निर्भर थे) से भिन्न और उल्लेखनीय रूप से छोटी हैं।

परिणाम स्मृति विश्लेषण के दायरे को व्यापक $BC(\Sigma^0_2)$ भाषाओं तक विस्तारित करते हैं, जिसमें गैर-$\omega$-रेगुलर उद्देश्य जैसे ऊर्जा (energy) और मीन-पेऑफ (mean-payoff) खेल, और $\omega$-ट्यूरिंग मशीनों द्वारा पहचाने जाने वाले भाषाएँ शामिल हैं। शोध पत्र स्पष्ट रूप से नोट करता है कि जबकि यह $\omega$-रेगुलर उद्देश्यों के लिए 'परिमित-से-अनंत लिफ्ट' को पुनः प्राप्त करता है, यह स्मृति $k > 1$ के लिए '1-से-2-प्लेयर लिफ्ट' (असममित लिफ्ट) को पुनः प्राप्त नहीं करता है, क्योंकि इसके प्रति-उदाहरण मौजूद हैं।

सीमाएँ और खुले प्रश्न
लेखक स्वीकार करते हैं कि जहाँ वे NP में निर्णायकता स्थापित करते हैं, वहीं सटीक जटिलता (विशेष रूप से क्या यह P में है) अभी भी खुला है। वे यह भी नोट करते हैं कि उनकी विधियाँ वर्तमान में एक्सट्रैक्शन लेम्मा की कठिनाइयों के कारण $\Delta^0_3$ वर्ग तक विस्तारित नहीं होती हैं। यह प्रश्न कि क्या $\omega$-रेगुलर उद्देश्यों में क्रोमैटिक स्मृति के लिए एक असममित लिफ्ट मौजूद है, अभी भी खुला है।