संगणना में कालिक और मोडल तर्क

कालिक (Temporal) और मोडल (Modal) तर्क शास्त्रीय तर्क को समय और संभावना के लिए ऑपरेटरों के साथ विस्तारित करते हैं, जिससे यह निर्दिष्ट करने के लिए सटीक भाषाएँ मिलती हैं कि एक प्रोग्राम या प्रतिक्रियाशील प्रणाली को अपने पूरे निष्पादन के दौरान कैसा व्यवहार करना चाहिए।

Definition

कालिक तर्क प्रस्तावनात्मक या प्रथम-क्रम तर्क को उन ऑपरेटरों के साथ बढ़ाता है जो यह वर्णन करते हैं कि किसी संगणना के साथ गुण कब धारण करते हैं, जैसे कि हमेशा, अंततः, और जब तक; मोडल तर्क इसे राज्यों और संक्रमणों की संरचना पर आवश्यकता और संभावना के लिए ऑपरेटरों के साथ सामान्यीकृत करता है।

Scope

यह विषय LTL और CTL जैसे रैखिक-समय और शाखा-समय कालिक तर्क, डायनामिक तर्क और मोडल म्यू-कैलकुलस सहित मोडल तर्क, सुरक्षा और जीवंतता गुणों की अभिव्यक्ति, और मॉडल जाँच (model checking) और संतोषजनकता (satisfiability) की एल्गोरिथम समस्याओं को शामिल करता है जो इन तर्कों को स्वचालित सत्यापन के लिए केंद्रीय बनाते हैं।

Core questions

• एक तर्क यह कैसे व्यक्त कर सकता है कि कुछ अच्छा अंततः होता है या कुछ बुरा कभी नहीं होता है?
• एकल निष्पादन के बारे में तर्क करने और सभी संभावित भविष्य के बारे में तर्क करने में क्या अंतर है?
• यह जाँच कैसे की जाती है कि कोई प्रणाली कालिक गुण को संतुष्ट करती है, इसे एल्गोरिथम कैसे बनाया जाता है?
• कौन से कालिक तर्क कुशल सत्यापन के विरुद्ध अभिव्यंजक शक्ति को संतुलित करते हैं?

Key theories

प्रोग्राम विशिष्टता के लिए कालिक तर्क

पानुएली ने दिखाया कि कालिक तर्क प्रतिक्रियाशील और समवर्ती प्रोग्रामों की शुद्धता को उनके निष्पादन पर गुणों को व्यक्त करके पकड़ता है, जो सुरक्षा और जीवंतता आवश्यकताओं के लिए एक समान भाषा प्रदान करता है।

शाखा-समय तर्क की मॉडल जाँच

क्लार्क और एमर्सन ने संगणना वृक्ष तर्क और एक एल्गोरिथम पेश किया ताकि इसे एक परिमित-राज्य मॉडल के विरुद्ध स्वचालित रूप से सत्यापित किया जा सके, जिससे मॉडल जाँच के क्षेत्र की स्थापना हुई।

Clinical relevance

कालिक तर्क मॉडल चेकर्स की विशिष्टता भाषाएँ हैं जिनका उपयोग हार्डवेयर डिज़ाइन, संचार प्रोटोकॉल और समवर्ती सॉफ़्टवेयर को सत्यापित करने के लिए नियमित रूप से किया जाता है, जो परिनियोजन से पहले डेडलॉक और सुरक्षा व जीवंतता के उल्लंघनों को पकड़ते हैं; इस तकनीक ने इसके मूल रचनाकारों को ट्यूरिंग पुरस्कार दिलाया और चिप डिज़ाइन में यह मानक है।

History

पानुएली ने 1977 में प्रोग्रामों के बारे में तर्क करने के लिए कालिक तर्क का प्रस्ताव रखा, और क्लार्क और एमर्सन ने, क्यूइल और सिफाकिस के साथ स्वतंत्र रूप से, 1981 के आसपास मॉडल जाँच विकसित की। यह दृष्टिकोण 1990 के दशक की शुरुआत में प्रतीकात्मक तरीकों के माध्यम से औद्योगिक प्रणालियों तक बढ़ा, और इसके रचनाकारों को इस तकनीक के लिए ट्यूरिंग पुरस्कार मिला।

Key figures

• Amir Pnueli
• Edmund Clarke
• E. Allen Emerson
• Joseph Sifakis

Seminal works

• clarkeEmerson1981
• huthRyan2004

Frequently asked questions

रैखिक-समय और शाखा-समय तर्क में क्या अंतर है?

LTL जैसे रैखिक-समय तर्क एक एकल, संभवतः अनंत, निष्पादन पथ के गुणों का वर्णन करते हैं। CTL जैसे शाखा-समय तर्क प्रत्येक राज्य से सभी संभावित भविष्य के वृक्ष पर मात्रा निर्धारित करते हैं, जिससे कोई यह कह सकता है कि किसी पथ के साथ या सभी पथों के साथ एक गुण धारण करता है। उनके पास अलग-अलग अभिव्यंजक शक्तियाँ और सत्यापन एल्गोरिदम हैं।

मॉडल जाँच इन तर्कों का उपयोग कैसे करती है?

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