أحادي الأثر

في علم الحاسوب ، يُعرف الأثر بأنه فئة تكافؤ للسلاسل النصية ، حيث يُسمح لبعض الأحرف في السلسلة بالتبديل ، بينما لا يُسمح لغيرها بذلك. تُعمم الآثار مفهوم السلاسل النصية بتخفيف شرط الترتيب المحدد لجميع الأحرف، مما يسمح بترتيبات غير محددة يمكن فيها إجراء بعض عمليات إعادة الترتيب. وعلى النقيض من ذلك، تُعمم الآثار مفهوم المجموعات ذات التعددية بالسماح بتحديد ترتيب غير كامل للأحرف بدلاً من اشتراط التكافؤ الكامل في جميع عمليات إعادة الترتيب. يُعرف أحادي الأثر، أو أحادي التبادل الجزئي الحر، بأنه أحادي الآثار.

تم تقديم مفهوم التتبعات بواسطة بيير كارتييه ودومينيك فواتا في عام 1969 لتقديم برهان توافقي لنظرية ماكماهون الرئيسية . تُستخدم التتبعات في نظريات الحوسبة المتزامنة ، حيث تمثل الأحرف المتبادلة أجزاءً من مهمة يمكن تنفيذها بشكل مستقل عن بعضها البعض، بينما تمثل الأحرف غير المتبادلة الأقفال أو نقاط التزامن أو وصلات الخيوط . ^{[ 1 ]}

يُبنى أحادي الأثر من أحادي الحرية (مجموعة جميع السلاسل ذات الطول المحدود) كما يلي: أولًا، تُعطى مجموعات الأحرف المتبادلة بعلاقة استقلال . تُنشئ هذه العلاقات علاقة تكافؤ بين السلاسل المتكافئة؛ عناصر فئات التكافؤ هي الآثار. ثم تُقسّم علاقة التكافؤ عناصر أحادي الحرية إلى مجموعة من فئات التكافؤ؛ والنتيجة لا تزال أحاديًا؛ وهو أحادي خارج القسمة يُسمى الآن أحادي الأثر . أحادي الأثر شامل ، بمعنى أن جميع الأحاديات المتماثلة تبعيًا (انظر أدناه) متماثلة في الواقع .

تُستخدم أحاديات التتبع بشكل شائع لنمذجة الحوسبة المتزامنة ، وتشكل أساس حسابات العمليات . وهي موضوع دراسة في نظرية التتبع . تكمن فائدة أحاديات التتبع في كونها متماثلة مع أحاديات مخططات التبعية ؛ مما يسمح بتطبيق التقنيات الجبرية على المخططات ، والعكس صحيح. كما أنها متماثلة مع أحاديات التاريخ ، التي تُنمذج تاريخ حساب العمليات الفردية في سياق جميع العمليات المجدولة على جهاز حاسوب واحد أو أكثر.

يترك${\displaystyle \Sigma ^{*}}$يرمز إلى الزمرة الحرة على مجموعة من المولدات${\displaystyle \Sigma }$أي مجموعة جميع السلاسل المكتوبة بالأبجدية${\displaystyle \Sigma }$النجمة هي رمز قياسي لنجمة كلين . علاقة استقلال${\displaystyle I}$حول الأبجدية${\displaystyle \Sigma }$ثم يُحدث علاقة ثنائية متناظرة${\displaystyle \sim }$على مجموعة السلاسل${\displaystyle \Sigma ^{*}}$سلسلتان${\displaystyle u,v}$مترابطة، ${\displaystyle u\sim v,}$إذا وفقط إذا كان هناك${\displaystyle x,y\in \Sigma ^{*}}$وزوج${\displaystyle (a,b)\in I}$بحيث${\displaystyle u=xaby}$و${\displaystyle v=xbay}$. هنا،${\displaystyle u,v,x}$و${\displaystyle y}$يُفهم أنها سلاسل نصية (عناصر من${\displaystyle \Sigma ^{*}}$)، بينما${\displaystyle a}$و${\displaystyle b}$هي حروف (عناصر من${\displaystyle \Sigma }$).

يُعرَّف الأثر بأنه الإغلاق الانعكاسي المتعدي لـ${\displaystyle \sim }$وبالتالي، فإن الأثر هو علاقة تكافؤ على${\displaystyle \Sigma ^{*}}$ويرمز إليه بـ${\displaystyle \equiv _{D}}$، أين${\displaystyle D}$هل علاقة التبعية المقابلة لـ${\displaystyle I.}$${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$و${\displaystyle I=(\Sigma \times \Sigma )\setminus D.}$ستؤدي العلاقات المستقلة أو التابعة المختلفة إلى علاقات تكافؤ مختلفة.

يشير الإغلاق المتعدي إلى أن${\displaystyle u\equiv _{D}v}$إذا وفقط إذا وُجدت سلسلة من السلاسل النصية${\displaystyle (w_{0},w_{1},\cdots ,w_{n})}$بحيث${\displaystyle u\sim w_{0},}$${\displaystyle v\sim w_{n},}$و${\displaystyle w_{i}\sim w_{i+1}}$للجميع${\displaystyle 0\leq i<n}$يكون الأثر مستقرًا تحت عملية المونويد على${\displaystyle \Sigma ^{*}}$أي، التسلسل ، و${\displaystyle \equiv _{D}}$وبالتالي، فهي علاقة تطابق على${\displaystyle \Sigma ^{*}.}$

أحادي الأثر، والذي يُشار إليه عادةً باسم${\displaystyle \mathbb {M} (D)}$، تُعرَّف بأنها أحادي القسمة

${\displaystyle \mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.}$

التماثل

${\displaystyle \phi _{D}:\Sigma ^{*}\to \mathbb {M} (D)}$

يُشار إليه عادةً باسم التشاكل الطبيعي أو التشاكل القانوني . وتستند تسمية "طبيعي" أو "قانوني" إلى حقيقة أن هذا التشاكل يجسد خاصية شاملة، كما سيتم توضيحه في قسم لاحق.

سيجد المرء أيضًا أحادي الأثر المشار إليه بـ${\displaystyle M(\Sigma ,I)}$أين${\displaystyle I}$هي علاقة الاستقلال. يمكن أيضًا إيجاد علاقة التبديل المستخدمة بدلاً من علاقة الاستقلال؛ وهي تختلف عن علاقة الاستقلال في أنها تشمل أيضًا جميع العناصر القطرية لـ${\textstyle \Sigma \times \Sigma }$لأن الحروف "تتبادل مع نفسها" في مجموعة أحادية حرة من سلاسل تلك الحروف.

لنأخذ الأبجدية كمثال${\displaystyle \Sigma =\{a,b,c\}}$إحدى علاقات التبعية المحتملة هي

${\displaystyle {\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}.\end{matrix}}}$

الاستقلال المقابل هو

${\displaystyle I_{D}=\{(b,c)\,,\,(c,b)\}.}$

لذلك، فإن الحروف${\displaystyle b,c}$التنقل. وبالتالي، على سبيل المثال، فئة تكافؤ التتبع للسلسلة${\displaystyle abababbca}$سيكون

${\displaystyle [abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;abababcba\}}$

وفئة التكافؤ${\displaystyle [abababbca]_{D}}$سيكون عنصرًا من عناصر أحادي الأثر.

تنص خاصية الإلغاء على أن التكافؤ يبقى قائماً في ظل الإلغاء الصحيح . أي، إذا${\displaystyle w\equiv v}$، ثم${\displaystyle (w\div a)\equiv (v\div a)}$هنا، الترميز${\displaystyle w\div a}$يشير إلى الحذف من اليمين، أي إزالة أول ظهور للحرف a من السلسلة w ، بدءًا من الجانب الأيمن. ويُحافظ على التكافؤ أيضًا بالحذف من اليسار. وتترتب على ذلك عدة نتائج:

• التضمين:${\displaystyle w\equiv v}$إذا وفقط إذا${\displaystyle xwy\equiv xvy}$بالنسبة للسلاسل x و y . وبالتالي، فإن أحادي التتبع هو أحادي تركيبي .
• الاستقلال: إذا${\displaystyle ua\equiv vb}$و${\displaystyle a\neq b}$إذن، فإن a مستقل عن b . أي،${\displaystyle (a,b)\in I_{D}}$علاوة على ذلك، توجد سلسلة w بحيث${\displaystyle u\equiv wb}$و${\displaystyle v\equiv wa}$.
• قاعدة الإسقاط: يتم الحفاظ على التكافؤ في ظل إسقاط السلاسل النصية ، بحيث إذا${\displaystyle w\equiv v}$، ثم${\displaystyle \pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)}$.

ينطبق شكل قوي من مبرهنة ليفي على الآثار. تحديدًا، إذا${\displaystyle uv\equiv xy}$بالنسبة للسلاسل u و v و x و y ، توجد سلاسل${\displaystyle z_{1},z_{2},z_{3}}$و${\displaystyle z_{4}}$بحيث${\displaystyle (w_{2},w_{3})\in I_{D}}$ لجميع الرسائل${\displaystyle w_{2}\in \Sigma }$و${\displaystyle w_{3}\in \Sigma }$بحيث${\displaystyle w_{2}}$يحدث في${\displaystyle z_{2}}$و${\displaystyle w_{3}}$يحدث في${\displaystyle z_{3}}$، و

${\displaystyle u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},}$

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$^{[ 2 ]}

التشاكل التابع (بالنسبة إلى تبعية D ) هو تشاكل

${\displaystyle \psi$ :\Sigma ^{*}\to M}

إلى شبه زمرة M ، بحيث تتحقق خصائص الأثر "المعتادة"، وهي:

1.${\displaystyle \psi (w)=\psi (\varepsilon )}$يشير ذلك إلى أن${\displaystyle w=\varepsilon }$

2.${\displaystyle (a,b)\in I_{D}}$يشير ذلك إلى أن${\displaystyle \psi (ab)=\psi (ba)}$

3.${\displaystyle \psi (ua)=\psi (v)}$يشير ذلك إلى أن${\displaystyle \psi (u)=\psi (v\div a)}$

4.${\displaystyle \psi (ua)=\psi (vb)}$و${\displaystyle a\neq b}$يعني ذلك ${\displaystyle (a,b)\in I_{D}}$

تُعتبر تماثلات التبعية عالمية، بمعنى أنه بالنسبة لتبعية معينة وثابتة D ، إذا${\displaystyle \psi$ إذا كان Σ* → M تشاكل تبعية إلى أحادي M ، فإن M متماثل مع أحادي الأثر${\displaystyle \mathbb {M} (D)}$. على وجه الخصوص، فإن التشاكل الطبيعي هو تشاكل تبعية.

هناك شكلان طبيعيان معروفان للكلمات في أحاديات الأثر. أحدهما هو الشكل الطبيعي المعجمي ، الذي يعود الفضل فيه إلى أناتولي ف. أنيسيموف ودونالد كنوث ، والآخر هو الشكل الطبيعي لفواتا الذي يعود الفضل فيه إلى بيير كارتييه ودومينيك فواتا اللذين درسا أحاديات الأثر من أجل تركيبها في الستينيات. ^{[ 3 ]}

يُعدّ شكل التطبيع في Unicode ، وهو التحلل المتعارف عليه (NFD)، مثالاً على الشكل الطبيعي المعجمي - حيث يتمثل الترتيب في فرز الأحرف المتتالية ذات فئة الدمج المتعارف عليها غير الصفرية حسب تلك الفئة.

تمامًا كما يمكن اعتبار اللغة الرسمية مجموعة فرعية من${\displaystyle \Sigma ^{*}}$، وهي مجموعة جميع السلاسل الممكنة، لذا تُعرَّف لغة التتبع على أنها مجموعة فرعية من${\displaystyle \mathbb {M} (D)}$جميع الآثار الممكنة.

أو بدلاً من ذلك، ولكن بشكل مكافئ، لغة${\displaystyle L\subseteq \Sigma ^{*}}$هي لغة تتبع، أو يقال إنها متسقة مع التبعية D إذا

${\displaystyle L=[L]_{D}}$

أين

${\displaystyle [L]_{D}=\bigcup _{w\in L}[w]_{D}}$

هو الإغلاق التتبعي لمجموعة من السلاسل النصية.

• ذاكرة التتبع

مراجع عامة

• ديكيرت، فولكر. ميتيفييه، إيف (1997)، “التخفيف الجزئي والآثار” ، في روزنبرغ، ج.؛ Salomaa, A. (eds.)، دليل اللغات الرسمية المجلد. 3؛ ما وراء الكلمات ، Springer-Verlag، Berlin، pp. 457–534 ، ISBN  3-540-60649-1
• لوثير، م. (2011)، التوافقية الجبرية على الكلمات ، موسوعة الرياضيات وتطبيقاتها، المجلد  90، مع مقدمة بقلم جان بيرستيل ودومينيك بيرين (إعادة طبع  الطبعة ذات الغلاف المقوى لعام 2002)، مطبعة جامعة كامبريدج، ISBN 978-0-521-18071-9Zbl 1221.68183​ 
• أنطوني مازوركيويتش، "مقدمة في نظرية الأثر"، الصفحات 3-41، في كتاب الآثار ، تحرير ف. ديكرت وج. روزنبرغ (1995)، دار النشر العالمية، سنغافورة، رقم ISBN 981-02-2058-8
• فولكر ديكرت، التوافقية على الآثار ، سلسلة محاضرات في علوم الحاسوب 454، سبرينغر، 1990، رقم ISBN 3-540-53031-2، الصفحات  9-29
• ساندور، جوزيف؛ Crstici، Borislav (2004)، دليل نظرية الأعداد II ، Dordrecht: Kluwer Academic، الصفحات من 32 إلى 36، ISBN  1-4020-2546-7، Zbl 1079.11001 

منشورات رائدة

• بيير كارتييه ودومينيك فواتا، مشاكل التجميع وإعادة الترتيب ، ملاحظات محاضرة في الرياضيات 85، سبرينغر-فيرلاغ، برلين، 1969، إعادة طبع مجانية عام 2006 مع ملاحق جديدة
• أنطوني مازوركيويتش، مخططات البرامج المتزامنة وتفسيراتها ، تقرير DAIMI PB 78، جامعة آرهوس، 1977