परिमित मॉडल सिद्धांत

परिमित मॉडल सिद्धांत मॉडल सिद्धांत का एक उपक्षेत्र है। मॉडल सिद्धांत तर्क की शाखा है जो एक औपचारिक भाषा (वाक्यविन्यास) और इसकी व्याख्याओं (शब्दार्थ) के बीच के संबंध से संबंधित है। परिमित मॉडल सिद्धांत परिमित संरचना (गणितीय तर्क) पर व्याख्या (तर्क) के मॉडल सिद्धांत का एक प्रतिबंध है, जिसमें एक परिमित ब्रह्मांड है।

चूंकि मॉडल सिद्धांत के कई केंद्रीय प्रमेय परिमित संरचनाओं तक सीमित नहीं हैं, परिमित मॉडल सिद्धांत अपने प्रमाण के तरीकों में मॉडल सिद्धांत से काफी अलग है। शास्त्रीय मॉडल सिद्धांत के केंद्रीय परिणाम जो परिमित मॉडल सिद्धांत के तहत परिमित संरचनाओं के लिए विफल होते हैं, उनमें कॉम्पैक्टनेस प्रमेय, गोडेल की पूर्णता प्रमेय और प्रथम-क्रम तर्क (एफओ) के लिए ultraproduct ्स की विधि सम्मलित है। जबकि मॉडल सिद्धांत में सार बीजगणित के लिए कई अनुप्रयोग हैं, परिमित मॉडल सिद्धांत असामान्य रूप से प्रभावी हो गया है कंप्यूटर विज्ञान में उपकरण। दूसरे शब्दों में: गणितीय तर्क के इतिहास में सबसे अधिक रुचि अनंत संरचनाओं पर केंद्रित रही है। [...] फिर भी, कंप्यूटर के पास और धारण करने वाली वस्तुएँ हमेशा परिमित होती हैं। अभिकलन का अध्ययन करने के लिए हमें परिमित संरचनाओं के सिद्धांत की आवश्यकता है। इस प्रकार परिमित मॉडल सिद्धांत के मुख्य अनुप्रयोग क्षेत्र हैं: वर्णनात्मक जटिलता, डेटाबेस सिद्धांत और औपचारिक भाषा।

स्वयंसिद्धता

परिमित मॉडल सिद्धांत में एक सामान्य प्रेरक प्रश्न यह है कि क्या किसी दी गई भाषा में संरचनाओं के दिए गए वर्ग का वर्णन किया जा सकता है। उदाहरण के लिए, कोई पूछ सकता है कि क्या चक्रीय रेखांकन के वर्ग को एफओ वाक्य द्वारा ग्राफ के बीच अलग किया जा सकता है, जिसे यह पूछने के लिए भी कहा जा सकता है कि चक्रीयता एफओ-अभिव्यक्त है या नहीं।

एक एकल परिमित संरचना हमेशा गैर प्रथमक्रमक्षमता | प्रथम-क्रम तर्क में स्वयंसिद्ध हो सकती है, जहां एक भाषा एल में स्वयंसिद्ध का मतलब एकल एल-वाक्य द्वारा आइसोमोर्फिज्म तक विशिष्ट रूप से वर्णित है। इसी तरह, परिमित संरचनाओं के किसी भी परिमित संग्रह को पहले क्रम के तर्क में हमेशा स्वयंसिद्ध किया जा सकता है। कुछ, लेकिन सभी नहीं, परिमित संरचनाओं के अनंत संग्रह भी एक प्रथम-क्रम वाक्य द्वारा स्वयंसिद्ध हो सकते हैं।

एकल संरचना की विशेषता

क्या एक भाषा L एक एकल परिमित संरचना S को अभिव्यक्त करने के लिए पर्याप्त अभिव्यंजक है?

एकल रेखांकन (1) और (1') में सामान्य गुण हैं।

समस्या

आकृति में (1) जैसी संरचना को रेखांकन के तर्क में एफओ वाक्यों द्वारा वर्णित किया जा सकता है

1. प्रत्येक नोड में दूसरे नोड का किनारा होता है: $\forall _{x}\exists _{y}G(x,y).$
2. किसी भी नोड का कोई किनारा नहीं है: $\forall _{x,y}(G(x,y)\Rightarrow x\neq y).$
3. कम से कम एक नोड है जो अन्य सभी से जुड़ा है: $\exists _{x}\forall _{y}(x\neq y\Rightarrow G(x,y)).$

हालांकि, ये गुण संरचना को स्वयंसिद्ध नहीं करते हैं, क्योंकि संरचना (1') के लिए उपरोक्त गुण भी धारण करते हैं, फिर भी संरचनाएं (1) और (1') समरूपी नहीं हैं।

अनौपचारिक रूप से प्रश्न यह है कि क्या पर्याप्त गुणों को जोड़कर, ये गुण एक साथ बिल्कुल (1) का वर्णन करते हैं और किसी अन्य संरचना (समरूपता तक) के लिए मान्य (सभी एक साथ) हैं।

दृष्टिकोण

एकल परिमित संरचना के लिए एक एकल एफओ वाक्य द्वारा संरचना का सटीक वर्णन करना हमेशा संभव होता है। सिद्धांत यहाँ एक द्विआधारी संबंध के साथ एक संरचना के लिए सचित्र है $R$ और स्थिरांक के बिना:

1. कहते हैं कि कम से कम हैं $n$ तत्व: $\varphi _{1}=\bigwedge _{i\neq j}\neg (x_{i}=x_{j})$
2. कहना है कि ज्यादा से ज्यादा हैं $n$ तत्व: $\varphi _{2}=\forall _{y}\bigvee _{i}(x_{i}=y)$
3. संबंध के हर तत्व को बताएं $R$: $\varphi _{3}=\bigwedge _{(a_{i},a_{j})\in R}R(x_{i},x_{j})$
4. संबंध के हर गैर-तत्व को बताएं $R$: $\varphi _{4}=\bigwedge _{(a_{i},a_{j})\notin R}\neg R(x_{i},x_{j})$

सभी एक ही टपल के लिए $x_{1}..x_{n}$, एफओ वाक्य उपज $\exists _{x_{1}}\dots \exists _{x_{n}}(\varphi _{1}\land \varphi _{2}\land \varphi _{3}\land \varphi _{4})$.

संरचनाओं की एक निश्चित संख्या तक विस्तार

प्रथम-क्रम वाक्य के माध्यम से एकल संरचना का वर्णन करने की विधि को किसी भी निश्चित संख्या में संरचनाओं के लिए आसानी से बढ़ाया जा सकता है। प्रत्येक संरचना के लिए विवरणों के संयोजन से एक अद्वितीय विवरण प्राप्त किया जा सकता है। उदाहरण के लिए, दो संरचनाओं के लिए $A$ और $B$ परिभाषित वाक्यों के साथ $\varphi _{A}$ और $\varphi _{B}$ यह होगा

$\varphi _{A}\lor \varphi _{B}.$

एक अनंत संरचना का विस्तार

परिभाषा के अनुसार, एक अनंत संरचना वाला एक सेट उस क्षेत्र के बाहर पड़ता है जो FMT से संबंधित है। ध्यान दें कि लोवेनहाइम-स्कोलेम प्रमेय के कारण एफओ में अनंत संरचनाओं में कभी भी भेदभाव नहीं किया जा सकता है, जिसका अर्थ है कि अनंत मॉडल वाले पहले-क्रम के सिद्धांत में समरूपता तक एक अद्वितीय मॉडल नहीं हो सकता है।

सबसे प्रसिद्ध उदाहरण शायद अंकगणित का गैर-मानक मॉडल है | स्कोलेम का प्रमेय, कि अंकगणित का एक गणनीय गैर-मानक मॉडल है।

संरचनाओं के एक वर्ग की विशेषता

क्या एक भाषा L अभिव्यंजक है जो सटीक रूप से (समरूपता तक) उन परिमित संरचनाओं का वर्णन करने के लिए पर्याप्त है जिनके पास कुछ संपत्ति P है?

n संरचनाओं तक का सेट।

समस्या

अब तक दिए गए सभी विवरण ब्रह्मांड के तत्वों की संख्या को निर्दिष्ट करते हैं। दुर्भाग्य से संरचनाओं के सबसे दिलचस्प सेट एक निश्चित आकार तक ही सीमित नहीं हैं, जैसे सभी ग्राफ़ जो पेड़ हैं, जुड़े हुए हैं या विश्वकोश हैं। इस प्रकार संरचनाओं की एक सीमित संख्या में भेदभाव करना विशेष महत्व रखता है।

दृष्टिकोण

एक सामान्य कथन के अतिरिक्त , निम्नलिखित संरचनाओं के बीच अंतर करने के लिए एक पद्धति का एक रेखाचित्र है जिसमें भेदभाव किया जा सकता है और नहीं किया जा सकता है।

1. मूल विचार यह है कि जब भी कोई यह देखना चाहता है कि क्या संपत्ति पी को एफओ में व्यक्त किया जा सकता है, तो वह संरचना ए और बी को चुनता है, जहां ए में ' 'पी' और 'बी' नहीं है। यदि 'ए' और 'बी' के लिए समान एफओ वाक्य हैं, तो 'पी' को एफओ में व्यक्त नहीं किया जा सकता है। संक्षेप में:

$A\in P,B\not \in P$ और $A\equiv B,$

कहाँ $A\equiv B$ के लिए आशुलिपि है $A\models \alpha \Leftrightarrow B\models \alpha$ सभी एफओ-वाक्यों के लिए α, और पी संपत्ति पी के साथ संरचनाओं के वर्ग का प्रतिनिधित्व करता है।

'2.' कार्यप्रणाली भाषा के कई उपसमूहों पर विचार करती है, जिनमें से संघ स्वयं भाषा बनाता है। उदाहरण के लिए, एफओ के लिए प्रत्येक एम के लिए वर्ग एफओ [एम] पर विचार करें। प्रत्येक एम के लिए उपरोक्त मूल विचार को दिखाना होगा। वह है:

$A\in P,B\not \in P$ और $A\equiv _{m}B$

एक जोड़ी के साथ $A,B$ प्रत्येक के लिए $m$ और α (≡ में) एफओ [एम] से। भाषा का विभाजन बनाने के लिए एफओ [एम] वर्ग का चयन करना उचित हो सकता है।

'3।' एफओ [एम] को परिभाषित करने का एक आम तरीका एफओ फॉर्मूला α के क्वांटिफायर रैंक क्यूआर (α) के माध्यम से है, जो परिमाणक (तर्क)तर्क) नेस्टिंग की गहराई को व्यक्त करता है। उदाहरण के लिए, प्रीनेक्स सामान्य रूप में एक सूत्र के लिए, क्यूआर केवल इसके परिमाणकों की कुल संख्या है। तब FO[m] को qr(α) ≤ m के साथ सभी FO सूत्रों α के रूप में परिभाषित किया जा सकता है (या, यदि कोई विभाजन वांछित है, तो उन FO सूत्रों के रूप में m के बराबर क्वांटिफायर रैंक के साथ)।

'4।' इस प्रकार यह सब दिखाने के लिए नीचे आता है $A\models \alpha \Leftrightarrow B\models \alpha$ सबसेट एफओ [एम] पर। यहां मुख्य दृष्टिकोण एहरेनफ्यूच्ट-फ्रैसे गेम द्वारा प्रदान किए गए बीजगणितीय लक्षण वर्णन का उपयोग करना है। अनौपचारिक रूप से, ये ए और बी पर एक आंशिक समरूपता लेते हैं और इसे साबित करने या अस्वीकार करने के लिए इसे एम बार बढ़ाते हैं। $A\equiv _{m}B$खेल कौन जीतता है, इस पर निर्भर करता है।

उदाहरण

हम यह दिखाना चाहते हैं कि एक आदेशित संरचना का आकार A = (A, ≤) सम है, जिसे FO में व्यक्त नहीं किया जा सकता है।

1. विचार यह है कि A ∈ EVEN और B ∉ EVEN को चुना जाए, जहाँ EVEN समान आकार की सभी संरचनाओं का वर्ग है।

2. हम दो क्रमित संरचनाओं A से प्रारंभ करते हैं₂और बी₂ब्रह्मांड ए के साथ₂ = {1, 2, 3, 4} और बी₂ = {1, 2, 3}। जाहिर है ए₂∈ ईवन और बी₂∉ सम।

3. m = 2 के लिए, अब हम * दिखा सकते हैं कि A पर 2-चाल एहरेनफुच-फ्रैसे खेल में₂और बी₂अनुलिपित्र हमेशा जीतता है, और इस प्रकार ए₂और बी₂एफओ [2], अर्थात ए में भेदभाव नहीं किया जा सकता है₂ $\models$ ए ⇔ बी₂ $\models$ α प्रत्येक α ∈ एफओ [2] के लिए।

4. इसके बाद हमें 'एम' को बढ़ाकर स्ट्रक्चर को स्केल करना होगा। उदाहरण के लिए, एम = 3 के लिए हमें एक ए खोजना होगा₃और बी₃जैसे कि अनुलिपित्र हमेशा 3-चाल वाला खेल जीतता है। यह ए द्वारा प्राप्त किया जा सकता है₃ = {1, ..., 8} और बी₃ = {1, ..., 7}। अधिक सामान्यतः , हम ए चुन सकते हैं_m = {1, ..., 2^मी} और बी_m = {1, ..., 2^मी-1}; किसी भी मी के लिए डुप्लीकेटर हमेशा इस जोड़ी संरचनाओं के लिए एम-मूव गेम जीतता है*।

'5।' इस प्रकार परिमित आदेशित संरचनाओं पर भी एफओ में व्यक्त नहीं किया जा सकता है।

(*) ध्यान दें कि एहरेनफुच-फ्रैसे खेल के परिणाम का प्रमाण छोड़ दिया गया है, क्योंकि यह यहां मुख्य फोकस नहीं है।

शून्य-एक कानून

Glebskiĭ et al. (1969) और, स्वतंत्र रूप से, Fagin (1976) ने परिमित मॉडलों में प्रथम-क्रम के वाक्यों के लिए शून्य-एक नियम सिद्ध किया; फागिन के सबूत ने कॉम्पैक्टनेस प्रमेय का इस्तेमाल किया। इस परिणाम के अनुसार, संबंधपरक हस्ताक्षर में प्रत्येक प्रथम-क्रम वाक्य $\sigma$ परिमित में या तो लगभग हमेशा सत्य होता है या लगभग हमेशा असत्य होता है $\sigma$-संरचनाएं। अर्थात चलो S निश्चित प्रथम-क्रम वाक्य बनें, और एक यादृच्छिक चुनें $\sigma$-संरचना $G_{n}$ डोमेन के साथ $\{1,\dots ,n\}$, सबके बीच समान रूप से $\sigma$डोमेन के साथ संरचनाएं $\{1,\dots ,n\}$. फिर सीमा में n अनंत की ओर जाता है, संभावना है कि G_n मॉडल S या तो शून्य या एक की ओर प्रवृत्त होगा:

$\lim _{n\to \infty }\operatorname {Pr} [G_{n}\models S]\in \{0,1\}.$

यह निर्धारित करने की समस्या कि क्या किसी दिए गए वाक्य की प्रायिकता शून्य या एक की ओर है, पीएसपीएसीई-पूर्ण है। प्रथम-क्रम तर्क की तुलना में अधिक अभिव्यंजक तर्कशास्त्र के लिए एक समान विश्लेषण किया गया है। 0-1 कानून को कम से कम निश्चित बिंदु तर्क में वाक्यों के लिए दिखाया गया है | एफओ (एलएफपी), कम से कम निश्चित बिंदु ऑपरेटर के साथ संवर्धित प्रथम-क्रम तर्क, और सामान्यतः अनंत तर्क में वाक्यों के लिए $L_{\infty \omega }^{\omega }$, जो संभावित रूप से मनमाने ढंग से लंबे संयुग्मन और वियोग की अनुमति देता है। एक अन्य महत्वपूर्ण संस्करण बिना लेबल वाला 0-1 कानून है, जहां डोमेन के साथ संरचनाओं के अंश पर विचार करने के अतिरिक्त $\{1,\dots ,n\}$, एक के साथ संरचनाओं के समरूपता वर्गों के अंश पर विचार करता है n तत्व। यह अंश अच्छी तरह से परिभाषित है, क्योंकि कोई भी दो आइसोमॉर्फिक संरचनाएं समान वाक्यों को संतुष्ट करती हैं। बिना लेबल वाला 0-1 कानून भी लागू होता है $L_{\infty \omega }^{\omega }$ और इसलिए विशेष रूप से एफओ (एलएफपी) और प्रथम क्रम तर्क के लिए।

वर्णनात्मक जटिलता सिद्धांत

Main article: Descriptive complexity theory

परिमित मॉडल सिद्धांत का एक महत्वपूर्ण लक्ष्य उन भाषाओं को व्यक्त करने के लिए आवश्यक तर्क के प्रकार से जटिलता वर्गों का लक्षण वर्णन है। उदाहरण के लिए, PH (जटिलता), बहुपद पदानुक्रम में सभी जटिलता वर्गों का संघ, दूसरे क्रम के तर्क के बयानों द्वारा व्यक्त की जाने वाली भाषाओं का वर्ग है। जटिलता और परिमित संरचनाओं के तर्क के बीच यह संबंध परिणामों को एक क्षेत्र से दूसरे क्षेत्र में आसानी से स्थानांतरित करने की अनुमति देता है, नए प्रमाण विधियों की सुविधा प्रदान करता है और अतिरिक्त सबूत प्रदान करता है कि मुख्य जटिलता वर्ग किसी तरह प्राकृतिक हैं और परिभाषित करने के लिए उपयोग की जाने वाली विशिष्ट अमूर्त मशीनों से बंधे नहीं हैं। उन्हें।

विशेष रूप से, प्रत्येक तार्किक प्रणाली इसमें अभिव्यक्ति योग्य क्वेरी (जटिलता) का एक सेट उत्पन्न करता है। प्रश्न - जब परिमित संरचनाओं तक सीमित होते हैं - पारंपरिक जटिलता सिद्धांत की कम्प्यूटेशनल समस्याओं के अनुरूप होते हैं।

कुछ प्रसिद्ध जटिलता वर्गों को तार्किक भाषाओं द्वारा निम्नानुसार कब्जा कर लिया गया है:

• एक रेखीय क्रम की उपस्थिति में, एक क्रमविनिमेय, सकर्मक बंद करने वाले ऑपरेटर के साथ प्रथम-क्रम तर्क एल (जटिलता) को जोड़ता है, लॉगरिदमिक स्थान में हल करने योग्य समस्याएं।
• एक रेखीय क्रम की उपस्थिति में, एक सकर्मक क्लोजर ऑपरेटर के साथ प्रथम-क्रम तर्क एनएल (जटिलता) उत्पन्न करता है, गैर-नियतात्मक लॉगरिदमिक स्थान में हल करने योग्य समस्याएं।
• एक रेखीय क्रम की उपस्थिति में, कम से कम निश्चित बिंदु ऑपरेटर के साथ प्रथम-क्रम तर्क P (जटिलता) देता है, नियतात्मक बहुपद समय में हल करने योग्य समस्याएँ।
• सभी परिमित संरचनाओं पर (भले ही वे आदेशित हों), अस्तित्वगत दूसरे क्रम का तर्क [[एनपी (जटिलता)]] (फागिन का प्रमेय) देता है।

अनुप्रयोग

डेटाबेस सिद्धांत

एसक्यूएल का एक महत्वपूर्ण खंड (अर्थात् वह जो प्रभावी रूप से संबंधपरक बीजगणित है) प्रथम-क्रम तर्क पर आधारित है (कॉड के प्रमेय के माध्यम से डोमेन रिलेशनल कैलकुलस में अधिक सटीक रूप से अनुवादित किया जा सकता है), जैसा कि निम्नलिखित उदाहरण दिखाता है: एक डेटाबेस तालिका GIRLS के बारे में सोचें कॉलम FIRST_NAME और LAST_NAME के ​​साथ। यह FIRST_NAME X LAST_NAME पर एक द्विआधारी संबंध, मान लीजिए G(f, l) से संबंधित है। एफओ क्वेरी {एल: जी ('जूडी', एल)}, जो सभी अंतिम नाम देता है जहां पहला नाम 'जूडी' है, एसक्यूएल में इस तरह दिखेगा:

LAST_NAME चुनें
लड़कियों से
जहां FIRST_NAME = 'जूडी'

ध्यान दें, हम यहां मानते हैं कि सभी अंतिम नाम केवल एक बार दिखाई देते हैं (या हमें SELECT DISTINCT का उपयोग करना चाहिए क्योंकि हम मानते हैं कि संबंध और उत्तर सेट हैं, बैग नहीं)।

आगे हम एक और जटिल वक्तव्य देना चाहते हैं। इसलिए, GIRLS तालिका के अतिरिक्त हमारे पास एक तालिका BOYS भी है जिसमें कॉलम FIRST_NAME और LAST_NAME हैं। अब हम उन सभी लड़कियों के अंतिम नामों को पूछना चाहते हैं जिनका अंतिम नाम कम से कम एक लड़के के समान है। एफओ क्वेरी {(एफ, एल) है: ∃ एच (जी (एफ, एल) ∧ बी (एच, एल))}, और संबंधित एसक्यूएल कथन है:

FIRST_NAME, LAST_NAME चुनें
लड़कियों से
जहां LAST_NAME IN (लड़कों में से LAST_NAME चुनें);

ध्यान दें कि ∧ को व्यक्त करने के लिए हमने नए भाषा तत्व IN को बाद के चयन कथन के साथ पेश किया। यह सीखने और लागू करने के लिए उच्च कठिनाई की कीमत के लिए भाषा को अधिक अभिव्यंजक बनाता है। औपचारिक भाषा डिजाइन में यह एक सामान्य समझौता है। ऊपर दिखाया गया तरीका ( IN ) अब तक भाषा का विस्तार करने वाला एकमात्र नहीं है। एक वैकल्पिक तरीका है उदा। एक जॉइन ऑपरेटर पेश करने के लिए, वह है:

अलग g.FIRST_NAME, g.LAST_NAME चुनें
लड़कियों जी से, लड़कों बी
जहाँ g.LAST_NAME=b.LAST_NAME;

प्रथम-क्रम तर्क कुछ डेटाबेस अनुप्रयोगों के लिए बहुत अधिक प्रतिबंधात्मक है, उदाहरण के लिए सकर्मक समापन को व्यक्त करने में असमर्थता के कारण। इसने डेटाबेस क्वेरी भाषाओं में अधिक शक्तिशाली निर्माणों को जोड़ा है, जैसे SQL: 1999 में पुनरावर्ती के साथ। डेटाबेस सिद्धांत और अनुप्रयोगों के लिए उनकी प्रासंगिकता के कारण अधिक अभिव्यंजक लॉजिक्स, जैसे फिक्सपॉइंट तर्क ्स, का परिमित मॉडल सिद्धांत में अध्ययन किया गया है।

पूछताछ और खोज

नैरेटिव डेटा में कोई परिभाषित संबंध नहीं होता है। इस प्रकार पाठ खोज प्रश्नों की तार्किक संरचना को प्रस्तावात्मक तर्क में व्यक्त किया जा सकता है, जैसे:

(जावा और द्वीप नहीं) या (सी # और संगीत नहीं)

ध्यान दें कि पूर्ण पाठ खोज में चुनौतियाँ डेटाबेस क्वेरी से भिन्न होती हैं, जैसे परिणामों की रैंकिंग।

इतिहास

• ट्रेखटेनब्रॉट प्रमेय: प्रथम क्रम तर्क में पूर्णता प्रमेय की विफलता
• हेनरी स्कोल्ज़ 1952: प्रथम-क्रम तर्क में स्पेक्ट्रा का लक्षण वर्णन
• फागिन का प्रमेय: अस्तित्वगत दूसरे क्रम के तर्क में अभिव्यक्त होने वाले सभी गुणों का सेट ठीक जटिलता वर्ग एनपी है
• चंद्रा, हरेल 1979/80: सकर्मक समापन व्यक्त करने में सक्षम डेटाबेस क्वेरी भाषाओं के लिए फिक्स्ड-पॉइंट फर्स्ट-ऑर्डर लॉजिक एक्सटेंशन -> एफएमटी की केंद्रीय वस्तुओं के रूप में प्रश्न
• नील इमरमैन, मोशे वर्डी 1982: फिक्स्ड-पॉइंट लॉजिक ओवर ऑर्डर्ड स्ट्रक्चर कैप्चर्स पीटाइम -> वर्णनात्मक जटिलता (इमरमैन-ज़ेलेपेसेनी प्रमेय)
• Heinz-Dieter Ebbinghaus, Flum 1995: पहली व्यापक पुस्तक परिमित मॉडल सिद्धांत
• सर्ज एबितेबोल, हल, विक्टर वियानू 1995: बुक फ़ाउंडेशन ऑफ़ डेटाबेस
• नील इम्मरमैन 1999: पुस्तक वर्णनात्मक जटिलता
• कुपर, लिब्किन, पेरेडेन्स 2000: पुस्तक बाधा डेटाबेस

डार्मस्टैड 2005/आचेन 2006: एलगोरिदमिक मॉडल थ्योरी पर पहली अंतर्राष्ट्रीय कार्यशाला

संदर्भ

• Ebbinghaus, Heinz-Dieter; Flum, Jörg (1995). Finite Model Theory. Springer. ISBN 978-3-540-60149-4.

• Fagin, Ronald (1976). "Probabilities on Finite Models". The Journal of Symbolic Logic. 41 (1): 50–58. doi:10.2307/2272945. JSTOR 2272945.

• Glebskiĭ, Yu V., D. I. Kogan, M. I. Liogon'kiĭ, and V. A. Talanov. "Volume and fraction of satisfiability of formulae of the first-order predicate calculus." Kibernetika 2 (1969): 17-27.

• Libkin, Leonid (2004). Elements of Finite Model Theory. Springer. ISBN 3-540-21202-7.

• Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.

• Immerman, Neil (1999). Descriptive Complexity. New York: Springer. ISBN 0-387-98600-6.

अग्रिम पठन

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

बाहरी संबंध

• Libkin, Leonid (2009). "The finite model theory toolbox of a database theoretician". PODS 2009: Proceedings of the twenty-eighth ACM SIGACT–SIGMOD symposium on Principles of database systems. pp. 65–76. doi:10.1145/1559795.1559807. Also suitable as a general introduction and overview.
• Leonid Libkin. Introductory chapter of "Elements of Finite Model Theory" Archived 2015-09-24 at the Wayback Machine. Motivates three main application areas: databases, complexity and formal languages.
• Jouko Väänänen. A Short Course on Finite Model Theory. Department of Mathematics, University of Helsinki. Based on lectures from 1993-1994.
• Anuj Dawar. Infinite and Finite Model Theory, slides, University of Cambridge, 2002.
• "Algorithmic Model Theory". RWTH Aachen. Archived from the original on 17 July 2012. Retrieved 7 November 2013. Includes a list of open FMT problems.