💻 computer science

The complexity of downward closures of indexed languages

यह शोध पत्र इंडेक्स्ड भाषाओं के लिए डाउनवर्ड क्लोजर (downward closures) की गणना करने की जटिलता के संबंध में खुले प्रश्न को हल करता है, जो गैर-नियतात्मक (non-deterministic) और नियतात्मक (deterministic) ऑटोमेटा के लिए क्रमशः त्रि-घातीय (triply) और चतुर्घातीय (quadruply) ऊपरी सीमाओं को स्थापित करते हुए, साथ ही मिलान योग्य निचली सीमाओं को भी स्थापित करता है, जिसे सेमीग्रुप-आधारित शब्द सारांशों (semigroup-based word summaries) का उपयोग करके इंडेक्स्ड व्याकरणों को कॉन्टेक्स्ट-फ्री व्याकरणों में बदलने की एक नवीन पद्धति के माध्यम से प्राप्त किया गया है।

मूल लेखक: Richard Mandel, Corto Mascle, Georg Zetzsche

प्रकाशित 2026-05-28

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

CC BY 4.0

मूल लेखक: Richard Mandel, Corto Mascle, Georg Zetzsche

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

कल्पना कीजिए कि आपके पास कहानियों का एक विशाल, अनंत रूप से जटिल पुस्तकालय है। कुछ कहानियाँ छोटी हैं, कुछ लाखों पन्नों लंबी हैं, और कुछ के नियम इतने जटिल हैं कि एक सामान्य कंप्यूटर उन्हें पढ़ भी नहीं सकता। कंप्यूटर विज्ञान की दुनिया में, इन कहानियों को इंडेक्स्ड लैंग्वेजेस (Indexed Languages) कहा जाता है। ये मानक "कॉन्टेक्स्ट-फ्री" भाषाओं (जो प्रोग्रामिंग कोड के सिंटैक्स को संचालित करती हैं) का एक सुपर-चार्ज्ड संस्करण हैं, लेकिन इनमें जटिलता की एक अतिरिक्त परत है: "स्टैक्स का स्टैक" (a stack of stacks)।

एक सामान्य स्टैक (stack) एक प्लेटों के ढेर की तरह है। आप एक प्लेट जोड़ सकते हैं या उसे हटा सकते हैं। एक इंडेक्स्ड लैंग्वेज प्लेटों के पूरे टावरों के ढेर की तरह है। आप एक पूरा टावर जोड़ सकते हैं, या एक पूरा टावर हटा सकते हैं। यह सिस्टम को अविश्वसनीय रूप से शक्तिशाली बनाता है लेकिन इसे विश्लेषण करना भी बेहद कठिन बना देता है।

समस्या: "डाउनवर्ड क्लोजर" (The Downward Closure)

इस शोध पत्र के लेखक इन विशाल पुस्तकालयों को सरल बनाने के एक विशिष्ट तरीके में रुचि रखते हैं। वे इसे डाउनवर्ड क्लोजर कहते हैं।

कल्पना कीजिए कि आपके पास एक बहुत लंबा वाक्य है: "The quick brown fox jumps over the lazy dog."
इस वाक्य का "डाउनवर्ड क्लोजर" उन सभी संभावित छोटे वाक्यों का संग्रह है जिन्हें आप अक्षरों को हटाकर बना सकते हैं, लेकिन क्रम को बनाए रखते हुए।

"The fox jumps" इसके क्लोजर में है।
"Quick dog" इसके क्लोजर में है।
"Dog quick" इसमें नहीं है (क्योंकि क्रम बदल गया है)।

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

बड़ा सवाल: हम जानते थे कि हम इन जटिल इंडेक्स्ड लैंग्वेजेस को सरल सूचियों में बदल सकते हैं, लेकिन हमें यह नहीं पता था कि वह सूची कितनी बड़ी होगी। क्या वह एक फोन बुक के आकार की सूची होगी? इंटरनेट के आकार की? या इतनी बड़ी सूची जिसे लिखने में ब्रह्मांड की आयु से भी अधिक समय लगेगा?

खोज: एक ट्रिपल-एक्सपोनेंशियल विस्फोट (A Triple-Exponential Explosion)

लेखकों ने अंततः इस रहस्य को सुलझा लिया है। उन्होंने सिद्ध किया कि एक इंडेक्स्ड लैंग्वेज को उसके सरल डाउनवर्ड क्लोजर में बदलने के लिए, परिणामी मशीन का आकार ट्रिपल-एक्सपोनेंशियल (triply exponential) हो सकता है।

आइए समझते हैं कि "ट्रिपल-एक्सपोनेंशियल" का क्या अर्थ है, एक रूपक (metaphor) का उपयोग करके:

लीनियर (Linear): यदि आपके पास 10 आइटम हैं, तो आपको 10 बॉक्स चाहिए।
एक्सपोनेंशियल (Exponential): यदि आपके पास 10 आइटम हैं, तो आपको $2^{10}$ (1,024) बॉक्स चाहिए।
डबली एक्सपोनेंशियल (Doubly Exponential): यदि आपके पास 10 आइटम हैं, तो आपको $2^{2^{10}}$ (एक अरब-खरब से अधिक) बॉक्स चाहिए।
ट्रिपली एक्सपोनेंशियल (Triply Exponential): यदि आपके पास 10 आइटम हैं, तो आपको $2^{2^{2^{10}}}$ बॉक्स चाहिए। यह संख्या इतनी विशाल है कि इसे समझना लगभग असंभव है। यह हर समुद्र के किनारे की रेत के प्रत्येक कण को गिनने की कोशिश करने जैसा है, और फिर हर रेत के कण के लिए, हर समुद्र के किनारे के लिए, हर समुद्र के किनारे पर ऐसा करने जैसा है...

लेखकों ने दिखाया कि इंडेक्स्ड लैंग्वेजेस के लिए, डाउनवर्ड क्लोजर मशीन लगभग इतनी बड़ी होती है। उन्होंने यह भी सिद्ध किया कि आप इससे बेहतर नहीं कर सकते; कुछ भाषाओं के लिए मशीन को इतना बड़ा होना ही चाहिए।

उन्होंने यह कैसे किया: "समरी" (Summary) का तरीका

आप स्टैक्स के टावरों को एक साधारण सूची में कैसे बदल सकते हैं बिना पैटर्न पहचानने की क्षमता खोए?

लेखकों ने सेमीग्रुप थ्योरी (Semigroup Theory) नामक गणित की एक शाखा का एक चतुर तरीका इस्तेमाल किया। कल्पना कीजिए कि आप एक बहुत लंबी कहानी पढ़ रहे हैं, लेकिन आप केवल कहानी के "वाइब" (vibe) की परवाह करते हैं, हर एक शब्द की नहीं।

यदि एक कहानी बार-बार एक विशिष्ट पैटर्न को दोहराती है (जैसे गाने में कोरस), तो आपको हर बार पूरा कोरस लिखने की आवश्यकता नहीं है। आप बस "कोरस" लिख सकते हैं और आगे बढ़ सकते हैं।
लेखकों ने स्टैक्स के लिए एक गणितीय "सारांश" (summary) बनाया। स्टैक में प्रत्येक एकल "प्लेट" या "टावर" को ट्रैक करने के बजाय, उन्होंने लंबे समान अनुक्रमों को एक एकल समरी सिंबल (summary symbol) से बदल दिया।

उन्होंने दिखाया कि भले ही स्टैक्स अनंत हों, आप उन्हें इन सारांशों के साथ बदल सकते हैं। एक बार जब आप ऐसा कर लेते हैं, तो जटिल "इंडेक्स्ड ग्रामर" एक सरल "कॉन्टेक्स्ट-फ्री ग्रामर" बन जाता है (एक मानक प्रकार का कंप्यूटर ग्रामर)। फिर, उन्होंने उस सरल ग्रामर को अंतिम डाउनवर्ड क्लोजर मशीन में बदलने के लिए मौजूदा तरीकों का उपयोग किया।

परिणाम: एक नया रिकॉर्ड

इस शोध पत्र से पहले, लोग जानते थे कि समस्या हल करने योग्य है, लेकिन उन्हें यह नहीं पता था कि इसकी लागत क्या है।

अपर बाउंड (Upper Bound): उन्होंने एक विधि बनाई जिससे मशीन बनाई जा सकती है, और इसमें ट्रिपली एक्सपोनेंशियल समय और स्थान लगता है।
लोअर बाउंड (Lower Bound): उन्होंने एक विशिष्ट, कठिन भाषा भी बनाई जो किसी भी मशीन को कम से कम ट्रिपली एक्सपेंशियल आकार का होने के लिए मजबूर करती है।

इसका अर्थ है कि उन्होंने इस समस्या के लिए सटीक "मूल्य टैग" (price tag) ढूंढ लिया है। यह केवल "कठिन" नहीं है; यह "ट्रिपल-एक्सपोनेंशियल रूप से कठिन" है।

उन्होंने इसे दो अन्य प्रश्नों पर भी लागू किया:

तुलना (Comparison): यदि आपके पास दो जटिल भाषाएँ हैं, तो क्या आप बता सकते हैं कि क्या उनके "डाउनवर्ड क्लोजर" समान हैं? उत्तर हाँ है, लेकिन यह एक co-3-NEXP-complete समस्या है। सरल शब्दों में: यह एक ऐसी पहेली है जो अविश्वसनीय रूप से कठिन है, जो एक उचित समय सीमा में कंप्यूटर द्वारा संभालने योग्य सैद्धांतिक सीमा के बिल्कुल किनारे पर है।
पंपिंग थ्रेशोल्ड (Pumping Threshold): उन्होंने सिद्ध किया कि एक परिमित इंडेक्स्ड लैंग्वेज में पैटर्न दोहराना शुरू करने से पहले आप कितनी लंबी शब्द उत्पन्न कर सकते हैं, वह भी ट्रिपली एक्सपोनेंशियल है।

सारांश

इंडेक्स्ड लैंग्वेजेस को एक विशाल, अनंत भूलभुलैया के रूप में सोचें। "डाउनवर्ड क्लोजर" उस भूलभुलैया के माध्यम से सभी संभावित शॉर्टकट का एक नक्शा है।

पुराना ज्ञान: हम जानते थे कि एक नक्शा मौजूद है।
नया ज्ञान: अब हम जानते हैं कि सबसे जटिल भूलभुलैया के लिए, नक्शा इतना विशाल है कि इसे बनाने में एक कंप्यूटर को ब्रह्मांड के अस्तित्व से भी अधिक समय लगेगा।
विधि: लेखकों ने दोहराव वाले हिस्सों को सारांशित करके भूलभुलैया को एक प्रबंधनीय आकार में सिकोड़ने का एक तरीका खोजा, जिससे वे नक्शा बनाने और यह सिद्ध करने में सक्षम हुए कि उसे कितना बड़ा होना चाहिए।

उन्होंने केवल अनुमान नहीं लगाया; उन्होंने नक्शा बनाया और सिद्ध किया कि उससे छोटा कोई भी नक्शा काम नहीं कर सकता।

तकनीकी सारांश: इंडेक्स्ड भाषाओं के डाउनवर्ड क्लोजर की जटिलता

समस्या विवरण

यह शोध पत्र इंडेक्स्ड भाषाओं (indexed languages) के लिए डाउनवर्ड क्लोजर (downward closures) के निर्माण की कम्प्यूटेशनल जटिलता को संबोधित करता है। किसी भाषा $L$ का डाउनवर्ड क्लोजर, जिसे $L^\downarrow$ द्वारा दर्शाया जाता है, $L$ के शब्दों के सभी स्कैटरड सबवर्ड्स (scattered subwords) का सेट है। हिगमैन लेम्मा (Higman's Lemma) के अनुसार, $L^\downarrow$ हमेशा एक रेगुलर भाषा होती है, जो इसे अनंत-अवस्था प्रणालियों (जैसे कि हायर-ऑर्डर मॉडल चेकिंग, एसिंक्रोनस प्रोग्राम्स और लॉसी चैनल सिस्टम) के सत्यापन में उपयोग किए जाने वाले एक महत्वपूर्ण रेगुलर ओवर-एप्रोक्सिमेशन (over-approximation) के रूप में उपयोगी बनाती है।

यद्यपि 2015 में वेल-क्वासी-ऑर्डरिंग्स (well-quasi-orderings) पर आधारित एक सामान्य एल्गोरिदम के माध्यम से इंडेक्स्ड भाषाओं (जो ऑर्डर-2 पुशडाउन ऑटोमेटा या 2-PDA के समकक्ष हैं) के डाउनवर्ड क्लोजर की कम्प्यूटेबिलिटी स्थापित की जा चुकी थी, लेकिन इस निर्माण की जटिलता सीमाओं (complexity bounds) का प्रश्न खुला हुआ था। विशेष रूप से, यह अज्ञात था कि क्या कोई प्रिमिटिव-रिकर्सिव निर्माण मौजूद है, और उनके द्वारा निर्मित ऑटोमेटा के आकार पर कोई ऊपरी या निचली सीमा ज्ञात नहीं थी। इस कार्य से पूर्व, इंडेक्स्ड भाषा के डाउनवर्ड क्लोजर के लिए नॉन-डिटरमिनिस्टिक फाइनाइट ऑटोमेटा (NFA) के आकार के लिए सर्वोत्तम ज्ञात निचली सीमा डबली एक्सपोनेंशियल (doubly exponential) थी, और डाउनवर्ड क्लोजर समावेशन (inclusion) और तुल्यता (equivalence) जैसी निर्णय समस्याओं की जटिलता कम से कम co-2-NEXP-हार्ड ज्ञात थी।

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

लेखक एक नवीन बीजगणितीय एब्स्ट्रैक्शन (algebraic abstraction) का उपयोग करके इस खुले प्रश्न को हल करते हैं, जो स्टैक सामग्री को कॉन्टेक्स्ट-फ्री ग्रामर (CFG) में बदलने के लिए इंडेक्स्ड ग्रामर को रूपांतरित करता है, जबकि डाउनवर्ड क्लोजर को सुरक्षित रखता है।

1. प्रोडक्टिविटी और एनोटेशन (Productivity and Annotation)

निर्माण की शुरुआत यह सुनिश्चित करने से होती है कि इनपुट इंडेक्स्ड ग्रामर प्रोडक्टिव (प्रत्येक सेंटेंशियल फॉर्म टर्मिनल शब्द व्युत्पन्न कर सकता है) हो। लेखक एक एनोटेटेड संस्करण पेश करते हैं जहाँ स्टैक सिम्बल्स को उन नॉन-टर्मिनल्स के सेट के साथ जोड़ा जाता है जो उस स्टैक कॉन्फ़िगरेशन से टर्मिनल शब्द व्युत्पन्न कर सकते हैं। यह "डेड" टर्म्स के उत्पादन को रोकता है जो भाषा में योगदान नहीं दे सकते, जो बाद के रूपांतरणों के दौरान डाउनवर्ड क्लोजर को बनाए रखने के लिए एक आवश्यक गुण है।

2. स्टैक मोनोइड और समरीज़ (The Stack Monoid and Summaries)

मुख्य तकनीकी नवाचार फाइनाइट सेमीग्रुप थ्योरी पर आधारित है। लेखक एक स्टैक मोनोइड $M$ (बूलियन मैट्रिसेस का एक फाइनाइट मोनोइड) को परिभाषित करते हैं जो व्याकरण के नॉन-टर्मिनल्स के सापेक्ष स्टैक ऑपरेशन्स (पुश और पॉप) के व्यवहार को एनकोड करता है।

समरीज़ (Summaries): वे मनमाने लंबे स्टैक वर्ड्स के समरीज़ की गणना करने के लिए सेमीग्रुप थ्योरी में हालिया प्रगति (विशेष रूप से जेकर और गिम्बर्ट एट अल. के परिणाम) का उपयोग करते हैं। एक समरी स्टैक वर्ड का एक संकुचित प्रतिनिधित्व है जो मोनोइड $M$ के संबंध में पुश/पॉप ऑपरेशन्स के परिणाम को निर्धारित करने के लिए पर्याप्त जानकारी रखता है।
पंपिंग और स्किपिंग (Pumping and Skipping): लेखक दो नए डेरिवेशन रूल्स, पंप (pump) और स्किप (skip) पेश करते हैं, जो उन स्टैक इन्फिक्स (infixes) के विस्तार और न्यूनीकरण की अनुमति देते हैं जो मोनोइड में एक ही इडेम्पोटेंट एलिमेंट (idempotent element) पर मैप होते हैं। वे सिद्ध करते हैं कि ये नियम भाषा के डाउनवर्ड क्लोजर को परिवर्तित नहीं करते हैं।
संपीड़न (Compression): इन नियमों को लागू करके, वे दिखाते हैं कि किसी भी स्टैक सामग्री को सीमित आकार के समरी में संकुचित किया जा सकता है, जो व्याकरण के आकार के एक्सपोनेंशियल में होता है। यह संपीड़न स्टैक सामग्री के सटीक विवरण के बारे में जानकारी खो देता है लेकिन डाउनवर्ड क्लोजर को सुरक्षित रखता है।

3. कॉन्टेक्स्ट-फ्री ग्रामर (CFG) में न्यूनीकरण

इन समरीज़ का उपयोग करते हुए, लेखक एक कॉन्टेक्स्ट-फ्री ग्रामर (CFG) $G_{CFG}$ का निर्माण करते हैं जो मूल इंडेक्स्ड ग्रामर $G$ का अनुकरण (simulate) करता है। $G_{CFG}$ में, इंडेक्स्ड ग्रामर की स्टैक सामग्री को उनके समरीज़ द्वारा प्रतिस्थापित किया जाता है।

$G_{CFG}$ के नॉन-टर्मिनल्स ट्रिपल्स $(A, X, \sigma)$ हैं, जहाँ $A$ एक नॉन-टर्मिनल है, $X$ नॉन-टर्मिनल्स का एक सेट है, और $\sigma$ एक व्यवहार्य (feasible) समरी है।
मूल व्याकरण में पुश और पॉप ऑपरेशन्स को समरीज़ पर ऑपरेशन्स (मोनोइड पर परिभाषित push और pop संबंधों का उपयोग करके) द्वारा सिम्युलेट किया जाता है।
लेखक सिद्ध करते हैं कि $L(G_{CFG})^\downarrow = L(G)^\downarrow$ ।

4. जटिलता विश्लेषण (Complexity Analysis)

चूंकि एक समरी का आकार व्याकरण के आकार के एक्सपोनेंशियल में सीमित होता है, इसलिए परिणामी CFG $G_{CFG}$ का आकार डबली एक्सपोनेंशियल होता है। CFGs के डाउनवर्ड क्लोजर की गणना करने वाले मौजूदा एल्गोरिदम CFG के सापेक्ष एक्सपोनेंशियल आकार का NFA प्रदान करते हैं। फलस्वरूप, $L(G)^\downarrow$ के लिए NFA का संयोजन ट्रिपली एक्सपोनेंशियल आकार का परिणाम देता है।

डिटरमिनिस्टिक फाइनाइट ऑटोमेटा (DFA) के लिए, ट्रिपली एक्सपोनेंशियल NFA पर लागू मानक सबसेट कंस्ट्रक्शन क्वाड्रापली एक्सपोनेंशियल ऊपरी सीमा (upper bound) प्रदान करता है।

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

ऊपरी सीमाएँ (Upper Bounds)

NFA आकार: $n$ आकार के इंडेक्स्ड ग्रामर के लिए, इसके डाउनवर्ड क्लोजर के लिए एक NFA ट्रिपली एक्सपोनेंशियल समय में संगणित किया जा सकता है और इसका आकार अधिकतम ट्रिपली एक्सपोनेंशियल ( $O(\exp_3(n))$ ) होता है।
DFA आकार: डाउनवर्ड क्लोजर के लिए एक DFA अधिकतम क्वाड्रापली एक्सपोनेंशियल ( $O(\exp_4(n))$ ) आकार के साथ बनाया जा सकता है।
निर्णय समस्याएँ: इंडेक्स्ड भाषाओं के लिए डाउनवर्ड क्लोजर समावेशन ( $L_1^\downarrow \subseteq L_2^\downarrow$ ) और तुल्यता ( $L_1^\downarrow = L_2^\downarrow$ ) की समस्याएँ co-3-NEXP-कम्प्लीट हैं।

निचली सीमाएँ (Lower Bounds)

लेखक मिलान करने वाली निचली सीमाएँ प्रदान करते हैं, जो उनके ऊपरी अनुमानों की सटीकता को सिद्ध करती हैं:

NFA निचली सीमा: ऐसा एक इंडेक्स्ड ग्रामर परिवार मौजूद है जिसके बहुपद आकार के लिए, उनके डाउनवर्ड क्लोजर के लिए किसी भी NFA को कम से कम ट्रिपली एक्सपोनेंशियल स्टेट्स की आवश्यकता होती है। यह $\{a^{\exp_3(n)}\}$ भाषा उत्पन्न करने वाले व्याकरण का निर्माण करके प्राप्त किया गया है।
DFA निचली सीमा: एक इंडेक्स्ड ग्रामर परिवार मौजूद है जिसके लिए डाउनवर्ड क्लोजर के किसी भी DFA को कम से कम क्वाड्रापली एक्सपोनेंशियल स्टेट्स की आवश्यकता होती है।
पंपिंग थ्रेशोल्ड (Pumping Threshold): परिणाम यह संकेत देते हैं कि इंडेक्स्ड ग्रामर के लिए पंपिंग थ्रेशोल्ड (एक $n$ आकार के सीमित इंडेक्स्ड भाषा में शब्द की अधिकतम लंबाई) कम से कम ट्रिपली एक्सपोनेंशियल रूप से बढ़ता है, जो साहित्य में पाए गए पिछले द्वि-चरणीय (doubly exponential) दावे को सुधारता है।

महत्व

यह शोध पत्र इंडेक्स्ड भाषाओं के डाउनवर्ड क्लोजर की जटिलता से संबंधित एक लंबे समय से चले आ रहे खुले प्रश्न को हल करता है।

सटीक सीमाएँ: यह स्थापित करता है कि जटिलता कॉन्टेक्स्ट-फ्री भाषाओं (जो NFAs के लिए डबली एक्सपोनेंशियल होती हैं) की तुलना में स्पष्ट रूप से अधिक है, लेकिन $k > 2$ के उच्च-क्रम वाले सिस्टम से जुड़े सामान्य टॉवर ऑफ एक्सपोनेंशियल्स (tower of exponentials) से कम है। ऑर्डर-2 पुशडाउन ऑटोमेटा के लिए अन्य समस्याओं (जैसे एम्प्टीनेस) के साथ रैखिक वृद्धि के विपरीत, इंडेक्स्ड भाषाओं के लिए डबली से ट्रिपली एक्सपोनेंशियल की छलांग अप्रत्याशित है।
एल्गोरिथमिक व्यवहार्यता: यह पुष्टि करता है कि एक प्रिमिटिव-रिकर्सिव निर्माण मौजूद है, जिससे यह प्रश्न हल होता है कि क्या समस्या केवल कम्प्यूटेबल है या एक विशिष्ट जटिलता वर्ग के भीतर प्रभावी रूप से कंस्ट्रक्टिबल है।
मेथोडोलॉजिकल एडवांस: स्टैक सामग्री को संकुचित करने के लिए सेमीग्रुप-आधारित समरीज़ का उपयोग करने की तकनीक, जो डाउनवर्ड क्लोजर को सुरक्षित रखते हुए काम करती है, उच्च-क्रम प्रणालियों के विश्लेषण के लिए एक नया उपकरण प्रदान करती है, जो व्यापक श्रेणी के अनंत-अवस्था प्रणालियों पर भी लागू हो सकती है।

लेखक इस बात पर जोर देते हैं कि उनके परिणाम इंडेक्स्ड ग्रामर के एक कंस्ट्रक्टिव ट्रांसफॉर्मेशन से प्राप्त हुए हैं, जो स्टैक संरचना के डाउनवर्ड क्लोजर के लिए आवश्यक सबवर्ड स्ट्रक्चर को प्रबंधित करने के लिए स्टैक मोनोइड के बीजगणितीय गुणों का लाभ उठाते हैं।