निर्भरता संबंध

For other uses, see निर्भरता (बहुविकल्पी).

निर्भरता संबंध के साथ भ्रमित न हों, जो सदिश समष्टि के सदस्यों के बीच रैखिक निर्भरता की अवधारणा का एक सामान्यीकरण है।

कंप्यूटर विज्ञान में, विशेष रूप से संगामिति सिद्धांत में, निर्भरता संबंध एक परिमित क्षेत्र $\Sigma$ है, सममित संबंध, और प्रतिवर्ती संबंध है, अर्थात एक परिमित सहिष्णुता संबंध पर एक द्विआधारी संबंध होता है। यह आदेशित जोड़े $D$ का एक परिमित समुच्चय है, ऐसा है कि

• यदि $(a,b)\in D$ तब $(b,a)\in D$ (सममित)
• यदि $a\in \Sigma$, तब $(a,a)\in D$ (प्रतिवर्त)

सामान्यतः, निर्भरता संबंध सकर्मक संबंध नहीं होते है, इस प्रकार, वे सकर्मकता को त्याग कर एक तुल्यता संबंध की धारणा का सामान्यीकरण करते है।

$\Sigma$ को वर्णमाला भी कहा जाता है जिस पर $D$ परिभाषित किया गया है। प्रेरित स्वतंत्रता द्वारा $D$ द्विआधारी का संबंध है $I$

$I=(\Sigma \times \Sigma )\setminus D$

अर्थात्, स्वतंत्रता उन सभी क्रमित युग्मों का समुच्चय है जो $D$ के अंदर नहीं होते है। स्वतंत्रता संबंध सममित और अपरिवर्तनीय होते है। इसके विपरीत, किसी भी सममित और अपरिवर्तनीय संबंध को देखते हुए $I$ एक परिमित वर्णमाला है, संबंध

$D=(\Sigma \times \Sigma )\setminus I$

एक निर्भरता संबंध है।

जोड़ा $(\Sigma ,D)$ को समवर्ती वर्णमाला कहा जाता है। जोड़ा $(\Sigma ,I)$ को स्वतंत्रता वर्णमाला या रिलायंस वर्णमाला कहा जाता है, लेकिन यह शब्द त्रिपक्षीय को भी संदर्भित कर सकता है $(\Sigma ,D,I)$ (साथ $I$ प्रेरक $D$). तत्व $x,y\in \Sigma$ आश्रित कहलाते है यदि $xDy$ धारण करता है, और स्वतंत्र, अन्य (अर्थात यदि $xIy$ रखता है)।

एक रिलायंस वर्णमाला मे दिया गया $(\Sigma ,D,I)$, एक सममित और अपरिवर्तनीय संबंध $\doteq$ मुक्त मोनॉइड पर परिभाषित किया जा सकता है $\Sigma ^{*}$ परिमित लंबाई के सभी संभावित स्ट्रिंग: $xaby\doteq xbay$ सभी स्ट्रिंग के लिए $x,y\in \Sigma ^{*}$ और सभी स्वतंत्र प्रतीक $a,b\in I$. का तुल्यता समापन $\doteq$ निरूपित किया जाता है $\equiv$ या $\equiv _{(\Sigma ,D,I)}$ और $(\Sigma ,D,I)$-तुल्यता कहा जाता है। अनौपचारिक रूप से, $p\equiv q$ रखती है यदि स्ट्रिंग $p$ में परिवर्तित किया जा सकता है $q$ आसन्न स्वतंत्र प्रतीकों के स्वैप के परिमित अनुक्रम की समानता कक्षाएं $\equiv$ ट्रेस मोनोइड कहा जाता है, और ट्रेस सिद्धांत में अध्ययन किया जाता है।

उदाहरण

वर्णमाला $\Sigma =\{a,b,c\}$, एक संभावित निर्भरता संबंध है

$D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}$, तस्वीर देखें।

संगत स्वतन्त्रता है $I=\{(b,c),\,(c,b)\}$. तब उदाहरण प्रतीक $b,c$ एक दूसरे से स्वतंत्र है, और उदाहरण $a,b$ आश्रित है। स्ट्रिंग $acbba$ के बराबर होता है $abcba$ और $abbca$, लेकिन किसी अन्य स्ट्रिंग के लिए नहीं होता है।