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

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

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

एक्सिओममैटिसबीलीटी

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

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

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

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

एकल रेखांकन (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}.$

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

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

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

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

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

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. एफओ [एम] को परिभाषित करने का एक सामान्य विधि एफओ फॉर्मूला α के क्वांटिफायर रैंक क्यूआर (α) के माध्यम से होता है, जो परिमाणक (तर्क) नेस्टिंग की गहराई को व्यक्त करता है। उदाहरण के लिए, प्रीनेक्स सामान्य रूप में एक सूत्र के लिए क्यूआर केवल इसके परिमाणकों की कुल संख्या होती है। तब एफओ [एम] को क्यूआर (α) ≤ एम के साथ सभी एफओ सूत्रों α के रूप में परिभाषित किया जाता है या यदि कोई विभाजन वांछित है, तो उन एफओ सूत्रों के रूप में क्वांटिफायर रैंक एम के बराबर होती है।

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

उदाहरण

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

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

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

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

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

5. इस प्रकार परिमित क्रमबद्ध संरचनाओं को एफओ में व्यक्त नहीं किया जा सकता है।

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

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

ग्लीब्स्की et al. (1969) और स्वतंत्र रूप से, फेगिन (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: वर्णनात्मक जटिलता सिद्धांत

परिमित मॉडल सिद्धांत का एक महत्वपूर्ण लक्ष्य उन लैंग्वेज ओं को व्यक्त करने के लिए आवश्यक तर्क के प्रकार से जटिलता वर्गों का लक्षण वर्णन है। उदाहरण के लिए, 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.