عنوان

رابطه مابینی در ترتیب‌های جزئی

شماره

پ۲۷۸۸۶

زبان متن نوشتاري يا گفتاري و مانند آن

per

عنوان اصلي

رابطه مابینی در ترتیب‌های جزئی

نام نخستين پديدآور

رقیه (آیسان) پناهی

نام ناشر، پخش کننده و غيره

ریاضی،آمار و علوم کامپیوتر

تاریخ نشرو بخش و غیره

۱۴۰۱

نام خاص و کميت اثر

۵۸ص.

مواد همراه اثر

سی دی

جزئيات پايان نامه و نوع درجه آن

کارشناسی ارشد

نظم درجات

ریاضی محض، گرایش جبر (شاخه منطق)

زمان اعطا مدرک

۱۴۰۰/۰۷/۱۰

متن يادداشت

در این پایان نامه که بر اساس مقاله [B. Courcelle , Betweenness of Partical orders, Rairo-Theor. Inf. Appl.54(202)1-13]نوشته می¬شود، یک جمله مرتبۀ دوم تکین ارائه می¬شود که روابط سه¬گانه «مابینی» را در روابط جزئی متناهی یا نامتناهی طبقه¬بندی می¬کند. رده¬ی رابطه¬های مابینی در ترتیب¬¬های جزئی توسط مجموعه¬ای نامتناهی از جملات مرتبۀ اول اصل موضوعی می¬شود اما نشان داده شده است که اصل پذیر متناهی نیست. ترتیب¬های جزئی توسط یک جمله مرتبه دوم تکین (Manadic second order) که به اختصار با MSO نشان داده می¬شود. اصل موضوعی می¬شود و نشان داده می¬شود که هیچ جمله مرتبۀ اوّلی چنین توانایی را ندارد. همچنین ترتیب¬های جزئی که به طور یکتایی (تحت یکسان¬گیری با رابطه معکوس) از رابطه مابینی متناظر ساخته ¬می¬شوند، طبقه¬بندی خواهند شد. در انتها یک الگوریتم با پیچیدگی زمانی چند جمله¬ای ارئه خواهند شد که مشخص می¬کند رابطه سه گانه و متناهی داده شده R، یک رابطه مابینی برای یک ترتیب جزئی است یا نه؟

متن يادداشت

Abstract ‎This ‎dissertation ‎is ‎written ‎bassed ‎on ‎the ‎following ‎paper:‎‎ {‎Bruno Courcelle, Betweenness of partial orders, RAIRO-Theor. Inf. Appl. 54 (2020) 7}.‎‎ The Auther Constructs a monadic second-order sentence that characterizes the partial orders.‎ He proves that no first-order sentence can do that. Then, he characterizes the partial orders that can be reconstructed from their betweenness relations‎. At last, he proposes a polynomial time algorithm that test if a finite relation is the betweenness of a patial order‎.‎

عنوان گونه گون

BETWEENNESS OF PARTIAL ORDERS

عنصر شناسه اي

‏پناهی،

ساير عناصر نام

‏رقیه (آیسان)

کد نقش

تهیه کننده

عنصر شناسه اي

‏عیوضلو،

عنصر شناسه اي

بهمرام،

ساير عناصر نام

‏جعفر صادق

ساير عناصر نام

‏ افشین

تاريخ

استاد راهنما

تاريخ

استاد مشاور

عنصر شناسه اي

‏ تبریز