نظرية كورسيل

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 8 صور
الموسوعة الحرة

في دراسة خوارزميات الرسوم البيانية ، تنص نظرية كورسيل على أن كل خاصية من خصائص الرسم البياني القابلة للتعريف في منطق الرتبة الثانية الأحادي للرسوم البيانية يمكن تحديدها في زمن خطي على الرسوم البيانية ذات عرض الشجرة المحدود . [ 1 ] [ 2 ] [ 3 ] وقد أثبت برونو كورسيل هذه النتيجة لأول مرة عام 1990 [ 4 ] ، ثم أعاد اكتشافها بشكل مستقل كل من بوري وباركر وتوفي (1992) . [ 5 ] وتُعتبر هذه النظرية نموذجًا أوليًا لنظريات ما وراء الخوارزميات . [ 6 ] [ 7 ]

التركيبات

مجموعات الرؤوس

في أحد أشكال منطق الرسم البياني أحادي الدرجة الثانية المعروف باسم MSO 1 ، يتم وصف الرسم البياني بواسطة مجموعة من الرؤوس وعلاقة تجاور ثنائيةصفة⁡(.،.){\displaystyle \operatorname {adj} (.,.)}، ويعني التقييد بالمنطق الأحادي أنه يمكن تعريف خاصية الرسم البياني المعنية من حيث مجموعات رؤوس الرسم البياني المعطى، ولكن ليس من حيث مجموعات الحواف، أو مجموعات صفوف الرؤوس.

على سبيل المثال، خاصية الرسم البياني هي إمكانية تلوينه بثلاثة ألوان (ممثلة بثلاث مجموعات من الرؤوس).R{\displaystyle R}،جي{\displaystyle G}، وب{\displaystyle B}يمكن تعريف ) بواسطة الصيغة الأحادية من الدرجة الثانية ∃R ∃جي ∃ب (∀v (v∈R∨v∈جي∨v∈ب)∧∀u ∀v ((u∈R∧v∈R)→¬صفة⁡(u،v))∧∀u ∀v ((u∈جي∧v∈جي)→¬صفة⁡(u،v))∧∀u ∀v ((u∈ب∧v∈ب)→¬صفة⁡(u،v))){\displaystyle {\begin{aligned}\exists R\ \exists G\ \exists B\ {\Bigl (}&\forall v\ (v\in R\vee v\in G\vee v\in B)\wedge {}\\&\forall u\ \forall v\ {\bigl (}(u\in R\wedge v\in R)\rightarrow \lnot \operatorname {adj} (u,v){\bigr )}\wedge {}\\&\forall u\ \forall v\ {\bigl (}(u\in B\wedge v\in B)\rightarrow \lnot \operatorname {adj} (u,v){\bigr )}{\Bigr )}\end{aligned}}} مع مراعاة اصطلاح التسمية الذي يُشير فيه استخدام الأحرف الكبيرة للدلالة على مجموعات الرؤوس، بينما تُشير الأحرف الصغيرة للدلالة على الرؤوس الفردية (بحيث يُمكن حذف التحديد الصريح لأي منها من الصيغة). يضمن الجزء الأول من هذه الصيغة أن فئات الألوان الثلاث تُغطي جميع رؤوس الرسم البياني، بينما يضمن الجزء المتبقي أن كل فئة تُشكل مجموعة مستقلة . (يُمكن أيضًا إضافة بنود إلى الصيغة لضمان أن فئات الألوان الثلاث منفصلة، ​​ولكن هذا لا يُؤثر على النتيجة). وبالتالي، وفقًا لنظرية كورسيل، يُمكن اختبار إمكانية تلوين الرسوم البيانية ذات عرض الشجرة المحدود بثلاثة ألوان في وقت خطي.

بالنسبة لهذا النوع من منطق الرسم البياني، يمكن تعميم نظرية كورسيل من عرض الشجرة إلى عرض الزمرة : لكل خاصية MSO 1 ثابتةΠ{\displaystyle \Pi }وكل حد ثابتب{\displaystyle b}بناءً على عرض الزمرة في الرسم البياني، توجد خوارزمية خطية لاختبار ما إذا كان الرسم البياني ذو عرض الزمرة على الأكثرب{\displaystyle b}يمتلك عقارًاΠ{\displaystyle \Pi }[ 8 ] تطلبت الصيغة الأصلية لهذه النتيجة تقديم الرسم البياني المدخل مع بناء يثبت أن له عرض زمرة محدود، ولكن خوارزميات التقريب اللاحقة لعرض الزمرة أزالت هذا الشرط. [ 9 ]

مجموعات الحواف

يمكن أيضًا استخدام نظرية كورسيل مع صيغة أقوى من منطق الرتبة الثانية الأحادي، والمعروفة اختصارًا بـ MSO 2. في هذه الصيغة، يُمثَّل الرسم البياني بمجموعة V من الرؤوس، ومجموعة E من الحواف، وعلاقة وقوع بين الرؤوس والحواف. تسمح هذه الصيغة بالقياس الكمي على مجموعات الرؤوس أو الحواف، ولكن ليس على العلاقات الأكثر تعقيدًا بين أزواج الرؤوس أو الحواف.

على سبيل المثال، يمكن التعبير عن خاصية وجود دورة هاميلتونية في MSO 2 بوصف الدورة بأنها مجموعة من الحواف التي تتضمن حافتين متصلتين بكل رأس، بحيث تحتوي كل مجموعة جزئية غير فارغة من الرؤوس على حافة في الدورة المفترضة لها نقطة نهاية واحدة فقط في المجموعة الجزئية. مع ذلك، لا يمكن التعبير عن خاصية الهاميلتونية في MSO 1. [ 10 ]

الرسوم البيانية المصنفة

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

التوافقات المعيارية

ثمة اتجاه آخر لتوسيع نظرية كورسيل يتعلق بالصيغ المنطقية التي تتضمن محمولات لحساب حجم الاختبار. في هذا السياق، لا يمكن إجراء عمليات حسابية عشوائية على أحجام المجموعات، ولا حتى اختبار ما إذا كانت مجموعتان لهما نفس الحجم. ومع ذلك، يمكن توسيع منطق MSO 1 و MSO 2 إلى منطقين يُطلق عليهما CMSO 1 و CMSO 2 ، واللذان يتضمنان لكل ثابتين q و r محمولًا.بطاقةq،ر⁡(S){\displaystyle \operatorname {card} _{q,r}(S)}والتي تختبر ما إذا كانت عناصر المجموعة S متطابقة مع r modulo q . يمكن تعميم نظرية كورسيل على هذه المنطق . [ 4 ] 

القرار مقابل التحسين

كما ذُكر سابقًا، تنطبق نظرية كورسيل بشكل أساسي على مسائل القرار : هل يمتلك الرسم البياني خاصية معينة أم لا؟ مع ذلك، تسمح نفس الأساليب أيضًا بحل مسائل التحسين التي تكون فيها رؤوس أو حواف الرسم البياني ذات أوزان صحيحة، ويسعى الباحث إلى إيجاد مجموعة الرؤوس ذات الوزن الأدنى أو الأقصى التي تحقق خاصية معينة، مُعبرًا عنها بمنطق الرتبة الثانية. يمكن حل مسائل التحسين هذه في وقت خطي على الرسوم البيانية ذات عرض الزمرة المحدود. [ 8 ] [ 11 ]

تعقيد المساحة

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

استراتيجية الإثبات والتعقيد

يتضمن النهج المعتاد لإثبات نظرية كورسيل بناء آلة شجرية محدودة من الأسفل إلى الأعلى تعمل على تفكيكات الشجرة للرسم البياني المعطى. [ 6 ]

بتفصيلٍ أكبر، يمكن تعريف رسمين بيانيين G1 و G2 ، لكلٍ منهما مجموعة فرعية محددة T من الرؤوس تُسمى رؤوسًا طرفية، على أنهما متكافئان بالنسبة لصيغة MSO، F ، إذا كان ، بالنسبة لجميع الرسوم البيانية الأخرى H التي يتكون تقاطعها مع G1 و G2 من رؤوس في T فقط ، يتصرف الرسمان البيانيان G1 ∪ H و G2 ∪ H بنفس الطريقة بالنسبة لـ F : إما أنهما يمثلان F معًا أو لا يمثلان F معًا . هذه علاقة تكافؤ ، ويمكن إثباتها بالاستقراء على طول F (عندما يكون حجم كل من T و F محدودًا) أن لها عددًا محدودًا من فئات التكافؤ . [ 13 ]    

يتكون تجزئة الشجرة للرسم البياني G من شجرة، ولكل عقدة في الشجرة، مجموعة فرعية من رؤوس G تُسمى "حقيبة". يجب أن تستوفي هذه الحقيبة خاصيتين: لكل رأس v في G ، يجب أن تكون الحقائب التي تحتوي على v مرتبطة بشجرة فرعية متصلة من الشجرة، ولكل حافة uv في G ، يجب أن تكون هناك حقيبة تحتوي على كل من u و v . يمكن اعتبار الرؤوس في الحقيبة بمثابة نهايات رسم بياني فرعي من G ، ممثل بالشجرة الفرعية لتجزئة الشجرة المنحدرة من تلك الحقيبة. عندما يكون عرض الشجرة في G محدودًا، يكون لها تجزئة شجرة تكون فيها جميع الحقائب ذات حجم محدود، ويمكن إيجاد مثل هذه التجزئة في وقت قابل للمعالجة بمعاملات ثابتة. [ 14 ] علاوة على ذلك، من الممكن اختيار تجزئة الشجرة هذه بحيث تُشكل شجرة ثنائية ، مع شجرتين فرعيتين فقط لكل حقيبة. لذلك، من الممكن إجراء عملية حسابية من الأسفل إلى الأعلى على هذا التفكيك الشجري، وذلك بحساب مُعرِّف لفئة التكافؤ للشجرة الفرعية المتأصلة في كل مجموعة عن طريق دمج الحواف المُمثلة داخل المجموعة مع مُعرِّفي فئتي التكافؤ لأبنائها. [ 15 ]

إن حجم الآلة المُنشأة بهذه الطريقة ليس دالة أساسية لحجم صيغة MSO المُدخلة. هذا التعقيد غير الأساسي ضروري، بمعنى أنه (ما لم يكن P = NP ) لا يمكن اختبار خصائص MSO على الأشجار في وقت يمكن حسابه باستخدام معلمات ثابتة مع اعتماد أساسي على المعلمة. [ 16 ]

يعتمد نهج بديل على تحويل مشكلة التحقق من النموذج إلى حالة من مشكلة الإرضاء المنطقي ، وذلك بتوجيه عملية التحويل بعناية على طول تجزئة شجرية للحفاظ على تضخم عرض الشجرة عند أدنى حد ممكن. ونتيجةً لذلك، نحصل على حدود عليا دقيقة تقريبًا لوقت التشغيل في ظل فرضية الزمن الأسي . في الواقع، من المتوقع أن يكون ارتفاع البرج الناتج (بوحدة عدد تبديلات المُكمِّم) لحدود وقت التشغيل مثاليًا. [ 17 ] باستبدال خوارزمية البرمجة الديناميكية الأساسية لمشكلة الإرضاء المنطقي بخوارزمية لمشكلة الإرضاء القصوى أو ♯SAT ، نحصل مباشرةً على حدود عليا مقابلة لوقت التشغيل لنسخة التحسين أو نسخة العد، على التوالي.

نظرية Bojańczyk-Pilipczuk

تُظهر براهين نظرية كورسيل نتيجةً أقوى: لا يُمكن فقط التعرّف على كل خاصية من خصائص الرتبة الثانية الأحادية (العدّية) في زمن خطي للرسوم البيانية ذات عرض الشجرة المحدود، بل يُمكن أيضًا التعرّف عليها بواسطة آلة شجرية ذات حالات محدودة . افترض كورسيل عكس ذلك: إذا تم التعرّف على خاصية من خصائص الرسوم البيانية ذات عرض الشجرة المحدود بواسطة آلة شجرية، فإنه يُمكن تعريفها في منطق الرتبة الثانية الأحادي العدّي. في عام 1998، ادّعى لابوار (1998) حلّ هذا الافتراض. [ 18 ] ومع ذلك، يُعتبر البرهان على نطاق واسع غير مُرضٍ. [ 19 ] [ 20 ] حتى عام 2016، لم تُحَلّ سوى حالات خاصة قليلة: على وجه الخصوص، تم إثبات الفرضية للرسوم البيانية ذات عرض الشجرة الذي لا يتجاوز ثلاثة، [ 21 ] وللرسوم البيانية المتصلة من الرتبة k ذات عرض الشجرة k، وللرسوم البيانية ذات عرض الشجرة الثابت والوترية الثابتة، وللرسوم البيانية الخارجية المستوية من الرتبة k. وقد أثبت ميكولاي بويانتشيك وميشال بيليبكزوك الصيغة العامة للفرضية في النهاية . [ 22 ]

علاوة على ذلك، بالنسبة لرسوم هالين البيانية (وهي حالة خاصة من الرسوم البيانية ذات عرض الشجرة 3)، لا حاجة للعد: ففي هذه الرسوم البيانية، يمكن تعريف كل خاصية يمكن التعرف عليها بواسطة آلة الشجرة في منطق الرتبة الثانية الأحادي. وينطبق الأمر نفسه بشكل أعم على فئات معينة من الرسوم البيانية التي يمكن وصف تفكيك الشجرة فيها باستخدام منطق الرتبة الثانية الأحادي. مع ذلك، لا ينطبق هذا على جميع الرسوم البيانية ذات عرض الشجرة المحدود، لأن العد، بشكل عام، يضيف قوة إضافية على منطق الرتبة الثانية الأحادي بدون عد. على سبيل المثال، يمكن التعرف على الرسوم البيانية ذات العدد الزوجي من الرؤوس باستخدام العد، ولكن ليس بدونه. [ 20 ]

قابلية الإرضاء ونظرية سيس

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

كنتيجة جزئية عكسية، أثبت سيس (1991) أنه كلما كانت لعائلة من الرسوم البيانية مسألة إرضاء قابلة للتقرير من الدرجة الثانية MSO ، فلا بد أن يكون عرض الشجرة لهذه العائلة محدودًا. ويستند هذا البرهان إلى نظرية روبرتسون وسيمور التي تنص على أن عائلات الرسوم البيانية ذات عرض الشجرة غير المحدود تمتلك قواطع شبكية كبيرة كيفيًا . [ 23 ] كما افترض سيس أن كل عائلة من الرسوم البيانية ذات مسألة إرضاء قابلة للتقرير من الدرجة الأولى MSO يجب أن يكون عرض الزمرة فيها محدودًا؛ لم يُثبت هذا بعد، ولكن ثمة تخفيف لهذا الافتراض يستبدل MSO 1 بـ CMSO 1. [ 24 ]

التطبيقات

استخدم غروه (2001) نظرية كورسيل لإثبات أن حساب عدد التقاطعات في الرسم البياني G قابل للمعالجة بمعاملات ثابتة مع اعتماد تربيعي على حجم G ، مما حسّن خوارزمية ذات زمن تكعيبي مبنية على نظرية روبرتسون-سيمور . وقد اتبع كاواراباياشي وريد (2007) نفس النهج في تحسين لاحق للزمن الخطي . إذا كان الرسم البياني G ذو عرض شجري صغير، يمكن تطبيق نظرية كورسيل مباشرةً على هذه المسألة. من ناحية أخرى، إذا كان G ذو عرض شجري كبير، فإنه يحتوي على شبكة فرعية كبيرة ، يمكن تبسيط الرسم البياني ضمنها مع الحفاظ على عدد التقاطعات دون تغيير. تُجري خوارزمية غروه هذه التبسيطات حتى يصبح الرسم البياني المتبقي ذو عرض شجري صغير، ثم تُطبق نظرية كورسيل لحل المسألة الفرعية المُختزلة. [ 25 ] [ 26 ]

لاحظ غوتلوب ولي (2007) أن نظرية كورسيل تنطبق على العديد من مسائل إيجاد أصغر عدد من القطوعات متعددة الاتجاهات في الرسم البياني، عندما يكون عرض الشجرة للبنية المكونة من الرسم البياني ومجموعة أزواج القطوع محدودًا. ونتيجة لذلك، توصلا إلى خوارزمية قابلة للتطبيق ذات معلمات ثابتة لهذه المسائل، مُعَلمة بمعلمة واحدة هي عرض الشجرة، مما يُحسِّن الحلول السابقة التي كانت تجمع بين معلمات متعددة. [ 27 ]

في مجال الطوبولوجيا الحاسوبية ، قام بيرتون وداوني (2014) بتوسيع نظرية كورسيل من MSO 2 إلى شكل من أشكال منطق الرتبة الثانية الأحادي على المركبات التبسيطية ذات البعد المحدود، مما يسمح بالتكميم على التبسيطات ذات أي بعد ثابت. ونتيجة لذلك، بيّنا كيفية حساب بعض الثوابت الكمومية للمشعبات ثلاثية الأبعاد ، بالإضافة إلى كيفية حل بعض المسائل في نظرية مورس المنفصلة بكفاءة، عندما يكون للمشعب تثليث (مع تجنب التبسيطات المنحلة) يكون فيه الرسم البياني الثنائي ذو عرض شجري صغير. [ 28 ]

كما تم تطبيق الأساليب القائمة على نظرية كورسيل على نظرية قواعد البيانات ، [ 29 ] وتمثيل المعرفة والاستدلال ، [ 30 ] ونظرية الأوتوماتا ، [ 31 ] والتحقق من النماذج . [ 32 ]

مراجع

  1. ↑ إيجر، ستيفن (2008)، اللغات المنتظمة، وعرض الشجرة، ونظرية كورسيل: مقدمة ، دار نشر VDM، رقم ISBN 9783639076332.
  2. ↑ كورسيل، برونو ؛ إنجلفريت، جوست (2012)، بنية الرسم البياني ومنطق الرتبة الثانية الأحادي: مدخل لغوي نظري (ملف PDF) ، موسوعة الرياضيات وتطبيقاتها، المجلد 138، مطبعة جامعة كامبريدج ، رقم ISBN  9781139644006Zbl 1257.68006​ .
  3. ↑ داوني، رودني ج .؛ فيلوز، مايكل ر. (2013)، "الفصل 13: نظرية كورسيل"، أساسيات التعقيد المُعَلم ، نصوص في علوم الحاسوب، لندن: سبرينغر، ص 265-278 ، CiteSeerX 10.1.1.456.2729 ، doi : 10.1007/978-1-4471-5559-1 ، ISBN   978-1-4471-5558-4، MR 3154461 ، S2CID 23517218  .
  4. 1 2 كورسيل، برونو (1990)، "المنطق الأحادي من الدرجة الثانية للرسوم البيانية. الجزء الأول: مجموعات الرسوم البيانية المحدودة القابلة للتمييز"، المعلومات والحوسبة ، 85 (1): 12-75 ، doi : 10.1016/0890-5401(90)90043-H ، MR 1042649 ، Zbl 0722.03008  
  5. ↑ بوري، ريتشارد ب.؛ باركر، ر. غاري؛ توفي، كريغ أ. (1992)، "التوليد التلقائي لخوارزميات خطية الوقت من أوصاف حساب التفاضل والتكامل للمسائل المتعلقة بعائلات الرسوم البيانية المبنية بشكل متكرر"، Algorithmica ، 7 ( 5-6 ): 555-581 ، doi : 10.1007/BF01758777 ، MR 1154588 ، S2CID 22623740  .
  6. 1 2 كنيس، يواكيم؛ لانغر، ألكسندر (2009)، "نهج عملي لنظرية كورسيل"، الملاحظات الإلكترونية في علوم الحاسوب النظرية ، 251 : 65-81 ، doi : 10.1016/j.entcs.2009.08.028.
  7. ↑ لامبيس، مايكل (2010)، "نظريات فوقية خوارزمية لتقييد عرض الشجرة"، في دي بيرغ، مارك؛ ماير، أولريش (محرران)، وقائع الندوة الأوروبية السنوية الثامنة عشرة حول الخوارزميات ، سلسلة محاضرات في علوم الحاسوب، المجلد 6346، سبرينغر، الصفحات 549-560 ، doi : 10.1007/978-3-642-15775-2_47 ، ISBN   978-3-642-15774-5، Zbl 1287.68078 .
  8. 1 2 كورسيل، ب.؛ ماكوفسكي، ج. أ.؛ روتيكس، يو. (2000)، "مسائل التحسين القابلة للحل في زمن خطي على رسوم بيانية ذات عرض زمرة محدود"، نظرية أنظمة الحوسبة ، 33 (2): 125-150 ، CiteSeerX 10.1.1.414.1845 ، doi : 10.1007/s002249910009 ، MR 1739644 ، S2CID 15402031 ، Zbl 1009.68102    .
  9. ↑ أوم، سانغ-إيل ؛ سيمور، بول (2006)، "تقريب عرض الزمرة وعرض الفرع"، مجلة نظرية التوافيق ، السلسلة ب، 96 (4): 514-528 ، doi : 10.1016/j.jctb.2005.10.006 ، MR 2232389 .
  10. ^ كورسيل وإنجلفريت (2012) ، الاقتراح 5.13، ص.  338 .
  11. 1 2 أرنبورج، ستيفان؛ لاجرجرين، ينس؛ Seese، Detlef (1991)، “مشاكل سهلة للرسوم البيانية القابلة للتحلل الشجري”، مجلة الخوارزميات ، 12 (2): 308–340 ، CiteSeerX 10.1.1.12.2544 ، دوى : 10.1016 / 0196-6774(91)90006-K ، MR 1105479  .
  12. ↑ إلبرفيلد، مايكل؛ جاكوبي، أندرياس؛ تانتاو، تيل (أكتوبر 2010)، "صيغ فضاء اللوغاريتم لنظريات بودليندر وكورسيل" (ملف PDF) ، وقائع الندوة السنوية الحادية والخمسين لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS 2010) ، الصفحات 143-152 ، doi : 10.1109/FOCS.2010.21 ، ISBN  978-1-4244-8525-3، S2CID 1820251 .
  13. ↑ داوني وزملاء (2013) ، النظرية 13.1.1، ص 266.
  14. ↑ داوني وزملاء (2013) ، القسم 10.5: نظرية بودليندر، ص 195-203.
  15. ↑ داوني وزملاء (2013) ، القسم 12.6: الأوتوماتا الشجرية، ص 237-247.
  16. ↑ فريك، ماركوس؛ غروهي، مارتن (2004)، "إعادة النظر في تعقيد منطق الرتبة الأولى ومنطق الرتبة الثانية الأحادي"، حوليات المنطق البحت والتطبيقي ، 130 ( 1-3 ): 3-31 ، CiteSeerX 10.1.1.104.8429 ، doi : 10.1016/j.apal.2004.01.007 ، MR 2092847  .
  17. ^ باناخ، ماكس. هيشر ، ماركوس (2025/03/04). “الاستدلال الآلي الموجه بالهيكل”. في بيرسدورف، أولاف؛ بيليبكزوك، ميشال؛ بيمنتل، إيلين؛ ثونغ، نجوين كيم (محرران). الندوة الدولية الثانية والأربعون حول الجوانب النظرية لعلوم الكمبيوتر (STACS 2025) . LIPics. المجلد. 327. جينا، ألمانيا: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ص 15: 1-15: 18. دوى : 10.4230/LIPIcs.STACS.2025.15 . رقم ISBN   978-3-95977-365-2.
  18. ↑ لابوار، دينيس (1998)، "قابلية التعرف تساوي قابلية التعريف من الدرجة الثانية الأحادية لمجموعات الرسوم البيانية ذات عرض الشجرة المحدود"، STACS 98: الندوة السنوية الخامسة عشرة حول الجوانب النظرية لعلوم الحاسوب، باريس، فرنسا، 27 فبراير 1998، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 1373، الصفحات 618-628 ، Bibcode : 1998LNCS.1373..618L ، CiteSeerX 10.1.1.22.7805 ، doi : 10.1007/bfb0028596 ، ISBN    978-3-540-64230-5.
  19. ↑ كورسيل، ب.؛ إنجلفريت، ج. (2012)، "بنية الرسم البياني ومنطق الرتبة الثانية الأحادي - مدخل لغوي نظري"، موسوعة الرياضيات وتطبيقاتها ، المجلد 138، مطبعة جامعة كامبريدج .
  20. 1 2 جافكي، لارس؛ بودليندر، هانز ل. (2015)، قابلية تعريف MSOL تساوي قابلية التعرف عليها لرسوم هالين ورسوم خارجية مستوية من الدرجة k المحدودة ، arXiv : 1503.01604 ، Bibcode : 2015arXiv150301604J.
  21. ↑ كالر، د. (2000)، "قابلية التعريف تساوي قابلية التعرف على الأشجار الجزئية من الرتبة 3 والأشجار الجزئية المتصلة من الرتبة k "، Algorithmica ، 27 (3): 348-381 ، doi : 10.1007/s004530010024 ، S2CID 39798483 .
  22. ↑ بويانتشيك، ميكولاي؛ بيليبكزوك، ميخال (2016)، "قابلية التعريف تساوي قابلية التعرف للرسوم البيانية ذات عرض الشجرة المحدود"، وقائع الندوة السنوية الحادية والثلاثين لجمعية ACM/IEEE حول المنطق في علوم الحاسوب (LICS 2016) ، الصفحات 407-416 ، arXiv : 1605.03045 ، doi : 10.1145/2933575.2934508 ، ISBN  978-1-4503-4391-6، S2CID 1213054 .
  23. ↑ سيس، د. (1991)، "بنية نماذج النظريات الأحادية القابلة للتقرير للرسوم البيانية"، حوليات المنطق البحت والتطبيقي ، 53 (2): 169-195 ، doi : 10.1016/0168-0072(91)90054-P ، MR 1114848 .
  24. ↑ كورسيل، برونو؛ أوم، سانغ-إيل (2007)، "الرؤوس الصغرى، منطق الرتبة الثانية الأحادي، وتخمين سيس" (ملف PDF) ، مجلة نظرية التوافيق ، السلسلة ب، 97 (1): 91-126 ، doi : 10.1016/j.jctb.2006.04.003 ، MR 2278126 .
  25. ↑ غروه، مارتن (2001)، "حساب أعداد التقاطعات في زمن تربيعي"، وقائع الندوة السنوية الثالثة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '01) ، الصفحات 231-236 ، arXiv : cs/0009010 ، doi : 10.1145/380752.380805 ، ISBN  1-58113-349-9، S2CID 724544 .
  26. ↑ كاواراباياشي، كين-إيتشي ؛ ريد، بروس (2007)، "حساب عدد التقاطعات في زمن خطي"، وقائع الندوة السنوية التاسعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '07) ، الصفحات 382-390 ، doi : 10.1145/1250790.1250848 ، ISBN  978-1-59593-631-8، S2CID 13000831 .
  27. ↑ غوتلوب، جورج؛ لي، ستيفاني تيان (2007)، "نهج منطقي لمشاكل القطع المتعدد"، رسائل معالجة المعلومات ، 103 (4): 136-141 ، doi : 10.1016/j.ipl.2007.03.005 ، MR 2330167 .
  28. ↑ بيرتون، بنجامين أ.؛ داوني، رودني ج. (2014)، نظرية كورسيل للتثليثات ، arXiv : 1403.2926 ، Bibcode : 2014arXiv1403.2926B. رسالة قصيرة، المؤتمر الدولي للرياضيات ، 2014.
  29. ↑ غروه، مارتن؛ مارينو، جوليان (1999)، "قابلية التعريف والتعقيد الوصفي في قواعد البيانات ذات عرض الشجرة المحدود"، نظرية قواعد البيانات - المؤتمر الدولي السابع لنظرية قواعد البيانات - ICDT'99، القدس، إسرائيل، 10-12 يناير 1999، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 1540، الصفحات 70-82 ، CiteSeerX 10.1.1.52.2984 ، doi : 10.1007/3-540-49257-7_6 ، ISBN    978-3-540-65452-0.
  30. ↑ غوتلوب، جورج؛ بيشلر، راينهارد؛ وي، فانغ (يناير 2010)، "عرض الشجرة المحدود كمفتاح لسهولة التعامل مع تمثيل المعرفة والاستدلال"، الذكاء الاصطناعي ، 174 (1): 105-132 ، doi : 10.1016/j.artint.2009.10.003.
  31. ↑ مادوسودان، ب.؛ بارلاتو، جينارو (2011)، "عرض شجرة التخزين المساعد"، وقائع الندوة السنوية الثامنة والثلاثين لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة (POPL '11) (ملف PDF) ، نشرة SIGPLAN، المجلد 46، الصفحات 283-294 ، doi : 10.1145/1926385.1926419 ، ISBN   978-1-4503-0490-0، S2CID 6976816 
  32. ↑ أوبدرزالك، يان (2003)، "التحقق السريع من نموذج حساب التفاضل والتكامل عندما يكون عرض الشجرة محدودًا"، التحقق بمساعدة الحاسوب: المؤتمر الدولي الخامس عشر، CAV 2003، بولدر، كولورادو، الولايات المتحدة الأمريكية، 8-12 يوليو 2003، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 2725، الصفحات 80-92 ، CiteSeerX 10.1.1.2.4843 ، doi : 10.1007/978-3-540-45069-6_7 ، ISBN    978-3-540-40524-5.