علاقة التبعية

في علوم الحاسوب ، وتحديدًا في نظرية التزامن ، ^{تُعرَّف} علاقة التبعية بأنها علاقة ثنائية متناظرة وانعكاسية ^{[ 1 ] على} نطاق محدود .${\displaystyle \Sigma }$; ^{[ 1 ] : 4} أي علاقة تسامح محدودة . أي أنها مجموعة محدودة من الأزواج المرتبة${\displaystyle D}$بحيث

• لو${\displaystyle (a,b)\in D}$ ثم ${\displaystyle (b,a)\in D}$(متماثل)
• لو${\displaystyle a\in \Sigma }$، ثم ${\displaystyle (a,a)\in D}$(انعكاسي)

بشكل عام، علاقات التبعية ليست متعدية ؛ وبالتالي، فهي تعمم مفهوم علاقة التكافؤ عن طريق التخلي عن التعدي.

${\displaystyle \Sigma }$ويُطلق عليه أيضًا اسم الأبجدية التي${\displaystyle D}$يتم تعريفها. الاستقلالية الناتجة عن${\displaystyle D}$هي العلاقة الثنائية${\displaystyle I}$

${\displaystyle I=(\Sigma \times \Sigma )\setminus D}$

أي أن الاستقلال هو مجموعة جميع الأزواج المرتبة التي ليست في${\displaystyle D}$العلاقة المستقلة متناظرة وغير انعكاسية. وعلى العكس من ذلك، بالنظر إلى أي علاقة متناظرة وغير انعكاسية${\displaystyle I}$في أبجدية محدودة، العلاقة

${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$

هي علاقة تبعية.

الزوجان${\displaystyle (\Sigma ,D)}$يُطلق عليه اسم الأبجدية المتزامنة . ^{[ 2 ] : 6} الزوج${\displaystyle (\Sigma ,I)}$يُطلق عليها اسم أبجدية الاستقلال أو أبجدية الاعتماد ، ولكن قد يشير هذا المصطلح أيضًا إلى الثلاثية${\displaystyle (\Sigma ,D,I)}$(مع${\displaystyle I}$ناتج عن${\displaystyle D}$). ^{[ 3 ] : 6} عناصر${\displaystyle x,y\in \Sigma }$تُسمى تابعة إذا${\displaystyle xDy}$إذا كان الأمر كذلك، ومستقلًا ، وإلا (أي إذا${\displaystyle xIy}$(يحمل). ^{[ 1 ] : 6}

بالنظر إلى أبجدية الاعتماد${\displaystyle (\Sigma ,D,I)}$علاقة متناظرة وغير انعكاسية${\displaystyle \doteq }$يمكن تعريفها على المونويد الحر${\displaystyle \Sigma ^{*}}$من بين جميع السلاسل الممكنة ذات الطول المحدود بواسطة:${\displaystyle xaby\doteq xbay}$لجميع السلاسل${\displaystyle x,y\in \Sigma ^{*}}$وجميع الرموز المستقلة${\displaystyle a,b\in I}$إغلاق التكافؤ لـ${\displaystyle \doteq }$يُشار إليه بـ${\displaystyle \equiv }$أو${\displaystyle \equiv _{(\Sigma ,D,I)}}$ودعا${\displaystyle (\Sigma ,D,I)}$التكافؤ. بشكل غير رسمي،${\displaystyle p\equiv q}$يتحقق الشرط إذا كانت السلسلة${\displaystyle p}$يمكن تحويلها إلى${\displaystyle q}$عن طريق سلسلة محدودة من عمليات تبديل الرموز المستقلة المتجاورة. فئات التكافؤ لـ${\displaystyle \equiv }$وتسمى الآثار ، ^{[ 1 ] : 7-8} ويتم دراستها في نظرية الآثار .

بالنظر إلى الأبجدية${\displaystyle \Sigma =\{a,b,c\}}$، ومن العلاقات المحتملة للتبعية ما يلي:${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}$انظر الصورة.

الاستقلال المقابل هو${\displaystyle I=\{(b,c),\,(c,b)\}}$ثم على سبيل المثال الرموز${\displaystyle b,c}$مستقلة عن بعضها البعض، على سبيل المثال${\displaystyle a,b}$يعتمدان على بعضهما البعض. السلسلة${\displaystyle acbba}$يعادل${\displaystyle abcba}$وإلى${\displaystyle abbca}$ولكن ليس لأي وتر آخر.