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

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

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

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

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

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

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

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

एकल रेखांकन (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: वर्णनात्मक जटिलता सिद्धांत

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

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

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

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

अनुप्रयोग

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

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

select LAST_NAME 
from GIRLS
where FIRST_NAME = 'Judy'

ध्यान दें, हम यहां मानते हैं कि सभी अंतिम नाम केवल एक बार दिखाई देते हैं या हमें सेलेक्ट डिस्टींक्ट का उपयोग करना चाहिए क्योंकि हम मानते हैं कि संबंध और उत्तर समुच्चय हैं, बैग नहीं है। आगे हम एक और जटिल वक्तव्य देना चाहते हैं। इसलिए, गर्ल्स तालिका के अतिरिक्त हमारे पास एक तालिका बॉयज भी है, जिसमें कॉलम पहला_नाम और अंतिम_नाम हैं। अब हम उन सभी लड़कियों के अंतिम नामों को पूछना चाहते हैं जिनका अंतिम नाम कम से कम एक लड़के के समान है। एफओ क्वेरी {(f,l) : ∃h ( G(f, l) ∧ B(h, l) )} और संबंधित एसक्यूएल कथन इस तरह है

select FIRST_NAME, LAST_NAME 
from GIRLS
where LAST_NAME IN ( select LAST_NAME from BOYS );

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

select distinct g.FIRST_NAME, g.LAST_NAME 
from GIRLS g, BOYS b
where g.LAST_NAME=b.LAST_NAME;

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

पूछताछ और खोज

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

("Java" AND NOT "island") OR ("C#" AND NOT "music")

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

इतिहास

• ट्रेखटेनब्रॉट प्रमेय: प्रथम क्रम तर्क में पूर्णता प्रमेय की विफलता हुई थी
• हेनरी स्कोल्ज़ 1952: प्रथम-क्रम तर्क में स्पेक्ट्रा का लक्षण वर्णन किया गया है
• फागिन का प्रमेय: अस्तित्वगत दूसरे क्रम के तर्क में अभिव्यक्त होने वाले सभी गुणों का समुच्चय ठीक जटिलता क्लास एनपी के रूप में होते है
• चंद्रा, हरेल 1979/80: ट्रांससीटीव समापन व्यक्त करने में सक्षम डेटाबेस क्वेरी लैंग्वेजओं के लिए फिक्स्ड पॉइंट फर्स्ट ऑर्डर लॉजिक एक्सटेंशन -> एफएमटी की केंद्रीय वस्तुओं के रूप में प्रश्न है
• नील इमरमैन, मोशे वर्डी 1982: फिक्स्ड पॉइंट लॉजिक ओवर ऑर्डर्ड स्ट्रक्चर कैप्चर्स पीटाइम -> वर्णनात्मक जटिलता इमरमैन ज़ेलेपेसेनी प्रमेय के रूप में है
• हेंज-डाइटर एबिंगहॉस, 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.