Critical pair (term rewriting)
[[फ़ाइलः दो पुनर्लेखन नियमों एस. टी. टी. (ऊपरी पंक्ति, बाएँ) और एल. आर. आर. (दाएँ) से प्राप्त एक महत्वपूर्ण जोड़ी का क्रिटपेयर svg.svg |thumb |400px |Triangle आरेख। प्रतिस्थापन σ उपपद s|p को l के साथ एकीकृत करता है। परिणामी आच्छादन शब्द sσ [lσ] p (निचली पंक्ति, मध्य) को क्रमशः tσ और sσ [rσ] p (निचली पंक्ति, बाएँ और दाएँ) शब्द में फिर से लिखा जा सकता है। बाद के दो शब्द महत्वपूर्ण जोड़ी बनाते हैं। यदि पुनर्लेखन नियम सेट मिश्रित है तो उन्हें अंततः एक सामान्य शब्द में फिर से लिखा जा सकता है।] एक महत्वपूर्ण जोड़ी एक शब्द पुनर्लेखन प्रणाली में उत्पन्न होती है जब दो पुनर्लेखन नियम दो अलग-अलग शब्दों को प्राप्त करने के लिए ओवरलैप करते हैं। अधिक विस्तार से, (टी1, टी2) एक महत्वपूर्ण जोड़ी है यदि एक शब्द टी है जिसके लिए एक पुनर्लेखन नियम के दो अलग-अलग अनुप्रयोग (या तो एक ही नियम अलग-अलग लागू होते हैं, या दो अलग-अलग नियम) टी1 और टी2 शब्द प्राप्त करते हैं। परिभाषा एक महत्वपूर्ण जोड़ी की वास्तविक परिभाषा थोड़ी अधिक शामिल है क्योंकि इसमें उन जोड़े को शामिल नहीं किया गया है जिन्हें प्रतिस्थापन द्वारा महत्वपूर्ण जोड़े से प्राप्त किया जा सकता है और ओवरलैप के आधार पर जोड़ी को उन्मुख करता है। विशेष रूप से, अतिव्यापी नियमों की एक जोड़ी के लिए और, अतिव्यापी के साथ कुछ गैर-खाली संदर्भ के लिए, और शब्द (जो एक चर नहीं है) कुछ प्रतिस्थापनों के तहत मेल खाता है जो सबसे सामान्य हैं, महत्वपूर्ण जोड़ी है। जब महत्वपूर्ण जोड़ी के दोनों पक्ष एक ही अवधि तक कम हो सकते हैं, तो महत्वपूर्ण जोड़ी को अभिसारी कहा जाता है। जहाँ महत्वपूर्ण जोड़ी का एक पक्ष दूसरे के समान होता है, महत्वपूर्ण जोड़ी को तुच्छ कहा जाता है। उदाहरण के लिए, पुनर्लेखन प्रणाली शब्द में नियम {।-। f (g (x, y), z)।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।। इन दोनों शब्दों को एक ही पुनर्लेखन नियम लागू करके f (g (x, y), z) शब्द से प्राप्त किया जा सकता है। एक अन्य उदाहरण के रूप में, एकल नियम {।-। f (x, y)।।।। के साथ पुनर्लेखन प्रणाली शब्द पर विचार करें। ।-। इस नियम को f (f (x, x), x) शब्द पर दो अलग-अलग तरीकों से लागू करके, हम देखते हैं कि (f (x, x), f (x, x)) एक (तुच्छ) महत्वपूर्ण जोड़ी है। क्रिटिकल पेयर लेम्मा कॉन्फ्लूएंस स्पष्ट रूप से अभिसारी क्रिटिकल जोड़े का संकेत देता हैः यदि कोई क्रिटिकल पेयर अमलो ए, बीओएल उत्पन्न होता है, तो ए और बी में एक सामान्य कमी होती है और इस प्रकार क्रिटिकल पेयर अभिसारी होता है। यदि पुनर्लेखन प्रणाली शब्द समृद्ध नहीं है, तो महत्वपूर्ण जोड़ी अभिसरण नहीं कर सकती है, इसलिए महत्वपूर्ण जोड़े संभावित स्रोत हैं जहां संगम विफल हो जाएगा। 'क्रिटिकल पेयर लेम्मा' में कहा गया है कि एक शब्द पुनर्लेखन प्रणाली कमजोर है (उर्फ। स्थानीय रूप से) संगम यदि और केवल तभी जब सभी महत्वपूर्ण जोड़े अभिसारी हों। इस प्रकार, यह पता लगाने के लिए कि क्या एक शब्द पुनर्लेखन प्रणाली कमजोर रूप से मिश्रित है, सभी महत्वपूर्ण जोड़े का परीक्षण करना और यह देखना पर्याप्त है कि क्या वे अभिसारी हैं। इससे एल्गोरिदमिक रूप से यह पता लगाना संभव हो जाता है कि क्या कोई शब्द पुनर्लेखन प्रणाली कमजोर रूप से मिश्रित है या नहीं, यह देखते हुए कि कोई एल्गोरिदमिक रूप से जांच कर सकता है कि क्या दो शब्द अभिसरण करते हैं। यह भी देखें कि क्नुथ-बेंडिक्स कम्प्लीशन, एक दिए गए एक बाहरी लिंक के बराबर एक मिश्रित और समाप्ति शब्द पुनर्लेखन प्रणाली की गणना करने के लिए महत्वपूर्ण जोड़े पर आधारित एक एल्गोरिथ्म संदर्भ फ्रांज बाडर और टोबियास निपकोव, टर्म पुनर्लेखन और ऑल दैट, "कैम्ब्रिज यूनिवर्सिटी प्रेस, 1998 (बुक वेबलिंक) पुनर्लेखन प्रणाली