क्लेन बीजगणित: Difference between revisions

Latest revision as of 16:03, 14 June 2023

गणित में, क्लेन बीजगणित (/ˈkleɪni/ क्ले-नी; स्टीफन कोल क्लेन के नाम पर रखा गया) निष्क्रिय (और इस प्रकार आंशिक रूप से आदेशित) सेमीरिंग होता है जो क्लोजर ऑपरेटर के साथ संपन्न है। यह नियमित अभिव्यक्ति से ज्ञात संचालन को सामान्य करता है।^[1]

परिभाषा

साहित्य में क्लेन बीजगणित और संबंधित संरचनाओं की विभिन्न असमान परिभाषाएं दी गई हैं।^[2] यहां हम वह परिभाषा देते है जो आजकल सबसे सामान्य लगती है।

क्लेन बीजगणित समुच्चय (गणित) A है जो दो बाइनरी संक्रियाओं के साथ + : A × A → A और · : A × A → A और फलन ^* : A → A क्रमशः a + b, ab और a^* के रूप में लिखा जाता है, जिससे कि निम्नलिखित स्वयंसिद्ध संतुष्ट है।

+ और · की संबद्धता : a + (b + c) = (a + b) + c और a (bc) = (ab) c A में सभी a, b, c के लिए।
+ की क्रमविनिमेयता : a + b = b + a सभी a, b में A के लिए।
वितरण : ए (b + c) = (ab) + (ac) और (b + c) a = (ba) + (ca) A में सभी a, b, c के लिए।
+ और · के लिए पहचान तत्व : A में तत्व 0 उपस्तिथ होता है जैसे A में सभी के लिए: a + 0 = 0 + a = a.
A में अवयव 1 उपस्तिथ होता है जैसे A में सभी A के लिए : a1 = 1a = a.
a में सभी A के लिए 0: a0 = 0a = 0 द्वारा अवशोषक तत्व।

उपरोक्त स्वयंसिद्ध सेमिरिंग को परिभाषित करते हैं। अतः हमें और आवश्यकता होता है।

+ उदासीन है : A में सभी a के लिए a + a = a.

A पर आंशिक क्रम ≤ परिभाषित करना संभव होता है, अतः a ≤ b समूह करके और a + b = b (या समकक्ष: a ≤ b यदि A में x उपस्तिथ होता है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ होता है a = b)। इस क्रम से हम संक्रिया ^* के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं।

1 + a (a^*) ≤ a^* सभी के लिए A में।
1 + (a^*)a ≤ a^* सभी के लिए A में।
यदि a और x, A में ऐसे हैं कि ax ≤ x, तब a^*x ≤ x
यदि a और x, A में ऐसे हैं कि xa ≤ x, तब x(a^*) ≤ x ^[3]

सामान्यतः सहज रूप से, किसी को a + b को संघ के रूप में या a और b की कम से कम ऊपरी सीमा और ab को कुछ गुणन के रूप में सोचा जाता है, जो मोनोटोनिक फ़ंक्शन क्रम सिद्धांत में होता है, इस अर्थ में कि a ≤ b का अर्थ ax ≤ bx है। इस प्रकार स्टार ऑपरेटर के पीछे का विचार यह होता है कि a^* = 1 + a + aa + aaa + ... प्रोग्रामिंग भाषा सिद्धांत के दृष्टिकोण से, कोई भी + को पसंद के रूप में, · को अनुक्रमण के रूप में और ^* पुनरावृत्ति के रूप में व्याख्या कर सकता है।

उदाहरण

सांकेतिक पत्राचार के मध्य
क्लेन बीजगणित और	+	·	^*	0	1
नियमित अभिव्यक्ति	\|	नहीं लिखा	^*	∅	ε

माना Σ परिमित उपसमूह (वर्णमाला) हो और A को Σ पर सभी नियमित अभिव्यक्ति औपचारिक भाषा सिद्धांतों का समूह होता है। यदि वह ही औपचारिक भाषा का वर्णन करते हैं तब हम दो ऐसे नियमित भावों को समान मानते हैं। तब A क्लेन बीजगणित बनाता है। सामान्यतः यह इस अर्थ में मुक्त वस्तु क्लेन बीजगणित होती है कि नियमित अभिव्यक्तियों के मध्य कोई भी समीकरण क्लेन बीजगणित के स्वयंसिद्धों से अनुसरण करता है और इसलिए प्रत्येक क्लेन बीजगणित में मान्य होता है।

पुनः मान लीजिए Σ अक्षर होता है। मान लीजिए A Σ पर सभी नियमित भाषाओं का समूह होता है (या Σ पर सभी संदर्भ-मुक्त भाषाओं का समूह होता है, या Σ पर सभी पुनरावर्ती भाषाओं का समूह है या Σ पर सभी भाषाओं का समूह होता है)। तब संघ (समूह सिद्धांत) (+ के रूप में लिखा जाता है) और A के दो तत्वों का संयोजन (लिखा जाता है) फिर से A से संबंधित होता है और इसलिए क्लेन स्टार ऑपरेशन A के किसी भी तत्व पर प्रयुक्त होता है। इस प्रकार हम क्लेन बीजगणित A प्राप्त करते हैं जिसमें 0 रिक्त समूह होता है और 1 वह समूह होता है जिसमें केवल रिक्त स्ट्रिंग होती है।

सामान्यतः M को पहचान कर तत्व e के साथ मोनोइड होने देता है और A को M के सभी उपसमूहों का समूह होने देता है। इस प्रकार दो ऐसे उपसमूह S और T के लिए, S + T को S और T का संघ होने देता है और ST = {st: s में S समूह करना और t में T}। S^* को S द्वारा उत्पन्न M के सबमोनॉइड के रूप में परिभाषित किया गया है, जिसे {e} ∪ S ∪ SS ∪ SSS ∪ ... के रूप में वर्णित किया जा सकता है ... पुनः A रिक्त बीजगणित बनाता है जिसमें 0 रिक्त समूह होता है और 1 {e} किसी भी छोटी श्रेणी के सिद्धांत के लिए समान रूप से निर्माण किया जा सकता है।

इस प्रकार क्षेत्र के ऊपर इकाई बीजगणित के रैखिक उपस्थान क्लेन बीजगणित बनाते हैं। अतः रैखिक उपसमष्टियाँ V और W को देखते हुए, V + W को दो उपसमष्टियों के योग के रूप में और 0 को तुच्छ उपसमष्टि {0} के रूप में परिभाषित करता है। परिभाषित करना $V \cdot W = span {v \cdot w | v \in V, w \in W}$ , क्रमशः V और W से सदिश के उत्पाद की रैखिक अवधि को परिभाषित करना $1 = span {I}$ , बीजगणित की इकाई की अवधि V का बंद होना V की सभी शक्तियों के मॉड्यूल का प्रत्यक्ष योग होता है।

V^{*}=\bigoplus _{i=0}^{\infty }V^{i}

मान लीजिए कि M समुच्चय है और A, M पर सभी द्विआधारी संबंधों का समुच्चय होता है। इस प्रकार + होने के लिए और ^* रिफ्लेक्सिव ट्रांजिटिव क्लोजर हम क्लेन बीजगणित प्राप्त करते हैं।

संचालन के साथ प्रत्येक बूलियन बीजगणित (संरचना) $\lor$ और $\land$ यदि हम उपयोग करते हैं तब यह क्लेन बीजगणित में परिवर्तित हो जाता है $\lor$ + के लिए, $\land$ के लिए · और समूह के लिए a^* = 1 समूह करता है।

फ़्लॉइड-वॉर्शल एल्गोरिथम को प्रयुक्त करने के लिए अधिक भिन्न क्लेन बीजगणित का उपयोग किया जा सकता है, क्लेन के एल्गोरिथ्म द्वारा ग्राफ सिद्धांत के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई की गणना, नियतात्मक परिमित ऑटोमेटन के प्रत्येक दो राज्यों के लिए नियमित अभिव्यक्ति की गणना करता है। इस प्रकार विस्तारित वास्तविक संख्या रेखा का उपयोग करते हुए, a + b को न्यूनतम a और b और ab को a और b का सामान्य योग होने के लिए लिया जाता है (+∞ और −∞ के योग को +∞ के रूप में परिभाषित किया जा रहा है)। a^* को गैर-ऋणात्मक a के लिए वास्तविक संख्या शून्य और ऋणात्मक a के लिए −∞ के रूप में परिभाषित किया गया है। यह क्लेन बीजगणित है जिसमें शून्य तत्व +∞ और तत्व वास्तविक संख्या शून्य है। इस प्रकार भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है। अतः किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के मध्य सबसे छोटी पथ लंबाई का मूल्यांकन करती है।^[4]

गुण

0 ≤ a सभी a के लिए A में शून्य सबसे छोटा अवयव होता है।

योग a + b, a और b की सबसे छोटी ऊपरी सीमा होती है। इस प्रकार हमारे समीप a ≤ a + b और b ≤ a + b है और यदि x, A का तत्व है जिसमें a ≤ x और b ≤ x है, तब a + b ≤ x होता है। इसी प्रकार, a₁ + ... + a_n तत्वों a₁, ..., a_n का सबसे कम से कम ऊपरी सीमा है।

गुणन और योग एकदिष्ट होता हैं। यदि a ≤ b, तब

a + x ≤ b + x,
ax ≤ bx, और
xa ≤ xb

A में सभी x के लिए।

स्टार ऑपरेशन के संबंध में, हमारे समीप है।

0^* = 1 और 1^* = 1,
a ≤ b का अर्थ है a^* ≤ b^* (एकरसता),
aⁿ ≤ a^* प्रत्येक प्राकृत संख्या n के लिए, aⁿ ≤ a^* जहाँ a को a के n-गुना गुणन के रूप में परिभाषित किया गया है।
(a^*)(a^*) = a^*,
(a*)^{* = a^*}
1 + a (a^*) = a^* = 1 + (a^*)a,
ax = xb का अर्थ है (a^*)x = x(b*),
((ab)^*)a = a((ba)^*),
(a + b)^{* = a^{*(b(a^{*))^{*, और}}}}
pq = 1 = qp का अर्थ है q(a^*)p = (qap)^{*.^{^[5]}}

यदि A क्लेन बीजगणित है और n प्राकृतिक संख्या है, तब कोई समुच्चय M_n(A) पर विचार कर सकता है जिसमे A में प्रविष्टियों के साथ सभी n-बाय-n मैट्रिक्स (गणित) सम्मिलित है। मैट्रिक्स योग और गुणन की सामान्य धारणाओं का उपयोग करके, अद्वितीय को परिभाषित किया जा सकता है। इस प्रकार ^*-संचालन जिससे कि M_n(A) क्लेन बीजगणित बन जाता है।

इतिहास

क्लेन ने नियमित अभिव्यक्ति प्रस्तुत करता है और उनके कुछ बीजगणितीय नियम दिए है।^[6]^[7] चूंकि उन्होंने क्लेन बीजगणित को परिभाषित नहीं किया था, उन्होंने नियमित अभिव्यक्ति की समानता के लिए निर्णय प्रक्रिया की मांग की थी।^[8] इस प्रकार रेडको ने सिद्ध किया था कि समीकरणात्मक स्वयंसिद्धों का कोई परिमित समुच्चय नियमित भाषाओं के बीजगणित की विशेषता नहीं बता सकता है।^[9] अतः सलोमा ने इस बीजगणित का पूर्ण स्वसिद्धीकरण दिया था, चूंकि यह समस्याग्रस्त अनुमान नियमों पर निर्भर करता है।^[10] अतः स्वयंसिद्धों का पूर्ण समूह प्रदान करने की समस्या, जो नियमित अभिव्यक्तियों के मध्य सभी समीकरणों की व्युत्पत्ति की अनुमति देती है, जिसका जॉन हॉर्टन कॉनवे द्वारा नियमित बीजगणित के नाम से गहन अध्ययन किया गया था,^[11] चूँकि उनके उपचार का बड़ा भाग असीम था। सन्न 1981 में, डेक्सटर कोजेन ने नियमित भाषाओं के बीजगणित के लिए पूर्ण अनंत समीकरण निगमनात्मक प्रणाली दी थी।^[12] सन्न 1994 में, उन्होंने परिमित स्वयंसिद्ध प्रणाली की परिभाषा दी थी, जो बिना शर्त और सशर्त समानता का उपयोग करती है (a ≤ b को a + b = b के संक्षिप्त नाम के रूप में मानते हुए) और नियमित भाषाओं के बीजगणित के लिए समान रूप से पूर्ण होते है, अर्थात् दो नियमित भाव a और b ही भाषा को केवल तभी दर्शाते हैं जब a = b उपरोक्त स्वयंसिद्धों से अनुसरण करता है।^[13]

सामान्यीकरण (या अन्य संरचनाओं से संबंध)

क्लेन बीजगणित बंद सेमीरिंग्स की विशेष स्थिति होती है, जिसे अर्ध-नियमित सेमीरिंग्स या लेहमन सेमिरिंग भी कहा जाता है, जो सेमीरिंग्स हैं, जिनमें प्रत्येक तत्व में कम से कम अर्ध-व्युत्क्रम होता है जो समीकरण को संतुष्ट करता है: a* = aa* + 1 = a*a + 1. यह अर्ध-प्रतिलोम आवश्यक रूप से अद्वितीय नहीं होता है।^[14]^[15] इस प्रकार क्लेन बीजगणित में, a* फिक्सपॉइंट समीकरणों का सबसे कम समाधान होता है: X = aX + 1 और X = Xa + 1 होता है।^[15]

इस प्रकार बीजगणितीय पथ समस्याओं में बंद सेमिरिंग और क्लेन बीजगणित दिखाई देते हैं, जो सबसे छोटी पथ समस्या का सामान्यीकरण होता है।^[15]

यह भी देखें

नोट्स और संदर्भ

↑ Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. p. 246. ISBN 978-1-118-01086-0.
↑ For a survey, see: Kozen, Dexter (1990). "On Kleene algebras and closed semirings" (PDF). In Rovan, Branislav (ed.). Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990. Lecture Notes Computer Science. Vol. 452. Springer-Verlag. pp. 26–47. Zbl 0732.03047.
↑ Kozen (1990), sect.2.1, p.3
↑ Gross, Jonathan L.; Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204.
↑ Kozen (1990), sect.2.1.2, p.5
↑ S.C. Kleene (Dec 1951). तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व (PDF) (Technical report). U.S. Air Force / RAND Corporation. p. 98. RM-704. Here: sect.7.2, p.52
↑ Kleene, Stephen C. (1956). "तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व" (PDF). Automata Studies, Annals of Mathematical Studies. Princeton Univ. Press. 34. Here: sect.7.2, p.26-27
↑ Kleene (1956), p.35
↑ V.N. Redko (1964). "नियमित घटनाओं के बीजगणित के लिए संबंधों को परिभाषित करने पर" (PDF). Ukrainskii Matematicheskii Zhurnal [uk]. 16 (1): 120–126. (In Russian)
↑ Arto Salomaa (Jan 1966). "नियमित घटनाओं के बीजगणित के लिए दो पूर्ण स्वयंसिद्ध प्रणालियाँ" (PDF). Journal of the ACM. 13 (1): 158–169. doi:10.1145/321312.321326. S2CID 8445404.
↑ Conway, J.H. (1971). नियमित बीजगणित और परिमित मशीनें. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041. Chap.IV.
↑ Dexter Kozen (1981). "On induction vs. ^*-continuity" (PDF). In Dexter Kozen (ed.). प्रक्रिया। कार्यक्रमों के कार्यशाला तर्क. Lect. Notes in Comput. Sci. Vol. 131. Springer. pp. 167–176.
↑ Dexter Kozen (May 1994). "क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय" (PDF). Information and Computation. 110 (2): 366–390. doi:10.1006/inco.1994.1037. — An earlier version appeared as: Dexter Kozen (May 1990). क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय (Technical report). Cornell. p. 27. TR90-1123.
↑ Jonathan S. Golan (30 June 2003). उन पर सेमिरिंग्स और एफिन समीकरण. Springer Science & Business Media. pp. 157–159. ISBN 978-1-4020-1358-4.
↑ ^15.0 ^15.1 ^15.2 Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. pp. 232 and 248. ISBN 978-1-118-01086-0.

Kozen, Dexter. "CS786 स्प्रिंग 04, क्लीन बीजगणित का परिचय".

अग्रिम पठन

Peter Höfner (2009). Algebraic Calculi for Hybrid Systems. BoD – Books on Demand. pp. 10–13. ISBN 978-3-8391-2510-6. The introduction of this book reviews advances in the field of Kleene algebra made in the last 20 years, which are not discussed in the article above.

[PoulyKohlas2012-1] Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. p. 246. ISBN 978-1-118-01086-0.

[2] For a survey, see: Kozen, Dexter (1990). "On Kleene algebras and closed semirings" (PDF). In Rovan, Branislav (ed.). Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990. Lecture Notes Computer Science. Vol. 452. Springer-Verlag. pp. 26–47. Zbl 0732.03047.

[3] Kozen (1990), sect.2.1, p.3

[4] Gross, Jonathan L.; Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204.

[5] Kozen (1990), sect.2.1.2, p.5

[6] S.C. Kleene (Dec 1951). तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व (PDF) (Technical report). U.S. Air Force / RAND Corporation. p. 98. RM-704. Here: sect.7.2, p.52

[7] Kleene, Stephen C. (1956). "तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व" (PDF). Automata Studies, Annals of Mathematical Studies. Princeton Univ. Press. 34. Here: sect.7.2, p.26-27

[8] Kleene (1956), p.35

[9] V.N. Redko (1964). "नियमित घटनाओं के बीजगणित के लिए संबंधों को परिभाषित करने पर" (PDF). Ukrainskii Matematicheskii Zhurnal [uk]. 16 (1): 120–126. (In Russian)

[10] Arto Salomaa (Jan 1966). "नियमित घटनाओं के बीजगणित के लिए दो पूर्ण स्वयंसिद्ध प्रणालियाँ" (PDF). Journal of the ACM. 13 (1): 158–169. doi:10.1145/321312.321326. S2CID 8445404.

[11] Conway, J.H. (1971). नियमित बीजगणित और परिमित मशीनें. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041. Chap.IV.

[12] Dexter Kozen (1981). "On induction vs. ^*-continuity" (PDF). In Dexter Kozen (ed.). प्रक्रिया। कार्यक्रमों के कार्यशाला तर्क. Lect. Notes in Comput. Sci. Vol. 131. Springer. pp. 167–176.

[13] Dexter Kozen (May 1994). "क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय" (PDF). Information and Computation. 110 (2): 366–390. doi:10.1006/inco.1994.1037. — An earlier version appeared as: Dexter Kozen (May 1990). क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय (Technical report). Cornell. p. 27. TR90-1123.

[Golan2003-14] Jonathan S. Golan (30 June 2003). उन पर सेमिरिंग्स और एफिन समीकरण. Springer Science & Business Media. pp. 157–159. ISBN 978-1-4020-1358-4.

[PoulyKohlas2012b-15] 15.0 ^15.1 ^15.2 Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. pp. 232 and 248. ISBN 978-1-118-01086-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 1: / Line 1: @@
 {{about|क्लोजर ऑपरेशन के साथ क्लेन बीजगणित - नियमित अभिव्यक्तियों का सामान्यीकरण|सम्मिलित होने के साथ क्लेन बीजगणित- क्लेन के त्रिगुट तर्क का सामान्यीकरण-|क्लेन बीजगणित (यौगिकता के साथ)}}
-गणित में, क्लेन बीजगणित ({{IPAc-en|ˈ|k|l|eɪ|n|i}} {{respell|क्ले|नी}}; [[स्टीफन कोल क्लेन]] के नाम पर रखा गया) निष्क्रिय (और इस प्रकार आंशिक रूप से आदेशित) सेमीरिंग होता है जो क्लोजर ऑपरेटर के साथ संपन्न है। यह [[ नियमित अभिव्यक्ति ]]से ज्ञात संचालन को सामान्य करता है।<ref name="PoulyKohlas2012">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|page=246}}</ref>
+गणित में, क्लेन बीजगणित ({{IPAc-en|ˈ|k|l|eɪ|n|i}} {{respell|क्ले|नी}}; [[स्टीफन कोल क्लेन]] के नाम पर रखा गया) निष्क्रिय (और इस प्रकार आंशिक रूप से आदेशित) सेमीरिंग होता है जो क्लोजर ऑपरेटर के साथ संपन्न है। यह [[ नियमित अभिव्यक्ति |नियमित अभिव्यक्ति]] से ज्ञात संचालन को सामान्य करता है।<ref name="PoulyKohlas2012">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|page=246}}</ref>
 == परिभाषा ==
@@ Line 7: / Line 7: @@
 साहित्य में क्लेन बीजगणित और संबंधित संरचनाओं की विभिन्न असमान परिभाषाएं दी गई हैं।<ref>For a survey, see: {{cite book | zbl=0732.03047 | last=Kozen | first=Dexter | chapter=On Kleene algebras and closed semirings | title=Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990 | series=Lecture Notes Computer Science | volume=452 | pages=26–47 | year=1990 | author-link=Dexter Kozen | editor1-last=Rovan | editor1-first=Branislav | publisher=[[Springer-Verlag]] | chapter-url=http://ecommons.library.cornell.edu/bitstream/1813/6971/1/90-1131.pdf }}</ref> यहां हम वह परिभाषा देते है जो आजकल सबसे सामान्य लगती है।
-क्लेन बीजगणित समुच्चय (गणित) A है जो दो बाइनरी संक्रियाओं के साथ + : A × A → A और · : A × A → A और फलन है <sup>*</sup> : A → A, a + b, ab और a के रूप में लिखा जाता है<sup>*</sup> क्रमशः, जिससे कि निम्नलिखित स्वयंसिद्ध संतुष्ट हों।
+क्लेन बीजगणित समुच्चय (गणित) A है जो दो बाइनरी संक्रियाओं के साथ + : ''A'' × ''A'' → ''A'' और · : ''A'' × ''A'' → ''A'' और फलन <sup>*</sup> : ''A'' → ''A'' क्रमशः a + b, ab और a<sup>*</sup> के रूप में लिखा जाता है, जिससे कि निम्नलिखित स्वयंसिद्ध संतुष्ट है।
-* + और · की [[संबद्धता]]: ए + (बी + सी) = (ए + बी) + सी और ए (बीसी) = (एबी) सी ए में सभी ए, बी, सी के लिए।
+* + और · की [[संबद्धता]] : a + (b + c) = (a + b) + c और a (bc) = (ab) c A में सभी a, b, c के लिए।
-* की [[क्रमविनिमेयता]] +: a + b = b + a सभी a, b in A के लिए
+* + की [[क्रमविनिमेयता]] : a + b = b + a सभी a, b में A के लिए।
-* [[वितरण]]: ए (बी + सी) = (एबी) + (एसी) और (बी + सी) ए = (बीए) + (सीए) ए में सभी ए, बी, सी के लिए
+* [[वितरण]] : ए (b + c) = (ab) + (ac) और (b + c) a = (ba) + (ca) A में सभी a, b, c के लिए।
-* + और · के लिए [[पहचान तत्व]]: ए में तत्व 0 उपस्तिथ है जैसे ए में सभी के लिए: ए + 0 = 0 + ए = ए। A में अवयव 1 उपस्तिथ है जैसे A में सभी a के लिए: a1 = 1a = a।
+* + और · के लिए [[पहचान तत्व]] : A में तत्व 0 उपस्तिथ होता है जैसे A में सभी के लिए: a + 0 = 0 + a = a.
-* ए में सभी ए के लिए 0: ए0 = 0ए = 0 द्वारा अव[[शोषक तत्व]]।
+*A में अवयव 1 उपस्तिथ होता है जैसे A में सभी A के लिए : a1 = 1a = a.
-उपरोक्त स्वयंसिद्ध सेमिरिंग को परिभाषित करते हैं। हमें और आवश्यकता है:
+* a में सभी A के लिए 0: a0 = 0a = 0 द्वारा [[शोषक तत्व|अवशोषक तत्व]]।
-* + उदासीन है: ए में सभी ए के लिए ए + ए = ए।
+उपरोक्त स्वयंसिद्ध सेमिरिंग को परिभाषित करते हैं। अतः हमें और आवश्यकता होता है।
-ए पर आंशिक क्रम ≤ परिभाषित करना संभव है, ए ≤ बी समूह करके [[अगर और केवल अगर|यदि और केवल यदि]] ए + बी = बी (या समकक्ष: ए ≤ बी यदि और केवल यदि ए में एक्स उपस्तिथ है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ है a = b)। इस क्रम से हम संक्रिया के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं <sup>*</sup>:
+* + उदासीन है : A में सभी a के लिए a + a = a.
-* 1 + ए (ए<sup>*</sup>) ≤ ए<sup>*</sup> सभी के लिए ए में।
+A पर आंशिक क्रम ≤ परिभाषित करना संभव होता है, अतः a ≤ b समूह करके [[अगर और केवल अगर|और]] a + b = b (या समकक्ष: a ≤ b यदि A में x उपस्तिथ होता है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ होता है a = b)। इस क्रम से हम संक्रिया <sup>*</sup> के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं।
-* 1 + (अ<sup>*</sup>)a ≤ a<sup>*</sup> सभी के लिए ए में।
+* 1 + a (a<sup>*</sup>) ≤ a<sup>*</sup> सभी के लिए A में।
-* यदि a और x, A में ऐसे हैं कि ax ≤ x, तो a<sup>*</sup>x ≤ x
+* 1 + (a<sup>*</sup>)a ≤ a<sup>*</sup> सभी के लिए A में।
-* यदि a और x A में ऐसे हैं कि xa ≤ x, तो x(a<sup>*</sup>) ≤ x <ref>Kozen (1990), sect.2.1, p.3</ref>
+* यदि a और x, A में ऐसे हैं कि ax ≤ x, तब a<sup>*x</sup> ≤ x
-सहज रूप से, किसी को a + b को संघ के रूप में या a और b की कम से कम ऊपरी सीमा और ab को कुछ गुणन के रूप में सोचना चाहिए जो मोनोटोनिक फ़ंक्शन #Monotonicity क्रम सिद्धांत में है, इस अर्थ में कि a ≤ b का अर्थ ax ≤ bx है। स्टार ऑपरेटर के पीछे का विचार है a<sup>*</sup> = 1 + a + aa + aaa + ... [[ प्रोग्रामिंग भाषा सिद्धांत ]] के दृष्टिकोण से, कोई भी + को पसंद के रूप में व्याख्या कर सकता है, · अनुक्रमण के रूप में और <sup>*</sup> पुनरावृत्ति के रूप में।
+* यदि a और x, A में ऐसे हैं कि xa ≤ x, तब x(a<sup>*</sup>) ≤ x <ref>Kozen (1990), sect.2.1, p.3</ref>
+सामान्यतः सहज रूप से, किसी को a + b को संघ के रूप में या a और b की कम से कम ऊपरी सीमा और ab को कुछ गुणन के रूप में सोचा जाता है, जो मोनोटोनिक फ़ंक्शन क्रम सिद्धांत में होता है, इस अर्थ में कि a ≤ b का अर्थ ax ≤ bx है। इस प्रकार स्टार ऑपरेटर के पीछे का विचार यह होता है कि a<sup>*</sup> = 1 + a + aa + aaa + ... [[ प्रोग्रामिंग भाषा सिद्धांत |प्रोग्रामिंग भाषा सिद्धांत]] के दृष्टिकोण से, कोई भी + को पसंद के रूप में, · को अनुक्रमण के रूप में और <sup>*</sup> पुनरावृत्ति के रूप में व्याख्या कर सकता है।
 == उदाहरण ==
 {| class="wikitable" style="float:right"
-|+ Notational correspondence between
+|+ सांकेतिक पत्राचार के मध्य
 |-
-! [[#Definition|Kleene algebras]] and
+! [[#Definition|क्लेन बीजगणित]] और
 | + || · || <sup>*</sup> || 0 || 1
 |-
-! [[Regular expression#Formal language theory|Regular expressions]]
+! [[Regular expression#Formal language theory|नियमित अभिव्यक्ति]]
-| | | || not written  || <sup>*</sup> || ∅  || ε
+| | | || नहीं लिखा  || <sup>*</sup> || ∅  || ε
 |}
-चलो Σ परिमित [[सबसेट|उपसमूह]] (वर्णमाला) हो और A को Σ पर सभी नियमित अभिव्यक्ति # [[औपचारिक भाषा]] सिद्धांतों का समूह होने दें। यदि वे ही औपचारिक भाषा का वर्णन करते हैं तो हम दो ऐसे नियमित भावों को समान मानते हैं। तब A क्लेन बीजगणित बनाता है। वास्तव में, यह इस अर्थ में [[मुक्त वस्तु]] क्लेन बीजगणित है कि नियमित अभिव्यक्तियों के मध्य कोई भी समीकरण क्लेन बीजगणित के स्वयंसिद्धों से अनुसरण करता है और इसलिए प्रत्येक क्लेन बीजगणित में मान्य है।
+माना Σ परिमित [[सबसेट|उपसमूह]] (वर्णमाला) हो और A को Σ पर सभी नियमित अभिव्यक्ति [[औपचारिक भाषा]] सिद्धांतों का समूह होता है। यदि वह ही औपचारिक भाषा का वर्णन करते हैं तब हम दो ऐसे नियमित भावों को समान मानते हैं। तब A क्लेन बीजगणित बनाता है। सामान्यतः यह इस अर्थ में [[मुक्त वस्तु]] क्लेन बीजगणित होती है कि नियमित अभिव्यक्तियों के मध्य कोई भी समीकरण क्लेन बीजगणित के स्वयंसिद्धों से अनुसरण करता है और इसलिए प्रत्येक क्लेन बीजगणित में मान्य होता है।
-फिर से मान लीजिए Σ अक्षर है। मान लीजिए A Σ पर सभी [[नियमित भाषा]]ओं का समूह है (या Σ पर सभी [[संदर्भ-मुक्त भाषा]]ओं का समूह है; या Σ पर सभी [[पुनरावर्ती भाषा]]ओं का समूह है; या Σ पर सभी भाषाओं का समूह है)। तब [[संघ (सेट सिद्धांत)]] (+ के रूप में लिखा जाता है) और संयोजन#ए के दो तत्वों के स्ट्रिंग्स के समूह का संयोजन (लिखा हुआ ·) फिर से ए से संबंधित होता है, और इसलिए [[क्लेन स्टार]] ऑपरेशन ए के किसी भी तत्व पर लागू होता है। हम क्लेन बीजगणित ए प्राप्त करते हैं जिसमें 0 [[खाली सेट|खाली समूह]] होता है और 1 वह समूह होता है जिसमें केवल [[खाली स्ट्रिंग]] होती है।
+पुनः मान लीजिए Σ अक्षर होता है। मान लीजिए A Σ पर सभी [[नियमित भाषा]]ओं का समूह होता है (या Σ पर सभी [[संदर्भ-मुक्त भाषा|संदर्भ-मुक्त भाषाओं]] का समूह होता है, या Σ पर सभी [[पुनरावर्ती भाषा|पुनरावर्ती भाषाओं]] का समूह है या Σ पर सभी भाषाओं का समूह होता है)। तब [[संघ (सेट सिद्धांत)|संघ (समूह सिद्धांत)]] (+ के रूप में लिखा जाता है) और A के दो तत्वों का संयोजन (लिखा जाता है) फिर से A से संबंधित होता है और इसलिए [[क्लेन स्टार]] ऑपरेशन A के किसी भी तत्व पर प्रयुक्त होता है। इस प्रकार हम क्लेन बीजगणित A प्राप्त करते हैं जिसमें 0 [[खाली सेट|रिक्त समूह]] होता है और 1 वह समूह होता है जिसमें केवल [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] होती है।
-एम को पहचान तत्व ई के साथ [[मोनोइड]] होने दें और ए को एम के सभी उपसेटों का समूह होने दें। दो ऐसे उपसेट एस और टी के लिए, एस + टी को एस और टी का संघ होने दें और एसटी = {st: एस में एस समूह करें और टी में टी}। एस<sup>*</sup> को S द्वारा उत्पन्न M के सबमोनॉइड के रूप में परिभाषित किया गया है, जिसे {e} ∪ S ∪ SS ∪ SSS ∪ ... के रूप में वर्णित किया जा सकता है ... फिर A खाली बीजगणित बनाता है जिसमें 0 खाली समूह होता है और 1 { इ}। किसी भी छोटी श्रेणी के सिद्धांत के लिए समान निर्माण किया जा सकता है।
+सामान्यतः M को पहचान कर तत्व e के साथ [[मोनोइड]] होने देता है और A को M के सभी उपसमूहों का समूह होने देता है। इस प्रकार दो ऐसे उपसमूह S और T के लिए, S + T को S और T का संघ होने देता है और ST = {st: s में S समूह करना और t में T}। S<sup>*</sup> को S द्वारा उत्पन्न M के सबमोनॉइड के रूप में परिभाषित किया गया है, जिसे {e} ∪ S ∪ SS ∪ SSS ∪ ... के रूप में वर्णित किया जा सकता है ... पुनः A रिक्त बीजगणित बनाता है जिसमें 0 रिक्त समूह होता है और 1 {e} किसी भी छोटी श्रेणी के सिद्धांत के लिए समान रूप से निर्माण किया जा सकता है।
-क्षेत्र के ऊपर इकाई बीजगणित के रैखिक उपस्थान क्लेन बीजगणित बनाते हैं। रैखिक उपसमष्टियाँ V और W को देखते हुए, V + W को दो उपसमष्टियों के योग के रूप में और 0 को तुच्छ उपसमष्टि {0} के रूप में परिभाषित करें। परिभाषित करना {{math|1=''V'' · ''W'' = span {{mset|v · w | v ∈ V, w ∈ W}}}}, क्रमशः वी और डब्ल्यू से वैक्टर के उत्पाद की [[रैखिक अवधि]]। परिभाषित करना {{math|1=1 = span {I}<nowiki/>}}, बीजगणित की इकाई की अवधि। V का बंद होना V की सभी शक्तियों के [[मॉड्यूल का प्रत्यक्ष योग]] है।
+इस प्रकार क्षेत्र के ऊपर इकाई बीजगणित के रैखिक उपस्थान क्लेन बीजगणित बनाते हैं। अतः रैखिक उपसमष्टियाँ V और W को देखते हुए, V + W को दो उपसमष्टियों के योग के रूप में और 0 को तुच्छ उपसमष्टि {0} के रूप में परिभाषित करता है। परिभाषित करना {{math|1=''V'' · ''W'' = span {{mset|v · w | v ∈ V, w ∈ W}}}}, क्रमशः V और W से सदिश के उत्पाद की [[रैखिक अवधि]] को परिभाषित करना {{math|1=1 = span {I}<nowiki/>}}, बीजगणित की इकाई की अवधि V का बंद होना V की सभी शक्तियों के [[मॉड्यूल का प्रत्यक्ष योग]] होता है।
 <math display="block">V^{*} = \bigoplus_{i = 0}^{\infty} V^{i}</math>
-मान लीजिए कि M समुच्चय है और A, M पर सभी [[द्विआधारी संबंध]]ों का समुच्चय है। <sup>*</sup> [[रिफ्लेक्सिव ट्रांजिटिव क्लोजर]] होने के लिए, हम क्लेन बीजगणित प्राप्त करते हैं।
+मान लीजिए कि M समुच्चय है और A, M पर सभी [[द्विआधारी संबंध|द्विआधारी संबंधों]] का समुच्चय होता है। इस प्रकार + होने के लिए और <sup>*</sup> [[रिफ्लेक्सिव ट्रांजिटिव क्लोजर]] हम क्लेन बीजगणित प्राप्त करते हैं।
-संचालन के साथ प्रत्येक [[बूलियन बीजगणित (संरचना)]]। <math>\lor</math> और <math>\land</math> यदि हम उपयोग करते हैं तो यह क्लेन बीजगणित में बदल जाता है <math>\lor</math> + के लिए, <math>\land</math> के लिए · और समूह करें<sup>*</sup> = 1 सबके लिए a.
+संचालन के साथ प्रत्येक [[बूलियन बीजगणित (संरचना)]] <math>\lor</math> और <math>\land</math> यदि हम उपयोग करते हैं तब यह क्लेन बीजगणित में परिवर्तित हो जाता है <math>\lor</math> + के लिए, <math>\land</math> के लिए · और समूह के लिए a<sup>*</sup> = 1 समूह करता है।
-फ्लोयड-वारशाल एल्गोरिथम को लागू करने के लिए बहुत अलग क्लेन बीजगणित का उपयोग किया जा सकता है, सबसे छोटी पथ समस्या की गणना करना | [[ग्राफ सिद्धांत]] के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई, क्लेन के एल्गोरिथ्म द्वारा, नियतात्मक परिमित के प्रत्येक दो राज्यों के लिए नियमित अभिव्यक्ति की गणना automaton.
+फ़्लॉइड-वॉर्शल एल्गोरिथम को प्रयुक्त करने के लिए अधिक भिन्न क्लेन बीजगणित का उपयोग किया जा सकता है, क्लेन के एल्गोरिथ्म द्वारा [[ग्राफ सिद्धांत]] के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई की गणना, नियतात्मक परिमित ऑटोमेटन के प्रत्येक दो राज्यों के लिए नियमित अभिव्यक्ति की गणना करता है। इस प्रकार [[विस्तारित वास्तविक संख्या रेखा]] का उपयोग करते हुए, a + b को न्यूनतम a और b और ab को a और b का सामान्य योग होने के लिए लिया जाता है (+∞ और −∞ के योग को +∞ के रूप में परिभाषित किया जा रहा है)। a<sup>*</sup> को गैर-ऋणात्मक a के लिए वास्तविक संख्या शून्य और ऋणात्मक a के लिए −∞ के रूप में परिभाषित किया गया है। यह क्लेन बीजगणित है जिसमें शून्य तत्व +∞ और तत्व वास्तविक संख्या शून्य है। इस प्रकार भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है। अतः किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के मध्य सबसे छोटी पथ लंबाई का मूल्यांकन करती है।<ref>{{citation|title=Handbook of Graph Theory| series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press| year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref>
-[[विस्तारित वास्तविक संख्या रेखा]] का उपयोग करते हुए, a + b को न्यूनतम a और b और ab को a और b का सामान्य योग होने के लिए लें (+∞ और −∞ के योग को +∞ के रूप में परिभाषित किया जा रहा है)। ए<sup>*</sup> को गैर-ऋणात्मक a के लिए वास्तविक संख्या शून्य और ऋणात्मक a के लिए −∞ के रूप में परिभाषित किया गया है। यह क्लेन बीजगणित है जिसमें शून्य तत्व +∞ और तत्व वास्तविक संख्या शून्य है।
-भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है।
-किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के मध्य सबसे छोटी पथ लंबाई का मूल्यांकन करती है।<ref>{{citation|title=Handbook of Graph Theory| series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press| year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref>
 == गुण ==
-शून्य सबसे छोटा अवयव है: 0 ≤ a सभी a के लिए A में।
+≤ a सभी a के लिए A में शून्य सबसे छोटा अवयव होता है।
-योग a + b a और b की सबसे छोटी ऊपरी सीमा है: हमारे पास a ≤ a + b और b ≤ a + b है और यदि x, A का तत्व है जिसमें a ≤ x और b ≤ x है, तो a + b ≤ एक्स। इसी तरह, ए<sub>1</sub> + ... + ए<sub>''n''</sub> तत्वों की कम से कम ऊपरी सीमा है<sub>1</sub>, ..., ए<sub>''n''</sub>.
+योग a + b, a और b की सबसे छोटी ऊपरी सीमा होती है। इस प्रकार हमारे समीप a ≤ a + b और b ≤ a + b है और यदि x, A का तत्व है जिसमें a ≤ x और b ≤ x है, तब a + b ≤ x होता है। इसी प्रकार, a<sub>1</sub> + ... + a<sub>''n''</sub> तत्वों a<sub>1</sub>, ..., a<sub>''n''</sub> का सबसे कम से कम ऊपरी सीमा है।
-गुणन और योग एकदिष्ट हैं: यदि a ≤ b, तब
+गुणन और योग एकदिष्ट होता हैं। यदि a ≤ b, तब
-* ए + एक्स ≤ बी + एक्स,
+* a + x ≤ b + x,
-* कुल्हाड़ी ≤ बीएक्स, और
+* ax ≤ bx, और
-* एक्सए ≤ एक्सबी
+* xa ≤ xb
-ए में सभी एक्स के लिए।
+A में सभी x के लिए।
-स्टार ऑपरेशन के संबंध में, हमारे पास है
+स्टार ऑपरेशन के संबंध में, हमारे समीप है।
 * 0<sup>*</sup> = 1 और 1<sup>*</sup> = 1,
-* ए ≤ बी का अर्थ है ए<sup>*</sup> ≤ बी<sup>*</sup> (एकरसता),
+* a ≤ b का अर्थ है a<sup>*</sup> ≤ b<sup>*</sup> (एकरसता),
-* ए<sup>एन</sup> ≤ ए<sup>*</sup> प्रत्येक प्राकृत संख्या n के लिए, जहाँ a<sup>n</sup> को a के n-गुना गुणन के रूप में परिभाषित किया गया है,
+* a<sup>n</sup> ≤ a<sup>*</sup> प्रत्येक प्राकृत संख्या n के लिए, a<sup>n</sup> ≤ a<sup>*</sup> जहाँ a को a के n-गुना गुणन के रूप में परिभाषित किया गया है।
-* (ए<sup>*</sup>)(ए<sup>*</sup>) = ए<sup>*</सुप>,
+* (a<sup>*</sup>)(a<sup>*</sup>) = a<sup>*,
-* (ए<sup>*</सुप>)<sup>*</सुप> = ए<sup>*</सुप>,
+* (a*)<sup>* = a<sup>*
-* 1 + ए (ए<sup>*</sup>) = ए<sup>*</sup> = 1 + (ए<sup>*</sup>)ए,
+* 1 + a (a<sup>*</sup>) = a<sup>*</sup> = 1 + (a<sup>*</sup>)a,
-* कुल्हाड़ी = एक्सबी का अर्थ है (ए<sup>*</sup>)x = x(बी<sup>*</सुप>),
+* ax = xb का अर्थ है (a<sup>*</sup>)x = x(b*),
-* ((अब)<sup>*</sup>)ए = ए((बीए)<sup>*</sup>),
+* ((ab)<sup>*</sup>)a = a((ba)<sup>*</sup>),
-* (ए + बी)<sup>*</सुप> = ए<sup>*</sup>(बी(ए<sup>*</sup>))<sup>*</सुप>, और
+* (a + b)<sup>* = a<sup>*(b(a<sup>*))<sup>*, और
-* pq = 1 = qp का अर्थ है q(a<sup>*</sup>)p = (qap)<sup>*</सुप>.<ref>Kozen (1990), sect.2.1.2, p.5</ref>
+* pq = 1 = qp का अर्थ है q(a<sup>*</sup>)p = (qap)<sup>*.<sup><ref>Kozen (1990), sect.2.1.2, p.5</ref>
-यदि A क्लेन बीजगणित है और n प्राकृतिक संख्या है, तो कोई समुच्चय M पर विचार कर सकता है<sub>''n''</sub>(ए) ए में प्रविष्टियों के साथ सभी एन-बाय-एन [[मैट्रिक्स (गणित)]] से मिलकर।
+यदि A क्लेन बीजगणित है और n प्राकृतिक संख्या है, तब कोई समुच्चय M<sub>''n''</sub>(A) पर विचार कर सकता है जिसमे A में प्रविष्टियों के साथ सभी n-बाय-n [[मैट्रिक्स (गणित)]] सम्मिलित है। मैट्रिक्स योग और गुणन की सामान्य धारणाओं का उपयोग करके, अद्वितीय को परिभाषित किया जा सकता है। इस प्रकार <sup>*</sup>-संचालन जिससे कि M<sub>''n''</sub>(A) क्लेन बीजगणित बन जाता है।
-मैट्रिक्स योग और गुणन की सामान्य धारणाओं का उपयोग करके, अद्वितीय को परिभाषित किया जा सकता है <sup>*</sup>-ऑपरेशन जिससे कि एम<sub>''n''</sub>(ए) क्लेन बीजगणित बन जाता है।
 == इतिहास ==
-क्लेन ने रेगुलर एक्सप्रेशंस प्रस्तुत किए और उनके कुछ बीजगणितीय नियम दिए।<ref>{{cite techreport| author=S.C. Kleene| title=तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व|date=Dec 1951| number=RM-704| pages=98| institution=U.S. Air Force / RAND Corporation| url=http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf}} Here: sect.7.2, p.52</ref><ref>{{cite journal| author=Kleene, Stephen C.| title=तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व| journal=Automata Studies, Annals of Mathematical Studies| year=1956| volume=34| publisher=Princeton Univ. Press| url=http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf}} Here: sect.7.2, p.26-27</ref>
+क्लेन ने नियमित अभिव्यक्ति प्रस्तुत करता है और उनके कुछ बीजगणितीय नियम दिए है।<ref>{{cite techreport| author=S.C. Kleene| title=तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व|date=Dec 1951| number=RM-704| pages=98| institution=U.S. Air Force / RAND Corporation| url=http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf}} Here: sect.7.2, p.52</ref><ref>{{cite journal| author=Kleene, Stephen C.| title=तंत्रिका जाल और परिमित ऑटोमेटा में घटनाओं का प्रतिनिधित्व| journal=Automata Studies, Annals of Mathematical Studies| year=1956| volume=34| publisher=Princeton Univ. Press| url=http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf}} Here: sect.7.2, p.26-27</ref> चूंकि उन्होंने क्लेन बीजगणित को परिभाषित नहीं किया था, उन्होंने नियमित अभिव्यक्ति की समानता के लिए निर्णय प्रक्रिया की मांग की थी।<ref>Kleene (1956), p.35</ref> इस प्रकार रेडको ने सिद्ध किया था कि समीकरणात्मक स्वयंसिद्धों का कोई परिमित समुच्चय नियमित भाषाओं के बीजगणित की विशेषता नहीं बता सकता है।<ref>{{cite journal| author=V.N. Redko| url=http://umj.imath.kiev.ua/archiv/1964/01/umj_1964_01_10002_20139.pdf | title=नियमित घटनाओं के बीजगणित के लिए संबंधों को परिभाषित करने पर| journal={{ill|Ukrainskii Matematicheskii Zhurnal|uk|Український математичний журнал}} | year=1964| volume=16| number=1 | pages=120–126}} (In Russian)</ref> अतः सलोमा ने इस बीजगणित का पूर्ण स्वसिद्धीकरण दिया था, चूंकि यह समस्याग्रस्त अनुमान नियमों पर निर्भर करता है।<ref>{{cite journal| author=Arto Salomaa| title=नियमित घटनाओं के बीजगणित के लिए दो पूर्ण स्वयंसिद्ध प्रणालियाँ| journal= Journal of the ACM|date=Jan 1966| volume=13| number=1| pages=158–169| url=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/salomaa1966.pdf| doi=10.1145/321312.321326| s2cid=8445404| author-link=Arto Salomaa}}</ref> अतः स्वयंसिद्धों का पूर्ण समूह प्रदान करने की समस्या, जो नियमित अभिव्यक्तियों के मध्य सभी समीकरणों की व्युत्पत्ति की अनुमति देती है, जिसका [[जॉन हॉर्टन कॉनवे]] द्वारा नियमित बीजगणित के नाम से गहन अध्ययन किया गया था,<ref>{{cite book | first=J.H. | last=Conway | author-link=John Horton Conway | title=नियमित बीजगणित और परिमित मशीनें| publisher=Chapman and Hall | year=1971 | isbn=0-412-10620-5 | zbl=0231.94041 | location=London }}  Chap.IV.</ref> चूँकि उनके उपचार का बड़ा भाग असीम था। सन्न 1981 में, [[डेक्सटर कोजेन]] ने नियमित भाषाओं के बीजगणित के लिए पूर्ण अनंत समीकरण निगमनात्मक प्रणाली दी थी।<ref>{{cite book| author=Dexter Kozen| chapter=On induction vs. <sup>*</sup>-continuity| title=प्रक्रिया। कार्यक्रमों के कार्यशाला तर्क| year=1981| volume=131| pages=167–176| publisher=Springer| editor=Dexter Kozen| series=Lect. Notes in Comput. Sci.| chapter-url=http://www.cs.cornell.edu/~kozen/papers/indvsstarcont.pdf}}</ref> सन्न 1994 में, उन्होंने परिमित स्वयंसिद्ध प्रणाली की परिभाषा दी थी, जो बिना शर्त और सशर्त समानता का उपयोग करती है (a ≤ b को a + b = b के संक्षिप्त नाम के रूप में मानते हुए) और नियमित भाषाओं के बीजगणित के लिए समान रूप से पूर्ण होते है, अर्थात् दो नियमित भाव a और b ही भाषा को केवल तभी दर्शाते हैं जब a = b उपरोक्त स्वयंसिद्धों से अनुसरण करता है।<ref>{{cite journal| author=Dexter Kozen| title=क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय| journal=Information and Computation|date=May 1994| volume=110| number=2| pages=366–390| url=http://www.cs.cornell.edu/~kozen/papers/ka.pdf| doi=10.1006/inco.1994.1037}} &mdash; An earlier version appeared as: {{cite techreport| author=Dexter Kozen| title=क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय|date=May 1990| number=TR90-1123| pages=27| institution=Cornell| url=http://ecommons.library.cornell.edu/handle/1813/6963}}</ref>
-चूंकि उन्होंने क्लेन बीजगणित को परिभाषित नहीं किया, उन्होंने रेगुलर एक्सप्रेशंस की समानता के लिए निर्णय प्रक्रिया की मांग की।<ref>Kleene (1956), p.35</ref>
-रेडको ने सिद्ध किया कि समीकरणात्मक स्वयंसिद्धों का कोई परिमित समुच्चय नियमित भाषाओं के बीजगणित की विशेषता नहीं बता सकता।<ref>{{cite journal| author=V.N. Redko| url=http://umj.imath.kiev.ua/archiv/1964/01/umj_1964_01_10002_20139.pdf | title=नियमित घटनाओं के बीजगणित के लिए संबंधों को परिभाषित करने पर| journal={{ill|Ukrainskii Matematicheskii Zhurnal|uk|Український математичний журнал}} | year=1964| volume=16| number=1 | pages=120–126}} (In Russian)</ref>
-सलोमा ने इस बीजगणित का पूर्ण स्वसिद्धीकरण दिया, चूंकि यह समस्यामूलक अनुमान नियमों पर निर्भर करता है।<ref>{{cite journal| author=Arto Salomaa| title=नियमित घटनाओं के बीजगणित के लिए दो पूर्ण स्वयंसिद्ध प्रणालियाँ| journal= Journal of the ACM|date=Jan 1966| volume=13| number=1| pages=158–169| url=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/salomaa1966.pdf| doi=10.1145/321312.321326| s2cid=8445404| author-link=Arto Salomaa}}</ref>
-स्वयंसिद्धों का पूरा समूह प्रदान करने की समस्या, जो नियमित अभिव्यक्तियों के मध्य सभी समीकरणों की व्युत्पत्ति की अनुमति देती है, का [[जॉन हॉर्टन कॉनवे]] द्वारा नियमित बीजगणित के नाम से गहन अध्ययन किया गया था,<ref>{{cite book | first=J.H. | last=Conway | author-link=John Horton Conway | title=नियमित बीजगणित और परिमित मशीनें| publisher=Chapman and Hall | year=1971 | isbn=0-412-10620-5 | zbl=0231.94041 | location=London }}  Chap.IV.</ref> चूँकि, उनके उपचार का बड़ा हिस्सा असीम था।
-में, [[डेक्सटर कोजेन]] ने नियमित भाषाओं के बीजगणित के लिए पूर्ण अनंत समीकरण निगमनात्मक प्रणाली दी।<ref>{{cite book| author=Dexter Kozen| chapter=On induction vs. <sup>*</sup>-continuity| title=प्रक्रिया। कार्यक्रमों के कार्यशाला तर्क| year=1981| volume=131| pages=167–176| publisher=Springer| editor=Dexter Kozen| series=Lect. Notes in Comput. Sci.| chapter-url=http://www.cs.cornell.edu/~kozen/papers/indvsstarcont.pdf}}</ref>
-में, उन्होंने परिमित स्वयंसिद्ध प्रणाली की परिभाषा दी, जो बिना शर्त और सशर्त समानता का उपयोग करती है (a ≤ b को a + b = b के संक्षिप्त नाम के रूप में मानते हुए), और नियमित भाषाओं के बीजगणित के लिए समान रूप से पूर्ण है, अर्थात दो नियमित भाव a और b ही भाषा को केवल तभी दर्शाते हैं जब a = b #Definition axioms से अनुसरण करता है।<ref>{{cite journal| author=Dexter Kozen| title=क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय| journal=Information and Computation|date=May 1994| volume=110| number=2| pages=366–390| url=http://www.cs.cornell.edu/~kozen/papers/ka.pdf| doi=10.1006/inco.1994.1037}} &mdash; An earlier version appeared as: {{cite techreport| author=Dexter Kozen| title=क्लेन बीजगणित और नियमित घटनाओं के बीजगणित के लिए एक पूर्णता प्रमेय|date=May 1990| number=TR90-1123| pages=27| institution=Cornell| url=http://ecommons.library.cornell.edu/handle/1813/6963}}</ref>
 == सामान्यीकरण (या अन्य संरचनाओं से संबंध) ==
-क्लेन बीजगणित बंद सेमीरिंग्स का विशेष स्थिति है, जिसे अर्ध-नियमित सेमीरिंग्स या [[लेहमन सेमिरिंग]] भी कहा जाता है, जो सेमीरिंग्स हैं जिनमें प्रत्येक तत्व में कम से कम अर्ध-व्युत्क्रम होता है जो समीकरण को संतुष्ट करता है: a* = aa* + 1 = a*a + 1. यह अर्ध-प्रतिलोम आवश्यक रूप से अद्वितीय नहीं है।<ref name="Golan2003">{{cite book|author=Jonathan S. Golan|title=उन पर सेमिरिंग्स और एफिन समीकरण|url=https://books.google.com/books?id=jw4Hmgz5ETQC&pg=PA157|date=30 June 2003|publisher=Springer Science & Business Media|isbn=978-1-4020-1358-4|pages=157–159}}</ref><ref name="PoulyKohlas2012b"/> क्लेन बीजगणित में, a* [[ fixpoint ]] समीकरणों का सबसे कम समाधान है: X = aX + 1 और X = Xa + 1।<ref name="PoulyKohlas2012b"/>
+क्लेन बीजगणित बंद सेमीरिंग्स की विशेष स्थिति होती है, जिसे अर्ध-नियमित सेमीरिंग्स या [[लेहमन सेमिरिंग]] भी कहा जाता है, जो सेमीरिंग्स हैं, जिनमें प्रत्येक तत्व में कम से कम अर्ध-व्युत्क्रम होता है जो समीकरण को संतुष्ट करता है: a* = aa* + 1 = a*a + 1. यह अर्ध-प्रतिलोम आवश्यक रूप से अद्वितीय नहीं होता है।<ref name="Golan2003">{{cite book|author=Jonathan S. Golan|title=उन पर सेमिरिंग्स और एफिन समीकरण|url=https://books.google.com/books?id=jw4Hmgz5ETQC&pg=PA157|date=30 June 2003|publisher=Springer Science & Business Media|isbn=978-1-4020-1358-4|pages=157–159}}</ref><ref name="PoulyKohlas2012b"/> इस प्रकार क्लेन बीजगणित में, a* [[ fixpoint |फिक्सपॉइंट]] समीकरणों का सबसे कम समाधान होता है: X = aX + 1 और X = Xa + 1 होता है।<ref name="PoulyKohlas2012b"/>
-[[बीजगणितीय पथ समस्या]]ओं में बंद सेमिरिंग और क्लेन बीजगणित दिखाई देते हैं, जो सबसे छोटी पथ समस्या का सामान्यीकरण है।<ref name="PoulyKohlas2012b">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|pages=232 and 248}}</ref>
+इस प्रकार [[बीजगणितीय पथ समस्या|बीजगणितीय पथ समस्याओं]] में बंद सेमिरिंग और क्लेन बीजगणित दिखाई देते हैं, जो सबसे छोटी पथ समस्या का सामान्यीकरण होता है।<ref name="PoulyKohlas2012b">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|pages=232 and 248}}</ref>
 == यह भी देखें ==
 * [[क्रिया बीजगणित]]
@@ Line 99: / Line 85: @@
 * क्लेन स्टार
 * नियमित अभिव्यक्ति
-* [[मोटी हो जाओ]]
+* [[मोटी हो जाओ|स्टार सेमिरिंग]]
 * [[मूल्यांकन बीजगणित]]
@@ Line 109: / Line 95: @@
 == अग्रिम पठन ==
 * {{cite book|author=Peter Höfner|title=Algebraic Calculi for Hybrid Systems|url=https://books.google.com/books?id=40vn5XIMAtwC|year=2009|publisher=BoD – Books on Demand|isbn=978-3-8391-2510-6|pages=10–13}} The introduction of this book reviews advances in the field of Kleene algebra made in the last 20 years, which are not discussed in the article above.
-[[Category: बीजगणितीय संरचनाएं]] [[Category: बीजगणितीय तर्क]] [[Category: औपचारिक भाषाएँ]] [[Category: बहु-मूल्यवान तर्क]]
-[[Category: Machine Translated Page]]
+[[Category:All pages needing cleanup]]
+[[Category:Articles needing cleanup from August 2014]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Articles with invalid date parameter in template]]
+[[Category:Cleanup tagged articles with a reason field from August 2014]]
 [[Category:Created On 26/05/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Wikipedia pages needing cleanup from August 2014]]
+[[Category:औपचारिक भाषाएँ]]
+[[Category:बहु-मूल्यवान तर्क]]
+[[Category:बीजगणितीय तर्क]]
+[[Category:बीजगणितीय संरचनाएं]]

Anonymous

Search

क्लेन बीजगणित: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:03, 14 June 2023

Contents

परिभाषा

उदाहरण

गुण

इतिहास

सामान्यीकरण (या अन्य संरचनाओं से संबंध)

यह भी देखें

नोट्स और संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्लेन बीजगणित: Difference between revisions

Latest revision as of 16:03, 14 June 2023

परिभाषा

उदाहरण

गुण

इतिहास

सामान्यीकरण (या अन्य संरचनाओं से संबंध)

यह भी देखें

नोट्स और संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories