أحادي التاريخ

في الرياضيات وعلوم الحاسوب ، يُعدّ " المونويد التاريخي" طريقةً لتمثيل تاريخ العمليات الحاسوبية المتزامنة كمجموعة من السلاسل النصية ، حيث تمثل كل سلسلة تاريخًا فرديًا لعمليةٍ ما. يوفر المونويد التاريخي مجموعةً من أدوات التزامن الأساسية (مثل الأقفال ، والمؤشرات المتبادلة ، وربط الخيوط ) لتوفير نقاط التقاء بين مجموعة من العمليات أو الخيوط التي تُنفّذ بشكلٍ مستقل .

تظهر أحاديات التاريخ في نظرية الحوسبة المتزامنة ، وتوفر أساسًا رياضيًا منخفض المستوى لحسابات العمليات ، مثل لغة CSP (لغة العمليات المتسلسلة المتصلة )، أو حساب CCS ( حساب الأنظمة المتصلة) . وقد قدم إم دبليو شيلدز أحاديات التاريخ لأول مرة. ^{[ 1 ]}

تتشابه أحاديات التاريخ مع أحاديات التتبع ( أحاديات التبادل الجزئي الحرة ) ومع أحاديات مخططات التبعية . وبذلك، فهي كائنات حرة وعالمية . تُعد أحاديات التاريخ نوعًا من الضرب الفئوي شبه التبديلي في فئة الأحاديات.

يترك

${\displaystyle A=(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$

يرمز إلى مجموعة من n أبجديات (ليست بالضرورة منفصلة مثنى مثنى)${\displaystyle \Sigma _{k}}$. يترك${\displaystyle P(A)}$تشير إلى جميع التركيبات الممكنة لسلسلة واحدة ذات طول محدود من كل أبجدية:

${\displaystyle P(A)=\Sigma _{1}^{*}\times \Sigma _{2}^{*}\times \cdots \times \Sigma _{n}^{*}}$

(بلغة أكثر رسمية،${\displaystyle P(A)}$هو حاصل الضرب الديكارتي للأحاديات الحرة لـ${\displaystyle \Sigma _{k}}$النجمة المرتفعة هي نجمة كلين . التركيب في أحادي المنتج يكون على أساس المكونات، بحيث يكون، بالنسبة لـ

${\displaystyle \mathbf {u} =(u_{1},u_{2},\ldots ,u_{n})\,}$

و

${\displaystyle \mathbf {v} =(v_{1},v_{2},\ldots ,v_{n})\,}$

ثم

${\displaystyle \mathbf {uv} =(u_{1}v_{1},u_{2}v_{2},\ldots ,u_{n}v_{n})\,}$

للجميع${\displaystyle \mathbf {u} ,\mathbf {v} }$في${\displaystyle P(A)}$عرّف أبجدية الاتحاد على النحو التالي:

${\displaystyle \Sigma =\Sigma _{1}\cup \Sigma _{2}\cup \cdots \cup \Sigma _{n}.\,}$

(الاتحاد هنا هو اتحاد المجموعات ، وليس الاتحاد المنفصل .) بالنظر إلى أي سلسلة${\displaystyle w\in \Sigma ^{*}}$يمكننا أن نختار الحروف فقط في بعض${\displaystyle \Sigma _{k}^{*}}$باستخدام إسقاط السلسلة المقابل${\displaystyle \pi _{k}:\Sigma ^{*}\to \Sigma _{k}^{*}}$توزيع​${\displaystyle \pi$ :\Sigma ^{*}\to P(A)} هو التطبيق الذي يعمل على${\displaystyle w\in \Sigma ^{*}}$مع كل${\displaystyle \pi _{k}}$، بفصلها إلى مكونات في كل مونيد حر:

${\displaystyle \pi (w)\mapsto (\pi _{1}(w),\pi _{2}(w),\ldots ,\pi _{n}(w)).\,}$

لكل${\displaystyle a\in \Sigma }$، المجموعة${\displaystyle \pi (a)}$يُطلق عليه التاريخ الأولي للحرف a . وهو بمثابة مؤشر على إدراج الحرف a في الأبجدية.${\displaystyle \Sigma _{k}}$. إنه،

${\displaystyle \pi (a)=(a_{1},a_{2},\ldots ,a_{n})}$

أين

${\displaystyle a_{k}={\begin{cases}a{\mbox{ إذا }}a\in \Sigma _{k}\\\varepsilon {\mbox{ خلاف ذلك }}.\end{cases}}}$

هنا،${\displaystyle \varepsilon }$يشير إلى السلسلة الفارغة . أحادي التاريخ${\displaystyle H(A)}$هو شبه أحادي من أحادي الضرب${\displaystyle P(A)}$تم إنشاؤها بواسطة التواريخ الأولية:${\displaystyle H(A)=\{\pi (a)|a\in \Sigma \}^{*}}$(حيث يمثل النجم العلوي نجمة كلين المطبقة بتعريف التركيب المكون من عناصره كما هو موضح أعلاه). عناصر ${\displaystyle H(A)}$تُسمى هذه التواريخ بالتواريخ العالمية ، وتُسمى توقعات التاريخ العالمي بالتواريخ الفردية .

يمكن فهم استخدام كلمة " التاريخ" في هذا السياق، وارتباطها بالحوسبة المتزامنة، على النحو التالي: التاريخ الفردي هو سجل لتسلسل حالات عملية (أو خيط أو آلة )؛ الأبجدية${\displaystyle \Sigma _{k}}$هي مجموعة حالات العملية.

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

لنأخذ على سبيل المثال،${\displaystyle \Sigma _{1}=\{a,b,c\}}$و${\displaystyle \Sigma _{2}=\{a,d,e\}}$الأبجدية الموحدة هي بالطبع${\displaystyle \Sigma =\{a,b,c,d,e\}}$. التواريخ الأولية هي${\displaystyle (a,a)}$،${\displaystyle (b,\varepsilon )}$،${\displaystyle (c,\varepsilon )}$،${\displaystyle (\varepsilon ,d)}$و${\displaystyle (\varepsilon ,e)}$في هذا المثال، قد يكون التاريخ الفردي للعملية الأولى كما يلي:${\displaystyle bcbcc}$بينما قد يكون التاريخ الفردي للآلة الثانية${\displaystyle ddded}$يمثل التاريخ العالمي كلا التاريخين الفرديين.${\displaystyle bcbdddcced}$لأن إسقاط هذه السلسلة على الأبجديات الفردية ينتج عنه تواريخ فردية. في التاريخ العالمي، الحروف${\displaystyle b}$و${\displaystyle c}$يمكن اعتبار التنقل باستخدام الرسائل${\displaystyle d}$و${\displaystyle e}$بمعنى أنه يمكن إعادة ترتيب هذه العمليات دون تغيير سجلاتها الفردية. هذا التبديل هو ببساطة بيان بأن العمليتين الأولى والثانية تعملان بالتزامن، وليستا مرتبتين بالنسبة لبعضهما البعض؛ فلم تتبادلا (بعد) أي رسائل أو تجريا أي مزامنة.

الرسالة${\displaystyle a}$يُعدّ بمثابة عنصر أساسي للتزامن، إذ يُشير ظهوره إلى نقطة في التاريخ العالمي والفردي، لا يمكن استبدالها. وبالتالي، بينما الحروف${\displaystyle b}$و${\displaystyle c}$يمكن إعادة ترتيبها بعد${\displaystyle d}$و${\displaystyle e}$لا يمكن إعادة ترتيبها بعد ذلك${\displaystyle a}$وهكذا، التاريخ العالمي${\displaystyle bcdabe}$والتاريخ العالمي${\displaystyle bdcaeb}$لكل منهما تاريخه الخاص${\displaystyle bcab}$و${\displaystyle dae}$مما يشير إلى أن تنفيذ${\displaystyle d}$قد يحدث ذلك قبل أو بعد${\displaystyle c}$ومع ذلك، فإن الرسالة${\displaystyle a}$تتم عملية المزامنة، بحيث${\displaystyle e}$من المؤكد حدوث ذلك بعد${\displaystyle c}$، بالرغم من${\displaystyle e}$يخضع لعملية مختلفة عن${\displaystyle c}$.

المونويد التاريخي متماثل مع المونويد الأثري ، وعلى هذا النحو، فهو نوع من أنواع الضرب الفئوي شبه التبديلي في فئة المونويدات. على وجه الخصوص، المونويد التاريخي${\displaystyle H(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$متماثل مع أحادي الأثر${\displaystyle \mathbb {M} (D)}$مع علاقة التبعية المعطاة بواسطة

${\displaystyle D=\left(\Sigma _{1}\times \Sigma _{1}\right)\cup \left(\Sigma _{2}\times \Sigma _{2}\right)\cup \cdots \cup \left(\Sigma _{n}\times \Sigma _{n}\right).}$

ببساطة، هذا مجرد بيان رسمي للمناقشة غير الرسمية المذكورة أعلاه: حروف الأبجدية${\displaystyle \Sigma _{k}}$يمكن إعادة ترتيبها بشكل تبادلي بعد حروف الأبجدية${\displaystyle \Sigma _{j}}$إلا إذا كانت حروفاً تظهر في كلا الأبجديتين. وبالتالي، فإن الآثار هي تاريخ عالمي بالضبط، والعكس صحيح.

على العكس من ذلك، بالنظر إلى أي مونويد أثري${\displaystyle \mathbb {M} (D)}$يمكن للمرء أن يبني أحادي تاريخي متماثل عن طريق أخذ سلسلة من الأبجديات${\displaystyle \Sigma _{a,b}=\{a,b\}}$أين${\displaystyle (a,b)}$نطاقات على جميع الأزواج في${\displaystyle D}$.

• أنطوني مازوركيويتش، "مقدمة في نظرية الأثر"، الصفحات 3-41، في كتاب الآثار ، تحرير ف. ديكرت وج. روزنبرغ (1995)، دار النشر العالمية، سنغافورة، رقم ISBN 981-02-2058-8
• فولكر ديكرت، إيف ميتيفيه، " التبديل الجزئي والآثار "، في جي. روزنبرغ وأ . سالوما ، محررين، دليل اللغات الرسمية ، المجلد 3 ، ما وراء الكلمات، الصفحات 457-534. سبرينغر-فيرلاغ، برلين، 1997.