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

For other uses, see Dependency (disambiguation).

Not to be confused with Dependence relation, which is a generalization of the concept of linear dependence among members of a vector space.

कंप्यूटर विज्ञान में, विशेष रूप से संगामिति (कंप्यूटर विज्ञान) में, एक निर्भरता संबंध एक परिमित डोमेन पर एक द्विआधारी संबंध है $\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$, लेकिन किसी अन्य स्ट्रिंग के लिए नहीं।