← नवीनतम पेपर
💻 computer science

Hennessy-Milner Logic in CSLib, the Lean Computer Science Library

यह शोध पत्र लीन कंप्यूटर साइंस लाइब्रेरी (CSLib) के भीतर हेनेसी-मिलनर लॉजिक का एक सामान्य, पुन: प्रयोज्य औपचारिक रूप प्रस्तुत करता है, जिसमें एक पूर्ण मेटाथ्योरी शामिल है जो हेनेसी-मिलनर प्रमेय को समाहित करती है और स्वैच्छिक इमेज-फाइनाइट लेबल वाले ट्रांज़िशन सिस्टम्स (labelled transition systems) का समर्थन करने के लिए लीन के ऑटोमेशन का लाभ उठाती है।

मूल लेखक: Fabrizio Montesi, Marco Peressotti, Alexandre Rademaker

प्रकाशित 2026-02-18
📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें
CC BY 4.0

मूल लेखक: Fabrizio Montesi, Marco Peressotti, Alexandre Rademaker

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक विशाल, जटिल मशीन है—जैसे कि एक वीडियो गेम का पात्र, एक ट्रैफिक लाइट सिस्टम, या एक रोबोट वैक्यूम। आप यह जानना चाहते हैं: "यह चीज़ व्यवहार कैसे करती है?" और "क्या यह दूसरी मशीन की तरह ही बिल्कुल एक जैसा व्यवहार कर रही है?"

कंप्यूटर विज्ञान में, हम इन मशीनों के हर संभावित कदम को मैप करने के लिए Labelled Transition System (LTS) नामक एक ढांचे का उपयोग करते हैं। एक LTS को एक विशाल, शाखाओं वाले "चुनें अपना साहसिक कार्य" (Choose Your Own Adventure) वाली किताब की तरह समझें जहाँ हर पेज एक 'स्टेट' (state) है, और हर तीर एक लेबल वाला एक्शन है (जैसे "स्टार्ट दबाएं," "बाएं मुड़ें," या "संदेश भेजें")।

आप जिस शोध पत्र के बारे में पूछ रहे हैं, वह इन मशीनों का वर्णन करने के लिए एक सार्वीय नियम पुस्तिका (जिसे Hennessy–Milner Logic या HML कहा जाता है) बनाने और इस नियम पुस्तिका के पूरी तरह से सटीक होने को सिद्ध करने के बारे में है।

यहाँ उनके काम का सरल उपमाओं के माध्यम से विवरण दिया गया है:

1. समस्या: "क्या ये दो मशीनें जुड़वा हैं?"

कल्पना कीजिए कि आपके पास दो रोबोट हैं, रोबोट A और रोबोट B।

  • रोबोट A एक बटन दबा सकता है और एक ऐसे कमरे में जा सकता है जहाँ एक बिल्ली है।
  • रोबोट B एक बटन दबा सकता है और एक ऐसे कमरे में जा सकता है जहाँ एक कुत्ता है।

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

कंप्यूटर वैज्ञानिक Bisimulation का उपयोग करते हैं। यह एक "दर्पण परीक्षण" (mirror test) की तरह है। यदि रोबोट A एक कदम उठाता है, तो रोबोट B को एक मिलान करने वाला कदम उठाना चाहिए जो एक ऐसी स्थिति (state) की ओर ले जाए जो दिखने में उतनी ही अच्छी हो। यदि वे अनंत काल तक एक-दूसरे की नकल करना जारी रख सकते हैं, तो वे "bisimilar" (जुड़वा) हैं।

2. समाधान: "लॉजिक लैंग्वेज" (HML)

लेखकों ने इन मशीनों का वर्णन करने के लिए एक विशेष भाषा (HML) बनाई। मशीनों को "रोबोट A बिल्ली वाले कमरे में जाता है" कहने के बजाय, वे लॉजिकल वाक्यों का उपयोग करते हैं जैसे:

  • "डायमंड" (⟨μ⟩\langle \mu \rangle): "बटन μ\mu दबाना संभव है और अंततः ऐसी स्थिति में पहुँचना जहाँ ϕ\phi सत्य है।" (जैसे यह कहना: "खजाने तक जाने वाला एक रास्ता है।")
  • "बॉक्स" ([μ][\mu]): "चाहे आप बटन μ\mu को किसी भी तरह से दबाएं, आपको ऐसी स्थिति में पहुँचना ही होगा जहाँ ϕ\phi सत्य है।" (जैसे यह कहना: "हर रास्ता सुरक्षा की ओर ले जाता है।")

उन्होंने इस भाषा को Lean के भीतर बनाया है, जो एक शक्तिशाली उपकरण है जो एक अत्यंत सख्त गणित शिक्षक की तरह कार्य करता है। Lean उनके तर्क के हर कदम की जाँच करता है ताकि यह सुनिश्चित हो सके कि कोई गलती न हो।

3. बड़ी उपलब्धि: "द मिरर थ्योरम" (The Mirror Theorem)

उनके काम का सबसे प्रसिद्ध हिस्सा Hennessy–Milner Theorem को सिद्ध करना है।

इसे इस प्रकार समझें:

  • Bisimulation यह जाँचता है कि क्या दो मशीनें भौतिक रूप से पूर्ण तालमेल में चलती हैं।
  • Theory Equivalence यह जाँचता है कि क्या दो मशीनें हमारे लॉजिक लैंग्वेज में पूछे गए सवालों के एक ही सेट का "हाँ" में उत्तर देती हैं।

लेखकों ने यह जादुई तथ्य सिद्ध किया: उन मशीनों के लिए जिनमें अनंत शाखाओं वाली संभावनाएं नहीं होतीं (जिन्हें "image-finite" कहा जाता है), ये दोनों जाँच एक समान हैं।

यदि दो मशीनें हमारे लॉजिक लैंग्वेज में एक ही सवालों के जवाब देती हैं, तो वे भौतिक रूप से जुड़वा हैं। यदि वे भौतिक रूप से जुड़वा हैं, तो वे एक ही सवालों के जवाब देंगी। यह एक पूर्ण 1-टू-1 मिलान है।

4. यह पेपर क्यों महत्वपूर्ण है (The "CSLib" Part)

इससे पहले, लोग इन चीजों को जाँचने के लिए कोड लिखते थे, लेकिन वह अक्सर अव्यवस्थित, एक विशिष्ट प्रकार के रोबोट तक सीमित, या पुन: उपयोग करने में कठिन होता था।

लेखकों ने इस लॉजिक को एक लाइब्रेरी (एक टूलबॉक्स) के रूप में बनाया जिसे CSLib कहा जाता है।

  • उपमा: कल्पना कीजिए कि पिछले शोधकर्ताओं ने एक विशिष्ट बोल्ट के लिए एक कस्टम रिंच (wrench) बनाया था। लेखकों ने एक सार्वभौमिक, उच्च-गुणवत्ता वाला सॉकेट सेट बनाया जो किसी भी बोल्ट में फिट हो सके।
  • पुन: प्रयोज्यता (Reusability): क्योंकि उन्होंने इसे "Lean Computer Science Library" में बनाया है, इसलिए ऑटोमेटा, संचार प्रोटोकॉल या सॉफ्टवेयर सत्यापन पर काम करने वाले अन्य किसी भी व्यक्ति के लिए इस टूलबॉक्स को लेना और उपयोग करना आसान है। उन्हें पहिये का पुन: आविष्कार करने की आवश्यकता नहीं है।
  • स्वचालन (Automation): उन्होंने grind नामक एक विशेष तकनीक का उपयोग किया (इसे एक "जादुई इरेज़र" या "ऑटो-पायलट" समझें) जो उबाऊ, दोहराव वाले गणितीय प्रमाणों को स्वचालित रूप से हल करता है, जिससे शोधकर्ता बड़े विचारों पर ध्यान केंद्रित कर पाते हैं।

सारांश

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

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

अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?

आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।

Digest आज़माएँ →

इसी तरह के और पेपर

इस विषय के सभी पेपर देखें 💻 cs →