مخطط السلسلة

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

أعطى غونتر هوتز أول تعريف رياضي لمخططات الأوتار من أجل إضفاء الطابع الرسمي على الدوائر الإلكترونية . ^[1] ومع ذلك، فإن اختراع مخططات الأوتار يُنسب عادةً إلى روجر بينروز ، ^[2] مع وصف مخططات فاينمان أيضًا بأنها مقدمة. ^[3] تم وصفها لاحقًا بأنها أسهم الفئات الأحادية الحرة في مقال رائد بقلم أندريه جويال وروس ستريت . ^[4] في حين تم رسم المخططات في هذه المقالات الأولى يدويًا، فإن ظهور برامج الطباعة مثل LaTeX و PGF / TikZ جعل نشر مخططات الأوتار أكثر انتشارًا. ^[5]

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

تتكون مخططات الأوتار من صناديق تمثل العمليات ، مع قائمة من الأسلاك الواردة في الأعلى والأسفل ، والتي تمثل أنظمة الإدخال والإخراج التي تتم معالجتها بواسطة الصندوق . بدءًا من مجموعة من الأسلاك والصناديق، والتي تسمى التوقيع ، يمكن للمرء إنشاء مجموعة من جميع مخططات الأوتار عن طريق الاستدلال: ${\displaystyle f:x\to y}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle f}$

• كل مربع هو عبارة عن رسم تخطيطي لسلسلة،${\displaystyle f:x\to y}$
• لكل قائمة من الأسلاك ، تكون الهوية عبارة عن رسم تخطيطي للسلسلة يمثل العملية التي لا تفعل شيئًا لنظام الإدخال الخاص بها، ويتم رسمها كمجموعة من الأسلاك المتوازية،${\displaystyle x}$ ${\displaystyle {\text{id}}(x):x\to x}$
• لكل زوج من مخططات السلاسل و ، فإن موترهما هو مخطط سلسلة يمثل التركيب المتوازي للعمليات، ويتم رسمه كتسلسل أفقي للمخططين،${\displaystyle f:x\to y}$${\displaystyle f':x'\to y'}$ ${\displaystyle f\otimes f':xx'\to yy'}$
• بالنسبة لكل زوج من مخططات السلاسل و ، فإن تركيبهما عبارة عن مخطط سلسلة يمثل التركيب المتسلسل للعمليات، ويتم رسمه كتسلسل رأسي للمخططين.${\displaystyle f:x\to y}$${\displaystyle g:y\to z}$ ${\displaystyle g\circ f:x\to z}$

دع نجمة كليين تشير إلى المونويد الحر ، أي مجموعة القوائم التي تحتوي على عناصر في مجموعة . ${\displaystyle X^{\star }}$${\displaystyle X}$

يتم إعطاء التوقيع الأحادي بواسطة: ${\displaystyle \سيجما }$

• مجموعة من الكائنات المولدة ، قوائم الكائنات المولدة في تسمى أيضًا أنواعًا ،${\displaystyle \سيجما _{0}}$${\textstyle \Sigma _{0}^{\star }}$
• مجموعة من الأسهم المولدة ، والتي تسمى أيضًا بالمربعات ،${\displaystyle \سيجما _{1}}$
• زوج من الوظائف التي تقوم بتعيين مجال ومجال مشترك لكل مربع، أي أنواع الإدخال والإخراج.${\displaystyle {\text{dom}},{\text{cod}}:\Sigma _{1}\to \Sigma _{0}^{\star }}$

إن شكل التوقيع الأحادي هو زوج من الدوال و المتوافقة مع المجال والمجال المشترك، أي مثل و . وبالتالي نحصل على فئة التوقيعات الأحادية وشكلها. ${\displaystyle F:\Sigma \to \Sigma '}$${\displaystyle F_{0}:\Sigma _{0}\to \Sigma '_{0}}$${\displaystyle F_{1}:\Sigma _{1}\to \Sigma '_{1}}$${\displaystyle {\text{dom}}\circ F_{1}\ =\ F_{0}\circ {\text{dom}}}$${\displaystyle {\text{cod}}\circ F_{1}\ =\ F_{0}\circ {\text{cod}}}$${\displaystyle \mathbf {MonSig} }$

يوجد مُتتابع نسياني يرسل فئة أحادية إلى توقيعه الأساسي ومُتتابع أحادي إلى الشكل الأساسي للتوقيعات، أي أنه ينسى الهوية والتكوين والموتر. يُرسل المُتتابع الحر ، أي المُترافق الأيسر للمُتتابع النسياني، توقيعًا أحاديًا إلى الفئة الأحادية الحرة التي يُنشئها. ${\displaystyle U:\mathbf {MonCat} \to \mathbf {MonSig} }$ ${\displaystyle C_{-}:\mathbf {MonSig} \to \mathbf {MonCat} }$${\displaystyle \سيجما }$ ${\displaystyle C_{\سيجما}}$

المخططات الوترية (مع المولدات من ) هي أسهم في فئة أحادية الشكل الحرة . ^[8] يتم تعريف التفسير في فئة أحادية الشكل بواسطة مُستدِل أحادي الشكل ، والذي يتم تحديده بشكل فريد من خلال الحرية من خلال شكل التوقيعات أحادية الشكل . حدسيًا، بمجرد إعطاء صورة الكائنات المُولدة والسهام، يتم إصلاح صورة كل مخطط يتم إنشاؤه. ${\displaystyle \سيجما }$${\displaystyle C_{\سيجما}}$${\displaystyle D}$${\displaystyle F:C_{\Sigma }\to D}$${\displaystyle F:\Sigma \to U(D)}$

المخطط الطوبولوجي ، والذي يُسمى أيضًا مجمع الخلايا أحادي البعد ، هو مجموعة من فضاء هاوسدورف ، ومجموعة منفصلة مغلقة من العقد ومجموعة من المكونات المتصلة تسمى الحواف ، كل منها متماثل مع فاصل مفتوح مع حدود في و بحيث . ${\displaystyle (\Gamma ,\Gamma _{0},\Gamma _{1})}$ ${\displaystyle \جاما }$ ${\displaystyle \Gamma _{0}\subseteq \Gamma }$ ${\displaystyle \جاما _{1}}$${\displaystyle \جاما _{0}}$${\textstyle \Gamma -\Gamma _{0}=\coprod \Gamma _{1}}$

الرسم البياني المستوي بين عددين حقيقيين مع هو رسم بياني طوبولوجي منتهٍ مضمن في بحيث تكون كل نقطة عقدة أيضًا وتنتمي إلى إغلاق حافة واحدة بالضبط في . تسمى هذه النقاط بالعقد الخارجية ، وهي تحدد المجال والمجال المشترك لمخطط السلسلة، أي قائمة الحواف المتصلة بالحدود العلوية والسفلية. تسمى العقد الأخرى بالعقد الداخلية . ${\displaystyle a,b\in \mathbb {R} }$${\displaystyle a<b}$${\displaystyle \mathbb {R} \times [a,b]}$${\displaystyle x\in \Gamma \ \cap \ \mathbb {R} \times \{a,b\}}$${\displaystyle x\in \Gamma _{0}}$${\displaystyle \جاما _{1}}$${\displaystyle {\text{dom}}(\Gamma ),{\text{cod}}(\Gamma )\in \Gamma _{1}^{\star }}$${\displaystyle f\in \Gamma _{0}\ -\ \{a,b\}\times \mathbb {R} }$

الرسم البياني المستوي هو تقدمي ، ويسمى أيضًا متكئًا ، عندما يكون الإسقاط الرأسي حقنيًا لكل حافة . ​​بديهيًا، تنتقل الحواف في الرسم البياني المستوي التقدمي من الأعلى إلى الأسفل دون الانحناء للخلف. في هذه الحالة، يمكن إعطاء كل حافة اتجاهًا من الأعلى إلى الأسفل مع عقد معينة كمصدر وهدف. يمكن للمرء بعد ذلك تحديد المجال والمجال المشترك لكل عقدة داخلية ، والتي يتم تحديدها من خلال قائمة الحواف التي لها مصدر وهدف. ${\displaystyle e\to [a,b]}$${\displaystyle e\in \Gamma _{1}}$${\displaystyle {\text{dom}}(f),{\text{cod}}(f)\in \Gamma _{1}^{\star }}$${\displaystyle f}$

يكون الرسم البياني المستوي عامًا عندما يكون الإسقاط الرأسي حقنيًا، أي لا توجد عقدتان داخليتان على نفس الارتفاع. في هذه الحالة، يمكن للمرء تحديد قائمة بالعقد الداخلية مرتبة من الأعلى إلى الأسفل. ${\displaystyle \Gamma _{0}-\{a,b\}\times \mathbb {R} \to [a,b]}$${\displaystyle {\text{boxes}}(\Gamma )\in \Gamma _{0}^{\star }}$

يتم تصنيف الرسم البياني المستوي التدريجي باستخدام توقيع أحادي إذا كان مزودًا بزوج من الوظائف من الحواف إلى الكائنات المولدة ومن العقد الداخلية إلى الأسهم المولدة، بطريقة متوافقة مع المجال والمجال المشترك. ${\displaystyle \سيجما }$${\displaystyle v_{0}:\Gamma _{1}\to \Sigma _{0}}$${\displaystyle v_{1}:\Gamma _{0}-\{a,b\}\times \mathbb {R} \to \Sigma _{1}}$

تشوه الرسوم البيانية المستوية هو خريطة مستمرة بحيث ${\displaystyle h:\Gamma \times [0,1]\to [a,b]\times \mathbb {R} }$

• الصورة تحدد رسمًا بيانيًا مستويًا لجميع ،${\displaystyle h(-,t)}$${\displaystyle t\in [0,1]}$
• بالنسبة للجميع ، إذا كانت عقدة داخلية بالنسبة للبعض فهي داخلية بالنسبة للجميع .${\displaystyle x\in \Gamma _{0}}$${\displaystyle h(x,t)}$${\displaystyle t}$${\displaystyle t\in [0,1]}$

التشوه يكون تقدميًا (عامًا، مُسمى) إذا كان تقدميًا (عامًا، مُسمى) لجميع . التشوهات تحفز علاقة تكافؤ مع إذا وفقط إذا كان هناك بعض مع و . مخططات السلاسل هي فئات تكافؤ من الرسوم البيانية المستوية التقدمية المُسمى . في الواقع، يمكن للمرء أن يحدد: ${\displaystyle h(-,t)}$${\displaystyle t\in [0,1]}$${\displaystyle \Gamma \sim \Gamma '}$${\displaystyle h}$${\displaystyle h(-,0)=\Gamma }$${\displaystyle h(-,1)=\Gamma '}$

• مخطط الهوية عبارة عن مجموعة من الحواف المتوازية التي يتم تمييزها بنوع ما ،${\displaystyle {\text{id}}(x)}$${\displaystyle x\in \Sigma _{0}^{\star }}$
• تكوين مخططين كتسلسل رأسي لهما مع المجال المشترك للمخطط الأول المحدد بمجال المخطط الثاني،
• موتر الرسم البياني كتسلسل أفقي لهما.

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

إصلاح توقيع أحادي . يتم تعريف الطبقة على أنها ثلاثية من نوع على اليسار، ومربع في المنتصف ونوع على اليمين. تحتوي الطبقات على مجال ومجال مشترك محددين بطريقة واضحة. يشكل هذا رسمًا بيانيًا متعددًا موجهًا ، يُعرف أيضًا باسم الجعبة ، مع الأنواع كرؤوس والطبقات كحواف. يتم ترميز مخطط السلسلة كمسار في هذا الرسم البياني المتعدد ، أي أنه يتم إعطاؤه بواسطة: ${\displaystyle \سيجما }$${\displaystyle (x,f,y)\in \Sigma _{0}^{\star }\times \Sigma _{1}\times \Sigma _{0}^{\star }=:L(\Sigma )}$${\displaystyle x}$${\displaystyle f}$${\displaystyle y}$${\displaystyle {\text{dom}},{\text{cod}}:L(\Sigma )\to \Sigma _{0}^{\star }}$${\displaystyle د}$

• مجال كنقطة بداية${\displaystyle {\text{dom}}(d)\in \Sigma _{0}^{\star }}$
• طول​${\displaystyle {\text{len}}(د)=n\geq 0}$
• قائمة من${\displaystyle {\text{layers}}(d)=d_{1}\dots d_{n}\in L(\Sigma )}$

بحيث و لجميع . في الواقع، فإن القائمة الصريحة للطبقات زائدة عن الحاجة، يكفي تحديد طول النوع إلى يسار كل طبقة، والمعروف باسم الإزاحة . يتم تعريف تذبذب الرسم البياني حسب النوع على أنه الترابط إلى يمين كل طبقة وبشكل متماثل للتذبذب على اليسار. يمكن للمرء بعد ذلك تعريف: ${\displaystyle {\text{dom}}(d_{1})={\text{dom}}(d)}$${\displaystyle {\text{cod}}(d_{i})={\text{dom}}(d_{i+1})}$${\displaystyle i<n}$ ${\displaystyle d\otimes z}$${\displaystyle d=(x_{1},f_{1},y_{1})\dots (x_{n},f_{n},y_{n})}$${\displaystyle z}$${\displaystyle d\otimes z=(x_{1},f_{1},y_{1}z)\dots (x_{n},f_{n},y_{n}z)}$${\displaystyle z\otimes d}$

• مخطط الهوية مع و ،${\displaystyle {\text{id}}(x)}$${\displaystyle {\text{len}}({\text{id}}(x))=0}$${\displaystyle {\text{dom}}({\text{id}}(x))=x}$
• تكوين مخططين كتسلسل لقائمتهما من الطبقات،
• موتر الرسمين البيانيين باعتباره تركيبة من الشعيرات .${\displaystyle d\otimes d'=d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'}$

لاحظ أنه نظرًا لأن الرسم البياني في شكل عام (أي أن كل طبقة تحتوي على مربع واحد فقط)، فإن تعريف الموتر متحيز بالضرورة: يأتي الرسم البياني الموجود على الجانب الأيسر أعلى من الرسم البياني الموجود على الجانب الأيمن. كان من الممكن اختيار التعريف المعاكس . ${\textstyle d\otimes d'={\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$

يكون الرسمان متساويين (حتى حدود بديهيات الفئات الأحادية) كلما كانا في نفس فئة التكافؤ لعلاقة التطابق التي يولدها المبادل : أي إذا لم تكن الصناديق في طبقتين متتاليتين متصلة، فيمكن تبديل ترتيبها. بديهيًا، إذا لم يكن هناك اتصال بين عمليتين متوازيتين، فإن الترتيب الذي يحدثان به يكون غير ذي صلة. $${\displaystyle d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'\quad =\quad {\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$$

يمكن حل مشكلة الكلمات للفئات الأحادية الحرة، أي تحديد ما إذا كان الرسم البياني المعطى متساويين، في زمن متعدد الحدود . إن المبادل هو نظام إعادة كتابة متلاقٍ لمجموعة فرعية من الرسوم البيانية المتصلة بالحدود ، أي كلما لم يكن للرسوم البيانية المستوية أكثر من مكون متصل واحد غير متصل بالمجال أو المجال المشترك ولا تنطبق حجة إيكمان-هيلتون . ^[9]

الفكرة هي تمثيل الهياكل ذات البعد d بهياكل ذات البعد 2-d ، باستخدام ثنائية بوانكاريه . وبالتالي،

• يتم تمثيل الكائن بواسطة جزء من المستوى،
• يتم تمثيل خلية واحدة بقطعة رأسية - تسمى سلسلة - تفصل المستوى إلى قسمين (الجزء الأيمن يتوافق مع A والجزء الأيسر يتوافق مع B ).${\displaystyle f:A\to B}$
• يتم تمثيل الخلية المكونة من خليتين بواسطة تقاطع السلاسل (السلاسل المقابلة لـ f أعلى الرابط، والسلاسل المقابلة لـ g أسفل الرابط).${\displaystyle \alpha :f\Rightarrow g:A\to B}$

يتوافق التكوين الموازي للخليتين مع التجاور الأفقي للمخططات، ويتوافق التكوين المتسلسل مع التجاور الرأسي للمخططات.

الفئة الأحادية تعادل فئة مكونة من 2 خلية واحدة 0. وبشكل بديهي، فإن الانتقال من الفئات الأحادية إلى الفئتين يعادل إضافة ألوان إلى خلفية مخططات السلاسل.

لنفترض وجود فاصل بين فئتين ، حيث يكون الفاصل الأيسر لـ والتحويلات الطبيعية و هما الوحدة والعدد على التوالي. مخططات الأوتار المقابلة لهذه التحويلات الطبيعية هي: ${\displaystyle (F,G,\eta ,\varepsilon )}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle F:{\mathcal {C}}\leftarrow {\mathcal {D}}}$${\displaystyle G:{\mathcal {C}}\rightarrow {\mathcal {D}}}$ ${\displaystyle \eta :I\rightarrow GF}$${\displaystyle \varepsilon :FG\rightarrow I}$

يتم رسم السلسلة المقابلة لمتغير الهوية كخط منقط ويمكن حذفها. يتطلب تعريف المضاف المساواة التالية:

${\displaystyle {\begin{aligned}(\varepsilon F)\circ F(\eta )&=1_{F}\\G(\varepsilon )\circ (\eta G)&=1_{G}\end{aligned}}}$

الأول يصور على أنه

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

في سياق ميكانيكا الكم التصنيفية ، يُعرف هذا باسم معادلة الثعبان .

فئة فضاءات هيلبرت جامدة، وهذه الحقيقة تكمن وراء إثبات صحة بروتوكول النقل الآني الكمومي . وحدة وكونت الإضافة هما تجريد لحالة بيل وقياس بيل على التوالي. إذا تقاسم أليس وبوب اثنين من البتات الكمومية Y وZ في حالة متشابكة وأجرت أليس قياسًا متشابكًا ( محددًا لاحقًا ) بين Y وبت كمومي آخر X، فسيتم نقل هذا البت الكمومي X من أليس إلى بوب: النقل الآني الكمومي هو شكل هوية.

تظهر نفس المعادلة في تعريف قواعد ما قبل المجموعة حيث تلتقط مفهوم تدفق المعلومات في دلالات اللغة الطبيعية . وقد أدت هذه الملاحظة إلى تطوير إطار عمل DisCoCat ومعالجة اللغة الطبيعية الكمومية .

تم تقديم العديد من امتدادات مخططات الأوتار لتمثيل الأسهم في فئات أحادية الشكل مع بنية إضافية، مما يشكل تسلسلًا هرميًا للغات الرسومية المصنفة في مسح سيلنجر للغات الرسومية للفئات أحادية الشكل. ^[10]

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

لقد تم استخدام المخططات الوترية لصياغة أهداف الدراسة التالية.

• نظرية التزامن ^[11]
• الشبكات العصبية الاصطناعية ^[12]
• نظرية اللعبة ^[13]
• احتمالية بايزية ^[14]
• الوعي ^[15]
• نوى ماركوف ^[16]
• الرسوم البيانية لتدفق الإشارة ^[17]
• الاستعلامات الوصلية ^[18]
• التحويلات ثنائية الاتجاه ^[19]
• ميكانيكا الكم التصنيفية
• الدوائر الكمومية ، والحوسبة الكمومية القائمة على القياس وتصحيح الأخطاء الكمومية ، انظر حساب ZX
• معالجة اللغة الطبيعية ، انظر DisCoCat
• معالجة اللغة الطبيعية الكمومية

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

• TheCatsters (2007). String diagrams 1 (streamed video) . Youtube. مؤرشف من الأصل في 2021-12-19.
• مخططات الأوتار في مختبر n
• DisCoPy، مجموعة أدوات Python للحوسبة باستخدام مخططات السلسلة

• الوسائط ذات الصلة بـ String diagram في ويكيميديا ​​كومنز