💻 computer science

On Complexity Bounds and Confluence of Parallel Term Rewriting

यह शोध पत्र अनुक्रमिक जटिलता विधियों का लाभ उठाकर और अभिसरण (confluence) के लिए पर्याप्त मानदंड स्थापित करके, समानांतर-इनरमोस्ट टर्म रीराइटिंग की समानांतर जटिलता पर ऊपरी और निचली सीमाओं को प्राप्त करने के लिए स्वचालित तकनीकों को प्रस्तुत करता है, जो कि AProVE टूल के विस्तार और व्यापक बेंचमार्क प्रयोगों के माध्यम से मान्य एक ढांचा है।

मूल लेखक: Thaïs Baudon, Carsten Fuhs, Laure Gonnord

प्रकाशित 2026-04-08

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

CC BY 4.0

मूल लेखक: Thaïs Baudon, Carsten Fuhs, Laure Gonnord

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

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

लेकिन अब, आपके पास सैकड़ों शेफों वाली एक रसोई है (पैरेलल कंप्यूटिंग)। सवाल यह है: यदि सभी लोग एक ही समय में काम करते हैं, तो हम खाना बनाने में कितना तेज़ हो सकते हैं? और इससे भी महत्वपूर्ण बात यह है कि हम यह कैसे जान सकते हैं कि भोजन का स्वाद वास्तव में एक जैसा ही रहेगा, चाहे कोई भी शेफ पहले कौन सी सामग्री उठाए?

यह शोध पत्र उन प्रश्नों के उत्तर देने के लिए एक मार्गदर्शिका है जो कंप्यूटर विज्ञान में उपयोग किए जाने वाले एक विशिष्ट प्रकार के "रेसिपी" यानी टर्म रीराइटिंग (Term Rewriting) के लिए है। यहाँ उनके निष्कर्षों का सरल उपमाओं का उपयोग करके विवरण दिया गया है।

1. समस्या: "एकल शेफ" बनाम "रसोई दल"

पारंपरिक कंप्यूटर विज्ञान में, हम यह अनुमान लगाने में बहुत अच्छे हैं कि एक अकेला शेफ भोजन पकाने में कितना समय लेगा। हमारे पास ऐसे उपकरण हैं जो रेसिपी को देखकर कह सकते हैं, "इसमें 10 मिनट लगेंगे।"

हालाँकि, जब आपके पास एक रसोई दल (brigade) होता है जहाँ शेफ समानांतर (parallel) में काम करते हैं, तो नियम बदल जाते हैं।

जाल (The Trap): कभी-कभी, किसी कार्य को 100 शेफों को सौंप देने से वह 100 गुना तेज़ नहीं हो जाता। यदि रेसिपी कहती है, "प्याज काटने से पहले सॉस के उबलने का इंतज़ार करें," तो काटने वाले शेफों को बिना कुछ किए खाली खड़ा रहना पड़ता है।
लक्ष्य: लेखक एक ऐसा उपकरण बनाना चाहते थे जो रेसिपी को देख सके और आपको बता सके:
1. अपर बाउंड (ऊपरी सीमा): "अनंत शेफ होने के बावजूद, इसमें अधिकतम X मिनट लगेंगे।" (सर्वश्रेष्ठ-मामला गति)।
2. लोअर बाउंड (निचली सीमा): "अनंत शेफ होने के बावजूद, इसमें कम से कम Y मिनट लगेंगे।" (रुकावट/bottleneck)।

2. जादुई ट्रिक: "डिपेंडेंसी टुपल्स" एक मानचित्र के रूप में

इसे हल करने के लिए, लेखकों ने पैरेलल डिपेंडेंसी टुपल्स (Parallel Dependency Tuples) नामक एक चतुर तकनीक का उपयोग किया।

कल्पना कीजिए कि आप केक की रेसिपी देख रहे हैं।

सीक्वेंशियल दृश्य (Sequential View): आप एक सूची देखते हैं: "मैदा मिलाएं, फिर अंडे डालें, फिर बेक करें।"
पैरेलल दृश्य (Parallel View): आप एक मानचित्र देखते हैं। "मैदा मिलाना और अंडे डालना एक साथ हो सकता है, लेकिन बेकिंग दोनों के होने का इंतज़ार करेगी।"

लेखकों ने इस मानचित्र को बनाने का एक नया तरीका विकसित किया। केवल चरणों को सूचीबद्ध करने के बजाय, उन्होंने रेसिपी को निर्भरता श्रृंखलाओं (chains of dependencies) में तोड़ दिया।

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

उन्होंने महसूस किया कि समानांतर खाना पकाने का वर्णन करने के लिए एक पूरी नई भाषा आविष्कार करने के बजाय, वे पैरेलल रेसिपी को वापस उस प्रारूप में अनुवाद (translate) कर सकते हैं जिसे उनके मौजूदा "एकल-शेफ" विश्लेषण उपकरण पहले से ही समझते थे। उन्होंने मूल रूप से कहा, "हे, मौजूदा उपकरणों, बस मान लो कि ये पैरेलल श्रृंखलाएं अलग-अलग सीक्वेंशियल कार्य हैं, और फिर हमें सबसे लंबा रास्ता बताओ।"

3. "कॉन्फ्लुएंस" (Confluence) की जाँच: क्या केक का स्वाद एक जैसा रहेगा?

यह इस शोध पत्र का सबसे महत्वपूर्ण हिस्सा है। एक समानांतर रसोई में, अराजकता हो सकती है।

परिदृश्य: शेफ A सूप में नमक डालता है। शेफ B काली मिर्च डालता है।
जोखिम: क्या होगा यदि शेफ A और शेफ B दोनों ठीक एक ही समय में एक ही चम्मच पकड़ने की कोशिश करते हैं? या क्या होगा यदि उनके द्वारा सामग्री डालने का क्रम अंतिम स्वाद को बदल देता है?

कंप्यूटर विज्ञान में, इसे कॉन्फ्लुएंस (Confluence) कहा जाता है। यह पूछता है: क्या समानांतर चरणों को करने का क्रम मायने रखता है?

यदि हाँ (कॉन्फ्लुएंट नहीं है): कंप्यूटर क्रैश हो सकता है या परिणाम गलत दे सकता है, यह इस पर निर्भर करता है कि किस शेफ ने पहले कदम उठाया।
यदि नहीं (कॉन्फ्लुएंट है): परिणाम नियत (deterministic) है। चाहे कोई भी पहले क्या उठाए, अंतिम सूप का स्वाद बिल्कुल एक जैसा ही रहेगा।

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

उन्होंने दो नए "सुरक्षा चेक" (प्रमेय/Theorems) विकसित किए जो गुणवत्ता नियंत्रण निरीक्षक की तरह कार्य करते हैं:

"नो ओवरलैप" (कोई ओवरलैप नहीं) चेक: यदि रेसिपी के दो नियम कभी भी परस्पर विरोधी तरीके से एक ही सामग्री का उपयोग नहीं करते हैं, तो यह सुरक्षित है।
"ट्रिवियल ओवरलैप" (तुच्छ ओवरलैप) चेक: भले ही नियम ओवरलैप होते हों, यदि वे अंततः बिल्कुल एक ही परिणाम देते हैं, तो भी यह सुरक्षित है।

ये चेक तेज़ और स्वचालित हैं। वे कंप्यूटर को बताते हैं: "ठीक है, यह रेसिपी समानांतर में चलाने के लिए सुरक्षित है। अब इसकी गति की गणना करें।"

4. परिणाम: सिद्धांत से व्यवहार तक

लेखकों ने केवल सिद्धांत नहीं लिखा; उन्होंने APROVE (एक रोबोट शेफ) नामक एक उपकरण बनाया और कंप्यूटर विज्ञान समुदाय के सैकड़ों मानक बेंचमार्क पर इसका परीक्षण किया।

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

बड़ी तस्वीर की उपमा

इस शोध पत्र को एक सुपर-हाईवे के लिए ट्रैफिक कंट्रोल सिस्टम के रूप में सोचें।

सीक्वेंशियल एनालिसिस यह गिनने जैसा है कि एक कार को A से B तक जाने में कितना समय लगता है।
पैरेलल एनालिसिस यह पूछने जैसा है: "यदि हमारे पास 1,000 लेन हैं, तो 1,000 कारों को वहां पहुंचने में कितना समय लगेगा?"
लेखकों का योगदान:
- उन्होंने एक मानचित्र (Dependency Tuples) बनाया जो दिखाता है कि कौन सी लेन आपस में मिलती हैं और कौन सी स्वतंत्र हैं।
- उन्होंने एक सुरक्षा निरीक्षक (Confluence Criteria) बनाया ताकि यह सुनिश्चित हो सके कि यदि दो कारें मिलती हैं, तो वे टकराएं नहीं।
- उन्होंने सिद्ध किया कि आप इस नए, सुपर-फास्ट हाईवे के प्रवाह की भविष्यवाणी करने के लिए अपने पुराने, भरोसेमंद ट्रैफिक नियमों (सीक्वेंशियल टूल्स) का उपयोग कर सकते हैं, बशर्ते आप सुरक्षा नियमों की जाँच कर लें।

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

यहाँ शोध पत्र "On Complexity Bounds and Confluence of Parallel Term Rewriting" (बौडोन, फह्स और गोनॉर्ड द्वारा लिखित) का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र टर्म रीराइटिंग सिस्टम (TRSs) के लिए समानांतर रनटाइम जटिलता (parallel runtime complexity) के स्वचालित विश्लेषण के संबंध में साहित्य में मौजूद एक महत्वपूर्ण अंतर को संबोधित करता है।

संदर्भ: जबकि 'सीक्वेंशियल इनरमोस्ट रीराइटिंग' (जो OCaml, Scala और Rust जैसी भाषाओं में कॉल-बाय-वैल्यू मूल्यांकन के अनुरूप है) के लिए स्वचालित जटिलता विश्लेषण परिपक्व है, 'पैरेलल-इनरमोस्ट' रीराइटिंग के विश्लेषण के लिए कोई स्थापित तकनीक उपलब्ध नहीं है।
अंतराल (The Gap): पैरेलल-इनरमोस्ट रीराइटिंग उन मशीनों पर निष्पादन का मॉडल करती है जहाँ अनबाउंडेड पैरेललिज्म (unbounded parallelism) होता है, जहाँ सभी इनरमोस्ट रेडेक्स (डेटा पर फंक्शन कॉल्स) को एक साथ कम (reduce) किया जाता है। मौजूदा उपकरण यह स्वचालित रूप से निर्धारित करने में सक्षम नहीं हैं कि क्या समानांतरकरण (parallelization) करने पर किसी प्रोग्राम की जटिलता में सुधार होता है (जैसे, $O(n^2)$ से $O(n)$ में) या संरचनात्मक निर्भरताओं के कारण यह अपरिवर्तित रहती है।
चुनौती: पैरेलल जटिलता के लिए लोअर बाउंड्स (lower bounds) प्राप्त करने के लिए, रीराइट संबंध का कन्फ्लुएंट (confluent/एकसुसंग) होना आवश्यक है। हालाँकि, सीक्वेंशियल रीराइटिंग के लिए मानक कन्फुलेंस मानदंड पैरेलल-इनरमोस्ट रीराइटिंग पर आवश्यक रूप से लागू नहीं होते हैं, और इस पैरेलल रणनीति के लिए इस गुण को सत्यापित करने के लिए कोई स्वचालित उपकरण मौजूद नहीं थे।

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

लेखक एक ट्रांसफॉर्मेशनल दृष्टिकोण प्रस्तावित करते हैं जो पैरेलल समस्या को हल करने के लिए मौजूदा सीक्वेंशियल जटिलता विश्लेषण उपकरणों का लाभ उठाता है। यह कार्यप्रणाली तीन मुख्य स्तंभों से बनी है:

A. पैरेलल डिपेंडेंसी टुपल्स (Parallel Dependency Tuples - PDTs)

अपर बाउंड्स (upper bounds) का विश्लेषण करने के लिए, लेखक मानक डिपेंडेंसी टुपल्स (DT) ढांचे का विस्तार करते हैं।

अवधारणा: सीक्वेंशियल विश्लेषण में, एक नियम $\ell \to r$ सभी रिकर्सिव कॉल्स को समूहबद्ध करने वाला एक एकल DT उत्पन्न करता है। पैरेलल विश्लेषण में, स्वतंत्र कॉल्स को एक साथ मूल्यांकित किया जा सकता है।
तंत्र: लेखक मैक्सिमल स्ट्रक्चरल डिपेंडेंसी चेन्स (MSDC) को परिभाषित करते हैं। यदि किसी नियम के राइट-हैंड साइड में फंक्शन कॉल्स संरचनात्मक रूप से निर्भर हैं (एक दूसरे की प्रतीक्षा करेगा), तो उन्हें समूहबद्ध किया जाता है। यदि कॉल्स स्वतंत्र हैं, तो उन्हें अलग-अलग PDTs में विभाजित किया जाता है।
परिणाम: एक नियम प्रति DT के बजाय, PDTs का एक सेट उत्पन्न करता है। प्रत्येक PDT एक संभावित "वर्स्ट-केस" निष्पादन पथ (सबसे लंबी निर्भरता श्रृंखला) का प्रतिनिधित्व करता है। पैरेलल सिस्टम की जटिलता को मानक पॉलिनॉमियल इंटरप्रिटेशन का उपयोग करके इस PDTs के सेट की जटिलता द्वारा सीमित किया जाता है।

B. रिलेटिव रीराइटिंग में रूपांतरण (Transformation to Relative Rewriting)

लोअर बाउंड्स के लिए मौजूदा टूल्स का उपयोग करने और सीक्वेंशियल विश्लेषण मशीनरी को पुन: उपयोग करने के लिए, लेखक एक PDT समस्या को वापस एक मानक TRS में रूपांतरित करने का परिचय देते हैं।

तंत्र: वे एक $\langle PDT(R), PDT(R), R \rangle$ कैनोनिकल पैरेलल DT समस्या को एक रिलेटिव TRS $PDT(R) / R$ में परिवर्तित करते हैं।
तर्क: इस रिलेटिव सिस्टम में, $PDT(R) $के नियम (पैरेलल निर्भरताएं) जटिलता में गिने जाते हैं, जबकि$ R$ (मूल रीराइट नियम) के नियम "फ्री" (केवल आर्गुमेंट्स को मूल्यांकित करने के लिए उपयोग किए जाते हैं) होते हैं।
लाभ: यह लेखकों को उन अत्याधुनिक उपकरणों (जैसे APROVE और TCT) का उपयोग करने की अनुमति देता है जो सीक्वेंशियल इनरमोस्ट जटिलता के लिए लोअर बाउंड्स की गणना करते हैं, ताकि पैरेलल मामले के लिए लोअर बाउंड्स का अनुमान लगाया जा सके।

C. पैरेलल-इनरमोस्ट रीराइटिंग के लिए कन्फुलेंस मानदंड (Confluence Criteria)

चूंकि लोअर बाउंड ट्रांसफॉर्मेशन के लिए पैरेलल-इनरमोस्ट संबंध ( $\xrightarrow{i}_{R}$ ) का कन्फ्लुएंट होना आवश्यक है, इसलिए लेखक दो प्रभावी, सिंटैक्टिक पर्याप्त मानदंड प्रदान करते हैं:

नॉन-ओवरलैपिंग नियम (Non-overlapping Rules - कोरोलरी 6.10): यदि किसी TRS में कोई क्रिटिकल पेयर्स नहीं हैं (नॉन-ओवरलैपिंग), तो पैरेलल-इनरमोस्ट संबंध नियत (deterministic) और इस प्रकार कन्फ्लुएंट होता है।
ट्रिवियल इनरमोस्ट क्रिटिकल ओवरलेज़ (Trivial Innermost Critical Overlays - थ्योरम 6.18): एक मजबूत मानदंड जो कहता है कि यदि सभी इनरमोस्ट क्रिटिकल ओवरलेज़ (ओवरलैप जो वास्तव में इनरमोस्ट स्टेप में हो सकते हैं) ट्रिवियल हैं (अर्थात, एक ही टर्म परिणाम देते हैं), तो पैरेलल-इनरमोस्ट संबंध कन्फ्लुएंट होता है।

महत्व: ये मानदंड विशुद्ध रूप से सिंटैक्टिक हैं और इन्हें बिना सर्च समस्याओं के स्वचालित रूप से जांचा जा सकता है।

3. प्रमुख योगदान (Key Contributions)

औपचारिक ढांचा (Formal Framework): पैरेलल डिपेंडेंसी टुपल्स (PDTs) और पैरेलल-इनरमोस्ट रनटाइम कॉम्प्लेक्सिटी ( $pirc_R$ ) की परिभाषा।
सैद्धांतिक प्रमाण (Theoretical Proofs):
- यह सिद्ध करना कि कैनोनिकल पैरेलल DT समस्या की जटिलता पैरेलल-इनरमोस्ट रीराइटिंग की डेरिवेशन हाइट को सीमित करती है (थ्योरम 4.9)।
- यह सिद्ध करना कि एक रिलेटिव TRS में रूपांतरण दोनों अपर और लोअर जटिलता सीमाओं को सुरक्षित रखता है (थ्योरम 5.6 और 5.8)।
- यह सिद्ध करना कि नॉन-ओवरलैपिंग TRS और ट्रिवियल इनरमोस्ट क्रिटिकल ओवरलेज़ वाले TRS पैरेलल-इनरमोस्ट रीराइटिंग के तहत कन्फ्लुएंट हैं (थ्योरम 6.18)।
कार्यान्वयन (Implementation): इन तकनीकों को APROVE टूल में एकीकृत किया गया है (लगभग 730 लाइनों का जावा कोड जोड़ा गया)।
बेंचमार्क्स (Benchmarks): TPDB से 294 TRSs पर व्यापक प्रयोग किए गए, जिन्हें उनकी संभावित पैरेललिज्म के लिए चुना गया था।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने TPDB बेंचमार्क सूट पर अपने कार्यान्वयन का मूल्यांकन किया:

अपर बाउंड्स (Upper Bounds): नए "सेक्शन 4" कॉन्फ़िगरेशन (PDTs का उपयोग करके) ने बेसलाइन सीक्वेंशियल विश्लेषण (50 TRSs) की तुलना में 70 TRSs (लीनियर बाउंड्स) के लिए अनुमानित अपर बाउंड्स में सुधार किया, जो कि 40% का सुधार है।
- उदाहरण: एक विशिष्ट रिकर्सिव TRS के लिए, सीक्वेंशियल बाउंड $O(n^{10})$ था, जबकि पैरेलल विश्लेषण ने सही ढंग से $O(n)$ का टाइट बाउंड पहचाना।
लोअर बाउंड्स (Lower Bounds): रिलेटिव TRSs में रूपांतरण (सेक्शन 5) का उपयोग करके, टूल ने कमजोर मानदंड द्वारा सिद्ध कन्फ्लुएंट 165 में से 140 TRSs के लिए और थ्योरम 6.18 का उपयोग करके 190 में से 159 के लिए गैर-तुच्छ (non-trivial) लोअर बाउंड्स सफलतापूर्वक निकाले।
कन्फुलेंस विश्लेषण (Confluence Analysis): नए थ्योरम 6.18 ने बेंचमार्क सेट के लिए 64.6% कन्फुलेंस सिद्ध किया, जो नॉन-ओवरलैपिंग मानदंड (56.1%) से काफी बेहतर है। COPS कन्फुलेंस बेंचमार्क पर, इसने 47.5% सिस्टम के लिए कन्फुलेंस सिद्ध किया, जबकि नॉन-ओवरलैपिंग चेक के लिए यह केवल 10.4% था।
परिशुद्धता (Precision): 49 TRSs के लिए, टूल ने टाइट बाउंड्स (अपर और लोअर बाउंड्स का मिलान, जैसे $\Theta(n)$ ) सफलतापूर्वक निकाले।

5. महत्व और प्रभाव (Significance and Impact)

अंतराल को भरना (Bridging the Gap): यह पैरेलल टर्म रीराइटिंग जटिलता के लिए अपर और लोअर दोनों बाउंड्स का अनुमान लगाने के लिए पूर्णतः स्वचालित विधि प्रदान करने वाला पहला कार्य है।
कंपाइलर ऑप्टिमाइजेशन (Compiler Optimization): इसके परिणाम समानांतर कंपाइलर्स के लिए सीधे तौरable हैं। यह निर्धारित करके कि किसी फंक्शन की जटिलता सीक्वेंशियल और पैरेलल मोड में एसिम्प्टोटिक रूप से समान है या नहीं (जैसे, $O(n^2)$ बनाम $O(n^2)$ ), कंपाइलर अनावश्यक पैरेललिज्म ओवरहेड से बच सकते हैं। इसके विपरीत, उन मामलों की पहचान करना जहाँ पैरेललिज्म महत्वपूर्ण गति प्रदान करता है (जैसे, $O(n^2) \to O(n)$ ), यह मार्गदर्शन करता है कि कहाँ पैरेलल निष्पादन (जैसे, GPUs पर) लागू किया जाए।
टूल पुन: उपयोग (Tool Reuse): यह कार्य एक पैरेलल समस्या को सीक्वेंशियल समस्या में बदलकर मौजूदा सीक्वेंशियल जटिलता टूल (APROVE, TCT) के विशाल इकोसिस्टम का कुशलतापूर्वक पुन: उपयोग करता है, जिससे नए विश्लेषण इंजन बनाने की आवश्यकता नहीं पड़ती।
कन्फुलेंस थ्योरी (Confluence Theory): यह शोध पत्र सीक्वेंशियल और पैरेलल कन्फुलेंस के बीच संबंधों के बारे में खुले अनुमानों को हल करता है, जो नियत (deterministic) पैरेलल प्रोग्रामों के लिए व्यावहारिक, जांच योग्य मानदंड प्रदान करता है।

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