💻 Category

cs.LO

1090 पेपर

💻 computer science

Revisiting average case complexity of multilevel syllogistic: From the 1995 Courant Technical Report to Lean 4 Formalization

यह शोध पत्र मल्टीलेवल सिलोगिस्टिक (Multilevel Syllogistic) की औसत-मामले की जटिलता (average-case complexity) पर 1995 की कोर्टेंट तकनीकी रिपोर्ट (Courant Technical Report) का एक लीन 4 (Lean 4) औपचारिकीकरण प्रस्तुत करता है, जो इसके अर्थविज्ञान (semantics), निर्णय प्रक्रियाओं (decision procedures) और जटिलता परिणामों को एनकोडिंग करके सशर्त एनपी-औसत पूर्णता (NP-average completeness) और गैर-एवीपी (non-AvP) कठोरता के उपसंयोजकों (corollaries) को स्थापित करता है।

Lars Warren Ericson2026-06-16
💻 computer science

The Complexity of Bisimilarity and Model Checking in Finitary Diagrams

यह शोध पत्र व्युत्क्रमणीय आवेों (invertible matrices) के अस्तित्व संबंधी सिद्धांत (ETIM) के लिए एक कुशल यादृच्छिक एल्गोरिदम पेश करके, फिनिटरी आरेखों (finitary diagrams) में बिसिमिलरिटी (bisimilarity) और मॉडल चेकिंग के लिए जटिलता सीमाओं में महत्वपूर्ण सुधार करता है, बिसिमिलरिटी के लिए एक NEXP ऊपरी सीमा और आरेखीय पथ तर्क (diagrammatic path logic) के लिए एक मिलान वाली NP-पूर्ण सीमा स्थापित करता है, साथ ही परिमित क्षेत्रों (finite fields) के लिए जटिलता को परिष्कृत करता है और ETIM के एक विशेष रैखिक समूह संस्करण को वास्तविकों के अस्तित्व संबंधी सिद्धांत (existential theory of the reals) के समकक्ष के रूप में अभिलक्षणित करता है।

Markus Bläser, Sagnik Dutta, Samuel Okyay2026-06-16
💻 computer science

An Efficient MaxSAT-DDD Approach for Train Rescheduling via Precedence Propagation and Hybrid AMO Encodings

यह शोध पत्र ट्रेन पुनर्गठन (train rescheduling) के लिए एक कुशल MaxSAT-DDD दृष्टिकोण प्रस्तुत करता है जो संसाधन संघर्षों (resource conflicts) के हाइब्रिड एनकोडिंग के साथ प्राथमिकता प्रसार (precedence propagation) को जोड़कर रनटाइम को काफी कम कर देता है, और विभिन्न विलंब उद्देश्यों (delay objectives) पर मौजूदा MILP और CP मॉडलों से बेहतर प्रदर्शन करता है।

Tuyen Van Kieu, Tan Huu Nguyen, Khanh Van To2026-06-16
🤖 AI

Symbolic Informalization: Fluent, Productive, Multilingual

यह शोध पत्र इन्फॉर्मथ (Informath) प्रोजेक्ट का परिचय देता है, जो एक डेडक्टी हब (Dedukti hub) और ग्रामैटिकल फ्रेमवर्क (Grammatical Framework) पर निर्मित एक प्रतीकात्मक अनौपचारिककरण ढांचे (symbolic informalization framework) का उपयोग करता है ताकि एगडा (Agda), लीन (Lean) और रॉक (Rocq) जैसे सिस्टम के औपचारिक प्रमाणों को प्रवाहपूर्ण, सटीक और बहुभाषी प्राकृतिक भाषा में विश्वसनीय रूप से परिवर्तित किया जा सके।

Aarne Ranta2026-06-16
💻 computer science

Constructive Preference Relations: Navigating Undecidability in Rational LTL Contraction

यह शोध पत्र यह प्रदर्शित करता है कि तर्कसंगत LTL विश्वास संकुचन (belief contraction) के लिए ज्ञानमीमांसीय वरीयता संबंधों (epistemic preference relations) का निर्माण करना अनिर्णायक (undecidable) है और इस सीमा को पार करने तथा पूर्ण तर्कसंगतता प्राप्त करने के लिए नवीन, प्रभावी निर्माणों—जिसमें सामान्यीकृत दूरी माप (generalized distance measures) और पदानुक्रमित संरचनाएं (hierarchical compositions) शामिल हैं—का प्रस्ताव करता है।

Hannes Gaißer, Dominik Klumpp, Jandson S. Ribeiro2026-06-16
💻 computer science

Automating Boundary Filling in Cubical Type Theories

यह शोधपत्र एक प्रयोगात्मक हैस्केल (Haskell) सॉल्वर प्रस्तुत करता है जो पोसेट मैप्स (poset maps) के माध्यम से कंटोर्शन सॉल्विंग (contortion solving) के लिए ह्यूरिस्टिक्स और कान सॉल्विंग (Kan solving) के लिए कंस्ट्रेंट सेटिस्फैक्शन प्रोग्रामिंग का उपयोग करके क्यूबिकल टाइप थ्योरी में निर्दिष्ट सीमाओं वाले क्यूब्स के निर्माण को स्वचालित करता है, जिससे उच्च-आयामी समीकरण संबंधी तर्क (higher-dimensional equational reasoning) की जटिल संयोजकता (combinatorics) का समाधान किया जा सके।

Maximilian Doré, Evan Cavallo, Anders Mörtberg2026-06-15
🔢 mathematics

Hypercubical manifolds in homotopy type theory

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

Samuel Mimram, Émile Oleon2026-06-15
🤖 AI

History of the Muddy Children Puzzle

यह शोध पत्र तार्किक और साहित्यिक प्रकाशनों के माध्यम से 'मडी चिल्ड्रन पज़ल' (Muddy Children Puzzle) की दो शताब्दी पुरानी उत्पत्ति का पता लगाता है, इसके अनेक विविध रूपों का अन्वेषण करता है, और एक नवीन स्व-संदर्भित 'हैट्स पज़ल' (hats puzzle) प्रस्तुत करता है।

Hans van Ditmarsch2026-06-15
💻 computer science

From Phase Semantics to Base-extension Semantics (and back)

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

Ekaterina Piotrovskaya2026-06-15
💻 computer science

Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility

यह शोध पत्र सिद्ध करता है कि विभाज्यता के साथ अस्तित्वगत प्रेस्टरर अंकगणित (EPAD) के लिए संतुष्टि समस्या (satisfiability problem) PP-कठिन (PP-hard) है, जिससे उस लंबे समय से चले आ रहे अनुमान का खंडन होता है कि यह NP में है, क्योंकि यह इसे योग और शिफ्ट्स पर आधारित अंकगणितीय सर्किटों के लिए एक थ्रेशोल्ड गुणांक समस्या (threshold coefficient problem) में अपचयित (reduce) करता है।

Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez2026-06-15