💻 computer science

How Concise are Chains of co-Büchi Automata?

यह शोध पत्र को-ब्यूची ऑटोमेटा (co-Büchi automata) की श्रृंखलाओं (COCOA) की संक्षिप्तता का विश्लेषण करता है, यह प्रदर्शित करते हुए कि यद्यपि वे नियतात्मक पैरिटी ऑटोमेटा (deterministic parity automata) की तुलना में घातीय रूप से अधिक संक्षिप्त हो सकते हैं, लेकिन यह लाभ वियोजन (disjunction), संयोजन (conjunction), या पूरकता (complementation) जैसे बुलियन ऑपरेशनों को करने पर समाप्त हो जाता है, जिनके लिए आकार में घातीय वृद्धि आवश्यक होती है।

मूल लेखक: Rüdiger Ehlers

प्रकाशित 2026-03-23

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Rüdiger Ehlers

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप अनंत कहानियों के एक विशाल पुस्तकालय को व्यवस्थित करने की कोशिश कर रहे हैं। कंप्यूटर विज्ञान में, ये "कहानियाँ" घटनाओं के अनंत अनुक्रम (जैसे कि एक रोबोट का कभी न रुकना, या एक नेटवर्क का हमेशा चलते रहना) हैं। यह जाँचने के लिए कि क्या ये कहानियाँ नियमों का पालन करती हैं, हम विशेष मशीनों का उपयोग करते हैं जिन्हें ऑटोमेटा (Automata) कहा जाता है।

इन कहानियों को व्यवस्थित करने के लिए लंबे समय तक मानक मशीन डिटरमिनिस्टिक पैरिटी ऑटोमेटा (DPW) रही है। एक DPW को एक बहुत ही सख्त, एक ही कतार में चलने वाले लाइब्रेरियन (पुस्तकालयाध्यक्ष) के रूप में सोचें। यह एक कहानी पढ़ता है और इस आधार पर उसे एक "रंग" (संख्या) देता है कि कहानी कैसे समाप्त होती है। यदि अनंत काल तक दिखने वाला सबसे निचला रंग एक सम (even) संख्या है, तो कहानी "अच्छी" (स्वीकृत) मानी जाती है। यदि वह विषम (odd) संख्या है, तो कहानी "खराब" (अस्वीकृत) मानी जाती है।

हालाँकि, ये लाइब्रेरियन बहुत बड़े हो सकते हैं। कभी-कभी, एक सरल नियम का वर्णन करने के लिए, आपको एक गगनचुंबी इमारत के आकार की लाइब्रेरी की आवश्यकता होती है।

COCOA से मिलिए: "विशेषज्ञों की एक श्रृंखला"

कुछ साल पहले, शोधकर्ताओं ने इन कहानियों को व्यवस्थित करने का एक नया तरीका खोजा जिसे चेन्स ऑफ को-बुची ऑटोमेटा (COCOA) कहा जाता है।

एक एकल विशाल लाइब्रेरियन के बजाय, एक विशेषज्ञों की श्रृंखला की कल्पना करें जो एक पंक्ति में खड़े हैं।

विशेषज्ञ #1 कहानी को देखता है। यदि उसे यह पसंद आती है, तो वह इसे एक "गोल्ड" (स्वर्ण) टिकट देता है।
यदि विशेषज्ञ #1 इसे अस्वीकार कर देता है, तो विशेषज्ञ #2 इसे देखता है। यदि उसे यह पसंद आती है, तो वह "सिल्वर" (रजत) टिकट देता है।
यदि विशेषज्ञ #2 इसे अस्वीकार कर देता है, तो विशेषज्ञ #3 देखता है, और इसी तरह आगे भी।

कहानी का अंतिम "रंग" श्रृंखला में मौजूद पहले विशेषज्ञ द्वारा निर्धारित किया जाता है जो उसे स्वीकार करता है। यदि कोई भी इसे स्वीकार नहीं करता है, तो इसे "ब्लैक" (काला) टिकट मिलता है।

बड़ी प्रतिज्ञा: पेपर कहता है कि यह चेन सिस्टम अद्भुत है क्योंकि:

आप मशीनों को बहुत छोटा बना सकते हैं (पॉलीनोमियल टाइम मिनिमाइजेशन)।
वे पुराने सिंगल-लाइब्रेरियन सिस्टम की तुलना में बहुत अधिक संक्षिप्त रूप में जटिल नियमों का प्रतिनिधित्व कर सकते हैं।

तीन बड़े आश्चर्य (लेकिन...)

इस पेपर के लेखक, रुडिगर एहलर्स (Rüdiger Ehlers) ने पूछा: "ठीक है, COCOA छोटा और कुशल है। लेकिन क्या यह बहुत नाजुक है? क्या होगा यदि हम इन कहानियों को आपस में मिलाने की कोशिश करें (जैसे दो नियमों को मिलाना) या नियमों को उलट दें (जैसे 'खराब' को 'अच्छा' बनाना)?"

यहाँ तीन मुख्य निष्कर्ष दिए गए, जिन्हें उपमाओं के साथ समझाया गया है:

1. आकार का "जादुई चमत्कार" (COCOA बनाम DPW)

निष्कर्ष: COCOA, पुराने DPW की तुलना में घातांकीय (exponentially) रूप से छोटा हो सकता है, भले ही श्रृंखला में व्यक्तिगत विशेषज्ञ बहुत सरल हों।
उपमा: कल्पना कीजिए कि आपको एक नियम बताना है: "कहानी अच्छी है यदि इसमें 'X' की संख्या सम है या 'Y' की संख्या सम है।"

पुराना तरीका (DPW): आपको एक विशाल मशीन की आवश्यकता होगी जिसमें X और Y के हर संभावित संयोजन के लिए एक अलग कमरा हो। यदि आपके पास 10 प्रकार के अक्षर हैं, तो आपको 1,000 से अधिक कमरों की आवश्यकता होगी।
COCOA का तरीका: आप 10 छोटे विशेषज्ञों की एक श्रृंखला का उपयोग करते हैं। प्रत्येक एक केवल यह जाँचता है कि क्या एक विशिष्ट अक्षर कितनी बार सम संख्या में आता है। वे कहानी को लाइन में आगे बढ़ाते हैं।
परिणाम: श्रृंखला छोटी है (10 छोटे कमरे), जबकि पुरानी मशीन एक हवेली है। पेपर यह सिद्ध करता है कि यह केवल इसलिए नहीं है क्योंकि विशेषज्ञ "स्मार्ट" (हिस्ट्री-डिटरमिनिस्टिक) हैं, बल्कि इसलिए है क्योंकि चेन की संरचना स्वयं स्थान बचाने का एक जादुई तरीका है।

2. "जिग्सॉ पज़ल" की समस्या (नियमों को मिलाना)

निष्कर्ष: यदि आप दो COCOA श्रृंखलाओं को मिलाते हैं (जैसे "कहानी A AND कहानी B"), तो परिणाम का आकार विस्फोट के साथ बहुत बड़ा हो सकता है, जो घातांकीय रूप से विशाल हो जाता है।
उपमा: कल्पना कीजिए कि आपके पास दो सघन, मुड़े हुए ओरिगामी क्रेन (COCOA) हैं।

पुराना तरीका (DPW): यदि आपके पास दो बड़े, अनफोल्ड किए गए कागज़ के मानचित्र (DPW) हैं और आप उन्हें मिलाना चाहते हैं, तो आप उन्हें बस आपस में चिपका देते हैं। यह थोड़ा बड़ा होता है, लेकिन प्रबंधनीय है।
COCOA का तरीका: इन दो मुड़े हुए क्रेनों को मिलाने के लिए, आपको दोनों को पूरी तरह से खोलना होगा ताकि उनके आंतरिक स्तरों के बीच की परस्पर क्रिया को देखा जा सके, और फिर उन्हें एक नए, विशाल आकार में फिर से मोड़ना होगा।
परिणाम: भले ही इनपुट श्रृंखलाएं छोटी थीं, आउटपुट श्रृंखला एक गगनचुंबी इमारत बन जाती है। पेपर दिखाता है कि कुछ नियमों के लिए, दो छोटी COCOA श्रृंखलाओं को मिलाने से आपको एक ऐसी मशीन बनानी पड़ती है जिसमें $2^k$ स्टेट्स (जहाँ $k$ इनपुट का आकार है) होते हैं। यह ऐसा है जैसे दो छोटी, कुशल टीमों को एक बड़े प्रोजेक्ट में विलय करने की कोशिश करना, और अचानक संचार प्रबंधन के लिए आपको एक पूरी नई सेना की आवश्यकता होती है।

3. "दर्पण" की समस्या (नियमों को पूरक बनाना/उलटना)

निष्कर्ष: यदि आप एक COCOA को उलटना चाहते हैं ( "अच्छा" को "खराब" और इसके विपरीत बदलना), तो मशीन का आकार भी बढ़ सकता है।
उपमा:

पुराना तरीका (DPW): नियम को उलटना आसान है। आप बस धूप का चश्मा पहन लेते हैं जो रंगों को उल्टा कर देता है। यदि लाइब्रेरियन ने "लाल" कहा था, तो अब वह "नीला" कहेगा। मशीन का आकार वही रहता है।
COCOA का तरीका: एक श्रृंखला को उलटना एक जटिल रूब गोल्डबर्ग मशीन (Rube Goldberg machine) को उलटने जैसा है। विशेषज्ञ विशिष्ट पैटर्न को पकड़ने के लिए व्यवस्थित किए गए थे। जब आप लक्ष्य को उलट देते हैं, तो पैटर्न इतने नाटकीय रूप से बदल जाते हैं कि नई श्रृंखला के पहले विशेषज्ञ को वह सब कुछ याद रखना पड़ता है जो पुरानी पूरी श्रृंखला जानती थी।
परिणाम: नए पहले विशेषज्ञ को $2^k$ विभिन्न संभावनाओं को याद रखने की आवश्यकता होती है। संक्षिप्त श्रृंखला बिखर जाती है, और अंततः आप फिर से एक विशाल मशीन के साथ समाप्त होते हैं।

यह क्यों मायने रखता है?

यह पेपर कंप्यूटर वैज्ञानिकों के लिए एक "रियलिटी चेक" है।

अच्छी खबर: COCOA जटिल नियमों को स्टोर करने और न्यूनतम (minimize) करने का एक शानदार, संक्षिप्त तरीका है। यह शुरुआती डिज़ाइन के लिए बेहतरीन है।
खराब खबर: यदि आप इन नियमों पर भारी गणितीय गणना करने की योजना बना रहे हैं (उन्हें मिलाना या उलटना), तो COCOA आपकी दक्षता को तोड़ सकता है। "संक्षिप्तता" नाजुक है।

निष्कर्ष: COCOA एक अत्यंत कुशल, संपीड़ित फ़ाइल प्रारूप (जैसे कि ZIP फ़ाइल) की तरह है। यह भंडारण के लिए छोटा और बढ़िया है। लेकिन यदि आप बिना अनज़िप किए सीधे ZIP फ़ाइल की सामग्री को संपादित करने की कोशिश करते हैं, तो उस प्रक्रिया के लिए पूरी चीज़ को अनपैक करने की आवश्यकता हो सकती है, जिससे वह फिर से विशाल हो जाएगी। यह पेपर हमें बताता है कि यह "अनपैकिंग" कब और क्यों होती है, जिससे इंजीनियरों को यह तय करने में मदद मिलती है कि उन्हें COCOA का उपयोग कब करना चाहिए और कब पुराने, अधिक मजबूत (लेकिन बड़े) तरीकों पर टिके रहना चाहिए।

यहाँ रूडिगर एहलर्स के शोध पत्र "How Concise Are Chains of Co-Büchi Automata?" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण (Problem Statement)

यह शोध पत्र $\omega$ -रेगुलर भाषाओं के एक कैनोनिकल मॉडल के रूप में Chains of Co-Büchi Automata (COCOA) की संक्षिप्तता (state complexity) की जांच करता है।

संदर्भ: COCOA को हाल ही में $\omega$ -रेगुलर भाषाओं के प्रतिनिधित्व के लिए Deterministic Parity Automata (DPW) के एक विकल्प के रूप में पेश किया गया है। COCOA का एक प्रमुख लाभ यह है कि उन्हें पॉलिनोमियल समय (polynomial time) में मिनिमाइज (minimize) किया जा सकता है, जबकि DPWs को मिनिमाइज करना NP-hard है।
अंतराल (The Gap): हालांकि यह ज्ञात है कि DPWs को COCOA में कैसे अनुवादित किया जाता है, लेकिन आकार (संक्षिप्तता) के संबंध में दोनों मॉडलों के बीच का संबंध पूरी तरह से स्पष्ट नहीं है। विशेष रूप से, यह स्पष्ट नहीं है कि:
1. COCOAs, DPWs की तुलना में कितने अधिक संक्षिप्त हो सकते हैं।
2. क्या COCOA पर किए जाने वाले बूलियन ऑपरेशन्स (conjunction, disjunction, complementation) के दौरान यह संक्षिप्तता बनी रहती है।
लक्ष्य: लेखक का लक्ष्य COCOA और DPW के बीच आकार के ट्रेड-ऑफ (size trade-offs) को स्पष्ट करना और COCOA पर मानक भाषा संचालन (language operations) की जटिलता को निर्धारित करना है।

2. कार्यप्रणाली (Methodology)

लेखक सैद्धांतिक ऑटोमेटा निर्माण और जटिलता विश्लेषण (complexity analysis) के संयोजन का उपयोग करता है:

कैनोनिकल डिकंपोजिशन (Canonical Decomposition): शोध पत्र COCOA की परिभाषा का उपयोग करता है, जहाँ एक $\omega$ -रेगुलर भाषा $L$ को को-बुची (co-Büchi) भाषाओं की एक श्रृंखला $L_1 \supset L_2 \supset \dots \supset L_n$ में विभाजित किया जाता है। एक शब्द का "प्राकृतिक रंग" (natural color) यह निर्धारित करता है कि वह श्रृंखला के किस स्तर पर आता है।
भाषाओं के परिवार का निर्माण (Family of Languages Construction): लोअर बाउंड्स (lower bounds) सिद्ध करने के लिए, लेखक एक पूर्णांक $k$ द्वारा पैरामीटराइज्ड विशिष्ट भाषा परिवारों ( $L_k$ , $\hat{L}_k$ , और उनके इंटरसेक्शन/कॉम्प्लीमेंट) का निर्माण करता है।
रेसिड्यूअल लैंग्वेज विश्लेषण (Residual Language Analysis): एक मुख्य तकनीक विशिष्ट भाषाओं को दर्शाने के लिए आवश्यक रेसिड्यूअल भाषाओं (Myhill-Nerode equivalence classes) की संख्या का विश्लेषण करना है। चूँकि न्यूनतम नियतात्मक (deterministic) और हिस्ट्री-डिटरमिनिस्टिक (history-deterministic) ऑटोमेटा को सभी रेसिड्यूअल भाषाओं के बीच अंतर करना चाहिए, इसलिए रेसिड्यूअल भाषाओं की संख्या अवस्थाओं (states) की संख्या के लिए एक निचली सीमा (lower bound) प्रदान करती है।
तुलनात्मक निर्माण (Comparative Construction): यह पेपर समान भाषाओं के लिए न्यूनतम DPWs और न्यूनतम COCOAs का निर्माण करता है ताकि उनके स्टेट काउंट की सीधे तुलना की जा सके।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

शोध पत्र तीन मुख्य तकनीकी परिणाम प्रस्तुत करता है जो COCOA की संक्षिप्तता की सीमाओं को परिभाषित करते हैं:

परिणाम 1: DPW पर COCOA की घातांकीय संक्षिप्तता (Exponential Concisenity of COCOA over DPW)

निष्कर्ष: COCOA, Deterministic Parity Automata (DPW) की तुलना में घातांकीय रूप से अधिक संक्षिप्त (exponentially more concise) हो सकते हैं, भले ही श्रृंखला में व्यक्तिगत को-बुची ऑटोमेटा नियतात्मक (deterministic) (केवल हिस्ट्री-डिटरमिनिस्टिक नहीं) हों।
महत्व: पिछले परिणामों ने दिखाया था कि COCOA हिस्ट्री-डिटरमिनिस्टिक (HD) ऑटोमेटा के उपयोग के कारण छोटे हो सकते हैं, जो नियतात्मक की तुलना में घातांकीय रूप से छोटे होते हैं। यह परिणाम सिद्ध करता है कि श्रृंखला संरचना स्वयं संक्षिप्तता में योगदान देती है।
उदाहरण: लेखक $C_k$ नामक भाषाओं के एक परिवार को परिभाषित करता है जहाँ प्रत्येक COCOA स्तर को केवल 2 अवस्थाओं (deterministic) की आवश्यकता होती है, फिर भी इसके समकक्ष किसी भी DPW को $2^k$ अवस्थाओं की आवश्यकता होती है। यह उन भाषाओं के लिए भी सत्य है जिनमें केवल एक ही रेसिड्यूअल भाषा है।

परिणाम 2: बाइनरी बूलियन ऑपरेशन्स में घातांकीय उछाल (Exponential Blow-up in Binary Boolean Operations)

निष्कर्ष: COCOA पर संयोजन (conjunction/intersection) या वियोजन (disjunction/union) करने से परिणामी ऑटोमेटा के आकार में घातांकीय उछाल (exponential blow-up) आ सकता है।
विपरीत स्थिति: DPWs के लिए, संयोजन और वियोजन अक्सर केवल पॉलिनोमियल उछाल के साथ किए जा सकते हैं (या कम से कम, यहाँ निर्मित विशिष्ट परिवार DPWs के लिए घातांकीय उछाल की आवश्यकता नहीं रखते हैं)।
तंत्र (Mechanism): उछाल इसलिए होता है क्योंकि परिणामी COCOA में "प्राकृतिक रंग" का असाइनमेंट श्रृंखला के स्तरों के पुनर्गठन की मांग करता है। दो COCOA श्रृंखलाओं का प्रतिच्छेदन (intersection) (प्रत्येक $k$ स्तरों वाली) $k \times k$ संयोजनों का एक ग्रिड बनाता है जिसे एक नई श्रृंखला में समाहित (collapse) करना आवश्यक होता है। लेखक सिद्ध करता है कि विशिष्ट भाषा परिवारों के लिए, परिणामी COCOA को $2^k$ अवस्थाओं की आवश्यकता होती है, जबकि उसी ऑपरेशन के DPW प्रतिनिधित्व का आकार इनपुट के सापेक्ष पॉलिनोमियल रहता है।

परिणाम 3: कॉम्प्लीमेंटेशन में घातांकीय उछाल (Exponential Blow-up in Complementation)

निष्कर्ष: एक COCOA का कॉम्प्लीमेंट (complementation) करने के लिए भी अत्यंत मामलों (worst case) में घातांकीय उछाल की आवश्यकता हो सकती है।
विपरीत स्थिति: DPWs के लिए, कॉम्प्लीमेंटेशन सरल है (ट्रांजिशन रंगों में 1 जोड़ना) और इसमें आकार में कोई वृद्धि नहीं होती है।
तंत्र: एक COCOA में, मूल भाषा में समान प्राकृतिक रंग वाले शब्दों को कॉम्प्लीमेंटेड भाषा में अलग-अलग प्राकृतिक रंगों के असाइनमेंट की आवश्यकता हो सकती है। कॉम्प्लीमेंटेड श्रृंखला में इन शब्दों के बीच अंतर करने के लिए, पहली ऑटोमेटा को $2^k$ रेसिड्यूअल भाषाओं को ट्रैक करने के लिए एक घातांकीय संख्या में अवस्थाओं की आवश्यकता होती है, जिससे इसकी संक्षिप्तता नष्ट हो जाती है।

4. प्रमाणों का तकनीकी विवरण (Technical Details of the Proofs)

"रेसिड्यूअल लैंग्वेज" तर्क: प्रमाण मुख्य रूप से इस तथ्य पर निर्भर करते हैं कि न्यूनतम HD-tCBW (History-Deterministic transition-based Co-Büchi Word) ऑटोमेटा अर्थतः (semantically) नियतात्मक होते हैं। इसलिए, एक न्यूनतम ऑटोमेटा में अवस्थाओं की संख्या अलग-अलग रेसिड्यूअल भाषाओं की संख्या द्वारा निम्न-बद्ध (lower-bounded) होती है।
$L_k$ का निर्माण: लेखक विशिष्ट प्रतीकों ( $X_i, Y_i$ $X_{i}, Y_{i}$ ) की गणना की पैरिटी (parity) और शब्द के सफिक्स (suffix) के आधार पर भाषाओं को परिभाषित करता है।
- $L_k$ में $O(k)$ आकार का COCOA है लेकिन $2^k$ रेसिड्यूअल भाषाएँ हैं।
- $L_k \cap \hat{L}_k$ COCOA को सभी $2^k$ पैरिटी संयोजनों के बीच अंतर करने के लिए मजबूर करता है, जिससे घातांकीय अवस्था आवश्यकता उत्पन्न होती है।
SCC नेस्टिंग: DPW लोअर बाउंड के लिए, लेखक स्ट्रॉन्गली कनेक्टेड कंपोनेंट्स (SCC) का विश्लेषण करता है और दिखाता है कि COCOA श्रृंखला की नेस्टेड स्वीकृति शर्तों (nested acceptance conditions) को सही ढंग से सिम्युलेट करने के लिए, एक DPW को अवस्थाओं को घातांकीय रूप से "नेस्ट" (nest) करना होगा।

5. महत्व और निहितार्थ (Significance and Implications)

सैद्धांतिक सीमाएँ: यह शोध पत्र स्थापित करता है कि यद्यपि COCOA एक शक्तिशाली, पॉलिनोमियल-टाइम मिनिमाइजेबल कैनोनिकल रूप प्रदान करते हैं, वे बूलियन ऑपरेशन्स के प्रति नाजुक (brittle) हैं। "संक्षिप्तता" मजबूत नहीं है; इसे भाषाओं को मिलाने पर आसानी से खोया जा सकता है।
एल्गोरिदम डिज़ाइन: ये परिणाम COCOA पर बूलियन ऑपरेशन करने का प्रयास करने वाले किसी भी भविष्य के एल्गोरिदम के लिए लोअर बाउंड्स प्रदान करते हैं। ऐसे किसी भी एल्गोरिदम को स्वाभाविक रूप से सबसे खराब स्थिति में घातांकीय वृद्धि को संभालना होगा।
भविष्य की दिशाएँ: निष्कर्ष बताते हैं कि उन अनुप्रयोगों के लिए जहाँ बार-बार बूलियन ऑपरेशन्स की आवश्यकता होती है (जैसे कम्पोजिशनल वेरिफिकेशन या सिंथेसिस), COCOA इष्टतम प्रतिनिधित्व नहीं हो सकते, भले ही उनके पास मिनिमाइजेशन के लाभ हों। यह शोध पत्र उन वैकल्पिक मॉडलों की खोज को प्रेरित करता जो पॉलिनोमियल-टाइम मिनिमाइजेशन बनाए रखते हुए भी उस घातांकीय रेसिड्यूअल भाषा विस्फोट से बच सकें जो ऑपरेशन्स के दौरान होता है।
व्यावहारिक प्रभाव: रिएक्टिव सिंथेसिस (reactive synthesis) के लिए, जहाँ CO-COA का उपयोग DPWs को बदलने के लिए किया जाता है, अभ्यासकर्ताओं को यह ध्यान रखना चाहिए कि स्पेसिफिकेशन को संयोजित करना (जैसे $Spec_1 \land Spec_2$ ) एक ऐसा ऑटोमेटा बना सकता है जो अपने भागों के योग की तुलना में काफी बड़ा हो, जिससे COCOA का उपयोग करने के लाभ समाप्त हो सकते हैं।

संक्षेप में, यह शोध पत्र प्रदर्शित करता है कि COCOA एक "दोधारी तलवार" हैं: वे विशिष्ट भाषाओं के लिए एक अनूठा मार्ग प्रदान करते हैं जो पॉलिनोमियल-टाइम मिनिमाइजेशन और DPWs की तुलना में घातांकीय रूप से छोटे हो सकते हैं, लेकिन उनकी यह संक्षिप्तता नाजुक है और मानक बूलियन ऑपरेशन्स तथा कॉम्प्लीमेंटेशन के तहत विफल हो जाती है।