💻 computer science

DateSAT: A Framework for Solving Date and Period Constraints

यह शोध पत्र DateSAT को प्रस्तुत करता है, जो तिथियों और कैलेंडर अवधियों से जुड़ी संतुष्टि बाधाओं (satisfiability constraints) को पूर्णांक-आधारित SMT सूत्रों में बदलकर उन्हें औपचारिक रूप से व्यक्त करने और हल करने वाला पहला फ्रेमवर्क है, और एक क्यूरेटेड डेटासेट (450 बाधाओं) पर इसके अनुभवजन्य मूल्यांकन के माध्यम से इसकी प्रभावशीलता को प्रमाणित करता है।

मूल लेखक: Leyi Cui, Shrey Tiwari, Rohan Padhye

प्रकाशित 2026-05-26

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Leyi Cui, Shrey Tiwari, Rohan Padhye

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

कल्पना कीजिए कि आप एक पहेली सुलझाने की कोशिश कर रहे हैं: "परसों मैं 25 का था, और अगले साल मैं 28 का हो जाऊँगा।" यह कब संभव है?

एक इंसान के लिए, यह एक मज़ेदार दिमागी कसरत है। एक कंप्यूटर के लिए, यह एक बुरा सपना है। कंप्यूटर गणित में बहुत अच्छे होते हैं, लेकिन वे कैलेंडर के मामले में बहुत खराब होते हैं। वे यह नहीं "जानते" कि फरवरी में कभी 29 दिन होते हैं, या जनवरी 31 को "एक महीना" जोड़ने से वह फरवरी 31 पर नहीं पहुँचता (क्योंकि वह दिन अस्तित्व में ही नहीं है)।

यह शोध पत्र DateSAT पेश करता है, जो एक नया टूल है जिसे कंप्यूटर को तारीखों और समय की अवधियों के बारे में बिना भ्रमित हुए सोचना सिखाने के लिए डिज़ाइन किया गया है।

लेखकों ने इसे कुछ रोज़मर्रा के उपमाओं (analogies) का उपयोग करके इस प्रकार समझाया है:

1. समस्या: कंप्यूटर को "धुंधला" समय पसंद नहीं है

कंपमर को एक बहुत ही सख्त लाइब्रेरियन की तरह समझें जो केवल सटीक संख्याओं को समझता है। यदि आप उससे किसी तारीख में "1 महीना" जोड़ने के लिए कहते हैं, तो वह घबरा जाता है यदि गणित पूरी तरह से मेल नहीं खाता।

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

2. समाधान: DateSAT (एक "कैलेंडर अनुवादक")

लेखकों ने DateSAT नामक एक फ्रेमवर्क बनाया है। DateSAT को एक अनुवादक (translator) के रूप में समझें जो एक इंसान के जटिल तारीख वाले सवाल और कंप्यूटर के सख्त गणितीय दिमाग के बीच बैठता है।

इनपुट (Input): आप DateSAT को ऐसा सवाल देते हैं जैसे, "क्या यह संभव है कि कोई कंपनी स्टॉक खरीदने के 500 दिनों बाद कानूनी चुनाव कर सके, यदि समय सीमा 'अधिग्रहण तिथि' के 9 महीने बाद की है?"
जादू: DateSAT इस उलझे हुए, मानवीय भाषा वाले कैलेंडर के सवाल को एक साफ, सख्त गणितीय समस्या में अनुवादित कर देता है जिसे एक कंप्यूटर सॉल्वर (जिसे SMT सॉल्वर कहा जाता है) पूरी सटीकता से संभाल सकता है।

3. यह कैसे काम करता है: पाँच अलग-अलग "नक्शे"

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

द नैव मैप (The Naive Map - कदम-दर-कदम चलने वाला): यह विधि दिन-दर-दिन चलने की कोशिश करती है। यदि आप 100 दिन जोड़ते हैं, तो यह 100 छोटे कदम उठाती है। यह बहुत सटीक है लेकिन अविश्वसनीय रूप से धीमी है, जैसे किसी देश को एक-एक फुट करके पार करना।
द एपोक मैप (The Epoch Map - मील के पत्थर का निशान): यह विधि एक निश्चित शुरुआती बिंदु (जैसे "1 मार्च, 2000") चुनती है और गिनती है कि तब से कितने दिन बीत चुके हैं। यह दिन जोड़ने के लिए बेहतरीन है, लेकिन जब आपको "महीनों" या "वर्षों" के हिसाब से कूदना हो, तो यह भ्रमित हो जाती है।
द हाइब्रिड मैप (The Hybrid Map - दोहरा दृष्टिकोण): यह रणनीति एक साथ दो नक्शों का उपयोग करती है। यह दिन जोड़ने के लिए "मील के पत्थर" वाले नक्शे का उपयोग करती है और महीने जोड़ने के लिए "कदम-दर-कदम" वाले नक्शे का। यह समय बचाने के लिए केवल आवश्यकता पड़ने पर ही उनके बीच स्विच करती है।
द अल्फा-बीटा मैप (The Alpha-Beta Map - कैलेंडर ग्रिड): यह एक चतुर शॉर्टकट है। हर एक दिन को गिनने के बजाय, यह गिनता है कि "कितने महीने बीत चुके हैं" और "वर्तमान महीने में कितने दिन बीते हैं।" यह ऐसा है जैसे यह जानना कि आप "गली 5, मकान 3" पर हैं, बजाय इसके कि शहर की शुरुआत से हर घर को गिना जाए।
द अल्फा-बीटा-टेबल मैप (The Alpha-Beta-Table Map - चीट शीट): यही विजेता है। यह "कैलेंडर ग्रिड" के विचार का उपयोग करता है लेकिन इसमें एक पहले से लिखी हुई चीट शीट भी जुड़ी होती है। चूंकि कैलेंडर चक्रों (हर 4 साल में) में दोहराए जाते हैं, इसलिए यह टूल हर बार गणित करने के बजाय बस एक टेबल में उत्तर ढूँढ लेता है। यह सबसे तेज़ तरीका है, जो जटिल समस्याओं को धीमी "नैव" विधि की तुलना में 2.4 गुना तेज़ी से हल करता है।

4. टेस्ट ड्राइव: DateSATBench

यह साबित करने के लिए कि उनका टूल काम करता है, लेखकों ने केवल मनगढ़ंत सवाल नहीं बनाए। उन्होंने DateSATBench नामक एक टेस्ट सूट बनाया जिसमें 450 अलग-अलग समस्याएं थीं:

100 जटिल मामलों को खोजने के लिए AI द्वारा जनरेट की गई थीं।
150 बेतरतीब ढंग से जनरेट किए गए "स्ट्रेस टेस्ट" थे जिन्हें सिस्टम को तोड़ने के लिए डिज़ाइन किया गया था।
200 वास्तविक अमेरिकी टैक्स कानूनों से लिए गए थे ताकि देखा जा सके कि क्या यह वास्तविक कानूनी दस्तावेजों को संभाल सकता है।

परिणाम:

टूल ने एक मिनट से कम समय में 85% समस्याओं को हल किया।
"चीट शीट" विधि (Alpha-Beta-Table) स्पष्ट विजेता थी, जिसने उन समस्याओं को सेकंड के एक अंश में हल किया जिन्हें "नैव" विधि को हल करने में बहुत अधिक समय लगा।
एक परीक्षण में, उन्होंने पायथन (Python) के एक फंक्शन में छिपे हुए बग को पाया जिसे दो अलग-अलग प्रोग्रामरों ने यह जांचने के लिए लिखा था कि क्या कोई तारीख 18 महीने की अवधि के भीतर है। मानव परीक्षकों ने इस बग को मिस कर दिया, लेकिन DateSAT ने इसे तुरंत ढूंढ लिया।

5. यह क्यों महत्वपूर्ण है

शोध पत्र निष्कर्ष निकालता है कि DateSAT पहला ऐसा टूल है जो कंप्यूटर को तारीखों और अवधियों के बारे में प्रतीकात्मक रूप से (symbolically) सोचने की अनुमति देता है। इसका मतलब है कि यह जांच सकता है कि कोड का कोई हिस्सा समय के संबंध में तार्किक रूप से सही है या नहीं, या क्या किसी कानूनी अनुबंध में उसकी तारीखों के संबंध में कोई विरोधाभास है, और इसके लिए उसे यह देखने के लिए कोड को लाखों बार चलाने की आवश्यकता नहीं है कि वह क्रैश हो जाता है या नहीं।

संक्षेप में, DateSAT कंप्यूटर को कैलेंडर की "सामान्य समझ" (common sense) देता है, जिससे तारीख-संबंधी तर्क को महंगे बगों के स्रोत से बदलकर एक हल करने योग्य गणितीय समस्या में बदल दिया जाता है।

तकनीकी सारांश: DateSAT

समस्या विवरण (Problem Statement)

सॉफ्टवेयर विश्लेषण, डेटा प्रोसेसिंग और कानूनी दस्तावेज़ तर्क (legal document reasoning) में तिथियाँ (dates) और कैलेंडर अवधियाँ (calendar periods) सर्वव्यापी हैं। हालाँकि, कैलेंडर संबंधी तर्क स्वाभाविक रूप से त्रुटि-प्रवण (error-prone) होता है क्योंकि इसमें अनियमित महीनों की लंबाई, लीप वर्ष और अवधि अंकगणित (जैसे कि "एक महीना" जोड़ने बनाम "एक दिन" जोड़ने की गैर-क्रमविनिमेयता/non-commutativity) में अस्पष्टता होती है। मौजूदा प्रोग्राम विश्लेषण और सत्यापन उपकरण तिथियों के लिए मूल समर्थन (native support) की कमी रखते हैं, जिससे वे या तो ठोस निष्पादन (concrete execution) पर निर्भर रहते हैं या लाइब्रेरी कार्यान्वयन (जैसे dateutil) के जटिल प्रतीकात्मक ट्रेसिंग (symbolic tracing) पर, जो अक्सर बाधा विस्फोट (constraint explosion) का कारण बनता है। इसके अतिरिक्त, लार्ज लैंग्वेज मॉडल्स (LLMs) अक्सर टेम्पोरल रीजनिंग (temporal reasoning) कार्यों में विफल रहते हैं। मुख्य समस्या तिथियों और कैलेंडर अवधियों से जुड़ी संतुष्टि बाधाओं (satisfiability constraints) को प्रतीकात्मक रूप से व्यक्त करने और हल करने के लिए एक औपचारिक ढांचे (formal framework) के अभाव की है।

कार्यप्रणाली (Methodology)

यह शोध पत्र DateSAT प्रस्तुत करता है, एक ऐसा ढांचा जो क्वांटिफायर-फ्री लीनियर इंटीजर अरिथमेटिक (QF-LIA) को दो नए सॉर्ट्स (sorts): Date और Period के साथ विस्तारित करता है।

औपचारिकीकरण (Formalization)

सिमेंटिक्स (Semantics): तिथियों को ग्रेगोरियन कैलेंडर नियमों के अनुसार ट्रिपल्स $(y, m, d)$ $(y, m, d)$ के रूप में परिभाषित किया गया है। अवधियाँ (Periods) ट्रिपल्स $(n_y, n_m, n_d)$ $(n_{y}, n_{m}, n_{d})$ हैं। यह ढांचा तिथि-अवधि जोड़ (date-period addition) के लिए एक विशिष्ट सिमेंटिक्स अपनाता है (जो Java के java.time और Python के dateutil जैसी लाइब्रेरी के अनुरूप है):
1. वर्ष/माह जोड़: इसे पहले किया जाता है, जिसमें ओवरफ्लो हैंडलिंग के लिए अमान्य तिथियों को नीचे की ओर राउंड (round down) किया जाता है (उदाहरण के लिए, Jan 31 + 1 month $\to$ Feb 28/29)।
2. दिन जोड़: इसे दूसरे स्थान पर किया जाता है, जो अगले महीनों में ओवरफ्लो की अनुमति देता है।
  यह सिमेंटिक्स सुनिश्चित करता है कि एक वैध तिथि में अवधि जोड़ने से हमेशा एक वैध तिथि प्राप्त होती है (प्रमेय 1)।
इनपुट भाषा: भाषा मुक्त तिथि वेरिएबल्स, तिथि/अवधि अंकगणित, तुलना, और घटक निष्कर्षण (वर्ष, माह, दिन) का समर्थन करती है। इस तर्क को QF-LIA में रिडक्शन के माध्यम से निर्णायक (decidable) सिद्ध किया गया है।

समाधान रणनीतियाँ (Solving Strategies)

लेखक पाँच एन्कोडिंग रणनीतियाँ प्रस्तावित करते हैं जो DateSAT बाधाओं को पूर्णांकों (integers) पर SMT फॉर्मुलों में मैप करने के लिए हैं, जिन्हें Z3 सॉल्वर का उपयोग करके लागू किया गया है। ये रणनीतियाँ लॉजिकल डेप्थ (इफ-देन-एल्स/ITE ब्लॉक्स का नेस्टिंग) और अरिथमेटिक कॉम्प्लेक्सिटी (पूर्णांक ऑपरेशन्स की संख्या) के बीच संतुलन बनाती हैं:

नेइव एन्कोडिंग (Naive Encoding): तिथियों को $(y, m, d)$ टुपल्स के रूप में प्रस्तुत करता है। तिथि-अवधि अंकगणित को चरण-दर-चरण अनरोल किया जाता है, जिससे दिन के ओवरफ्लो के लिए नेस्टेड ITEs के कारण $O(|n_d|)$ लॉजिकल डेप्थ उत्पन्न होती है।
एपोक-आधारित एन्कोडिंग (Epoch-based Encoding): तिथियों को एक निश्चित एपोक (epoch) से $\Delta$ दिनों के रूप में एक एकल पूर्णांक के रूप में प्रस्तुत करता है। लेखक लीप-वर्ष चक्रों (1461-दिवसीय चक्र) को सरल बनाने के लिए मार्च 1, 2000 को एपोक के रूप में चुनते हैं। दिन जोड़ना $O(1)$ हो जाता है, लेकिन वर्ष/माह अंकगणित के लिए $\Delta$ को वापस $(y, m, d)$ में बदलने की आवश्यकता होती है, जिससे जटिल डिवीजन/मॉड्यूलो बाधाएं आती हैं।
हाइब्रिड एन्कोडिंग (Hybrid Encoding): प्रत्येक तिथि के लिए $(y, m, d)$ और $\Delta$ दोनों प्रस्तुतियों को बनाए रखता है। यह आवश्यक होने पर ही (जैसे, केवल दिन वाले ऑपरेशन्स के लिए $\Delta$ का उपयोग करना और माह अंकगणित के लिए $(y, m, d)$ का उपयोग करना) प्रतिनिधित्व बदलने के लिए 'लेजी कंसिस्टेंसी फ्लैग्स' का उपयोग करता है।
अल्फा-बीटा एन्कोडिंग (Alpha-Beta Encoding): एक तिथि को $(\alpha, \beta)$ जोड़े के रूप में प्रस्तुत करता है, जहाँ $\alpha$ एपोक से महीनों की संख्या है और $\beta$ उस महीने के भीतर दिन का ऑफसेट है। यह माह की लंबाई निर्धारित करने के लिए मॉड्यूलर अंकगणित का उपयोग करके गहरे नेस्टिंग से बचता है।
अल्फा-बीटा-टेबल एन्कोडिंग (Alpha-Beta-Table Encoding): बाउंडेड इंस्टेंस (1900–2100) के लिए अल्फा-बीटा रणनीति का एक अनुकूलन। यह दिनों-में-माह (days-in-month) और दिनों-से-पहले-माह (days-before-month) के लिए पूर्व-गणना की गई लुकअप टेबल्स (48-माह चक्र) का उपयोग करता है, जो जटिल अंकगणित को ऐरे लुकअप और मॉड्यूलो ऑपरेशन्स से बदल देता है।

शुद्धता सत्यापन (Correctness Verification)

नेइव बेसलाइन के सापेक्ष एपोक-आधारित, हाइब्रिड और अल्फा-बीटा एन्कोडिंग की शुद्धता को Verus प्रूफ असिस्टेंट का उपयोग करके औपचारिक रूप से सत्यापित किया गया था। ये प्रमाण स्थापित करते हैं कि ये एन्कोडिंग अच्छी तरह से निर्मित (well-formed) बाधाओं के लिए नेइव एन्कोडिंग के साथ इक्विसेटेसिफिएबल (equisatisfiable) हैं।

बेंचमार्क और मूल्यांकन (Benchmark and Evaluation)

लेखकों ने तीन स्रोतों से 450 बाधाओं का एक डेटासेट DateSATBench तैयार किया:

LLM-सिंथेसाइज्ड (100): सिमेंटिक एज केस (जैसे, लीप वर्ष, माह की सीमाएं) पर केंद्रित।
ग्रामर-सैंपलड (150): कठिन/असंतोषजनक मामलों पर परीक्षण करने के लिए रैंडमली जनरेट किया गया।
लीगली ग्राउंडेड (200): अमेरिकी आंतरिक राजस्व संहिता (U.S. Internal Revenue Code) के कानूनों (जैसे, धारा 338(g) चुनाव समय सीमा) से लिया गया।

परिणाम:

प्रदर्शन: लीगल डेटासेट पर, Alpha-Beta-Table रणनीति ने सर्वश्रेष्ठ प्रदर्शन किया, जिसने 0.13 सेकंड के औसत समय के साथ 98.45% बाधाओं को हल किया।
स्पीडअप: नेइव बेसलाइन की तुलना में, पूरे बेंचमार्क सूट (430 समाधान योग्य बाधाएं) में Alpha-Beta-Table ने 2.41× का औसत स्पीडअप प्रदान किया।
दक्षता: हाइब्रिड रणनीति ने ग्रामर-सैंपलड बाधाओं पर महत्वपूर्ण सुधार दिखाया (औसत समय 4.69s बनाम नेइव के लिए 28.07s), जबकि एपोक-आधारित रणनीति सरल LLM-सिंथेसाइज्ड मामलों में उत्कृष्ट रही।
स्केलेबिलिटी: जैसे-जैसे बाधाएं अधिक जटिल होती गईं, एन्कोडिंग रणनीति का चयन अत्यंत महत्वपूर्ण हो गया, जहाँ अल्फा-बीटा-टेबल रणनीति ने मजबूती बनाए रखी जहाँ अन्य रणनीतियां टाइम-आउट हो गईं।

मुख्य योगदान (Key Contributions)

औपचारिकीकरण: तिथि और अवधि बाधा संतुष्टि का एक कठोर विवरण, जिसमें अंकगणित और तुलना के सिमेंटिक्स शामिल हैं।
रणनीतियाँ: पूर्णांक अंकगणित में तिथि तर्क को कम करने के लिए पांच अलग-अलग एन्कोडिंग रणनीतियाँ, जो लॉजिकल डेप्थ और अरिथमेटिक कॉम्प्लेक्सिटी के बीच संतुलन बनाती हैं।
कार्यान्वयन: Z3 का उपयोग करके एक ओपन-सोर्स पायथन कार्यान्वयन, जो cmu-pasta/DateSAT पर उपलब्ध है।
बेंचमार्क: तिथि तर्क उपकरणों का मूल्यांकन करने के लिए DateSATBench सूट (450 बाधाएं)।
मूल्यांकन: एक अनुभवजन्य अध्ययन (empirical study) जो दर्शाता है कि विशेष एन्कोडिंग, विशेष रूप से जटिल कानूनी और सिंथेटिक बाधाओं के लिए, नेइव दृष्टिकोणों की तुलना में काफी बेहतर प्रदर्शन करती है।

महत्व और दावे (Significance and Claims)

शोध पत्र दावा करता है कि यह तिथियों और कैलेंडर अवधियों से जुड़ी संतुष्टि बाधाओं को व्यक्त करने और हल करने वाला पहला ढांचा है। इसका महत्व निम्नलिखित में निहित है:

अंतराल को भरना: तिथि तर्क के बारे में औपचारिक तर्क करने के लिए टूल सपोर्ट की कमी को संबोधित करना, जो सॉफ्टवेयर बग्स (जैसे, पेटेंट समाप्ति त्रुटियां, क्लाउड आउटेज) का एक ज्ञात स्रोत है।
सत्यापन को सक्षम करना: कोड रिफैक्टरिंग में समानता (equivalence) को सत्यापित करने (जैसे, कस्टम लॉजिक के साथ लाइब्रेरी कॉल्स को बदलना) और त्रुटि-प्रवण LLMs या व्यापक ठोस परीक्षणों पर निर्भर रहने के बजाय कानूनी अनुपालन को मान्य करने के लिए एक तंत्र प्रदान करना।
भविष्य के कार्य के लिए आधार: एक बेंचमार्क और सॉल्वर प्रदान करना जिसे सटीक टेम्पोरल रीजनिंग की आवश्यकता वाले प्रोग्राम वेरिफिकेशन टूल्स और एजेंटिक AI सिस्टम में एकीकृत किया जा सके।

लेखक विनम्र रहते हुए कहते हैं कि हालांकि उनका वर्तमान कार्यान्वयन बैकएंड के रूप में Z3 का उपयोग करता है, भविष्य के कार्यों में इसे SMT-LIB में एक नए सिद्धांत के रूप में सीधे एकीकृत करना या बाउंडेड इंस्टेंस के लिए बिटवेक्टर एन्कोडिंग का पता लगाना शामिल हो सकता। वे इस बात पर जोर देते हैं कि उनका कार्य टेम्पोरल कंप्यूटेशन के बारे में सिद्धांतवादी तर्क (principled reasoning) की दिशा में एक मौलिक कदम है।

1. समस्या: कंप्यूटर को "धुंधला" समय पसंद नहीं है

2. समाधान: DateSAT (एक "कैलेंडर अनुवादक")

3. यह कैसे काम करता है: पाँच अलग-अलग "नक्शे"

4. टेस्ट ड्राइव: DateSATBench

5. यह क्यों महत्वपूर्ण है

तकनीकी सारांश: DateSAT

समस्या विवरण (Problem Statement)

कार्यप्रणाली (Methodology)

औपचारिकीकरण (Formalization)

समाधान रणनीतियाँ (Solving Strategies)

शुद्धता सत्यापन (Correctness Verification)

बेंचमार्क और मूल्यांकन (Benchmark and Evaluation)

मुख्य योगदान (Key Contributions)

महत्व और दावे (Significance and Claims)

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