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

Revision as of 21:51, 5 June 2023

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

परिभाषा

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

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

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

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

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

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

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

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

उदाहरण

Notational correspondence between
Kleene algebras and	+	·	^*	0	1
Regular expressions	\|	not written	^*	∅	ε

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

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

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

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

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

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

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

फ्लोयड-वारशाल एल्गोरिथम को लागू करने के लिए एक बहुत अलग क्लेन बीजगणित का उपयोग किया जा सकता है, सबसे छोटी पथ समस्या की गणना करना | ग्राफ सिद्धांत के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई, क्लेन के एल्गोरिथ्म द्वारा, नियतात्मक परिमित के प्रत्येक दो राज्यों के लिए एक नियमित अभिव्यक्ति की गणना automaton. विस्तारित वास्तविक संख्या रेखा का उपयोग करते हुए, a + b को न्यूनतम a और b और ab को a और b का सामान्य योग होने के लिए लें (+∞ और −∞ के योग को +∞ के रूप में परिभाषित किया जा रहा है)। ए^* को गैर-ऋणात्मक 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 ≤ एक्स। इसी तरह, ए₁ + ... + ए_n तत्वों की कम से कम ऊपरी सीमा है₁, ..., ए_n.

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

ए + एक्स ≤ बी + एक्स,
कुल्हाड़ी ≤ बीएक्स, और
एक्सए ≤ एक्सबी

ए में सभी एक्स के लिए।

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

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

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

इतिहास

क्लेन ने रेगुलर एक्सप्रेशंस पेश किए और उनके कुछ बीजगणितीय नियम दिए।^[6]^[7]

चूंकि उन्होंने क्लेन बीजगणित को परिभाषित नहीं किया, उन्होंने रेगुलर एक्सप्रेशंस की समानता के लिए एक निर्णय प्रक्रिया की मांग की।^[8]

रेडको ने सिद्ध किया कि समीकरणात्मक स्वयंसिद्धों का कोई परिमित समुच्चय नियमित भाषाओं के बीजगणित की विशेषता नहीं बता सकता।^[9]

सलोमा ने इस बीजगणित का पूर्ण स्वसिद्धीकरण दिया, चूंकि यह समस्यामूलक अनुमान नियमों पर निर्भर करता है।^[10]

स्वयंसिद्धों का एक पूरा सेट प्रदान करने की समस्या, जो नियमित अभिव्यक्तियों के बीच सभी समीकरणों की व्युत्पत्ति की अनुमति देती है, का जॉन हॉर्टन कॉनवे द्वारा नियमित बीजगणित के नाम से गहन अध्ययन किया गया था,^[11] हालाँकि, उनके उपचार का बड़ा हिस्सा असीम था। 1981 में, डेक्सटर कोजेन ने नियमित भाषाओं के बीजगणित के लिए एक पूर्ण अनंत समीकरण निगमनात्मक प्रणाली दी।^[12]

1994 में, उन्होंने परिमित स्वयंसिद्ध प्रणाली की परिभाषा दी, जो बिना शर्त और सशर्त समानता का उपयोग करती है (a ≤ b को a + b = b के संक्षिप्त नाम के रूप में मानते हुए), और नियमित भाषाओं के बीजगणित के लिए समान रूप से पूर्ण है, अर्थात दो नियमित भाव a और b एक ही भाषा को केवल तभी दर्शाते हैं जब a = b #Definition axioms से अनुसरण करता है।^[13]

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

क्लेन बीजगणित बंद सेमीरिंग्स का एक विशेष स्थिति है, जिसे अर्ध-नियमित सेमीरिंग्स या लेहमन सेमिरिंग भी कहा जाता है, जो सेमीरिंग्स हैं जिनमें प्रत्येक तत्व में कम से कम एक अर्ध-व्युत्क्रम होता है जो समीकरण को संतुष्ट करता है: a* = aa* + 1 = a*a + 1. यह अर्ध-प्रतिलोम आवश्यक रूप से अद्वितीय नहीं है।^[14]^[15]क्लेन बीजगणित में, a* fixpoint समीकरणों का सबसे कम समाधान है: 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 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 और एक फलन है <sup>*</sup> : A → A, a + b, ab और a के रूप में लिखा जाता है<sup>*</sup> क्रमशः, ताकि निम्नलिखित स्वयंसिद्ध संतुष्ट हों।
+एक क्लेन बीजगणित एक समुच्चय (गणित) है जो दो बाइनरी संक्रियाओं के साथ + : A × A → A और · : A × A → A और एक फलन है <sup>*</sup> : A → A, a + b, ab और a के रूप में लिखा जाता है<sup>*</sup> क्रमशः, जिससे कि निम्नलिखित स्वयंसिद्ध संतुष्ट हों।
 * + और · की [[संबद्धता]]: ए + (बी + सी) = (ए + बी) + सी और ए (बीसी) = (एबी) सी ए में सभी ए, बी, सी के लिए।
 * की [[क्रमविनिमेयता]] +: a + b = b + a सभी a, b in A के लिए
 * [[वितरण]]: ए (बी + सी) = (एबी) + (एसी) और (बी + सी) ए = (बीए) + (सीए) ए में सभी ए, बी, सी के लिए
-* + और · के लिए [[पहचान तत्व]]: ए में एक तत्व 0 मौजूद है जैसे ए में सभी के लिए: ए + 0 = 0 + ए = ए। A में एक अवयव 1 मौजूद है जैसे A में सभी a के लिए: a1 = 1a = a।
+* + और · के लिए [[पहचान तत्व]]: ए में एक तत्व 0 उपस्तिथ है जैसे ए में सभी के लिए: ए + 0 = 0 + ए = ए। A में एक अवयव 1 उपस्तिथ है जैसे A में सभी a के लिए: a1 = 1a = a।
 * ए में सभी ए के लिए 0: ए0 = 0ए = 0 द्वारा अव[[शोषक तत्व]]।
 उपरोक्त स्वयंसिद्ध एक सेमिरिंग को परिभाषित करते हैं। हमें और आवश्यकता है:
 * + उदासीन है: ए में सभी ए के लिए ए + ए = ए।
-ए पर आंशिक क्रम ≤ परिभाषित करना संभव है, ए ≤ बी सेट करके [[अगर और केवल अगर]] ए + बी = बी (या समकक्ष: ए ≤ बी अगर और केवल अगर ए में एक एक्स मौजूद है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ है a = b)। इस क्रम से हम संक्रिया के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं <sup>*</sup>:
+ए पर आंशिक क्रम ≤ परिभाषित करना संभव है, ए ≤ बी सेट करके [[अगर और केवल अगर|यदि और केवल यदि]] ए + बी = बी (या समकक्ष: ए ≤ बी यदि और केवल यदि ए में एक एक्स उपस्तिथ है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ है a = b)। इस क्रम से हम संक्रिया के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं <sup>*</sup>:
 * 1 + ए (ए<sup>*</sup>) ≤ ए<sup>*</sup> सभी के लिए ए में।
 * 1 + (अ<sup>*</sup>)a ≤ a<sup>*</sup> सभी के लिए ए में।
@@ Line 50: / Line 50: @@
 एक भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है।
 किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के बीच सबसे छोटी पथ लंबाई का मूल्यांकन करती है।<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>
 == गुण ==
@@ Line 76: / Line 74: @@
 * pq = 1 = qp का अर्थ है q(a<sup>*</sup>)p = (qap)<sup>*</सुप>.<ref>Kozen (1990), sect.2.1.2, p.5</ref>
 यदि A एक क्लेन बीजगणित है और n एक प्राकृतिक संख्या है, तो कोई समुच्चय M पर विचार कर सकता है<sub>''n''</sub>(ए) ए में प्रविष्टियों के साथ सभी एन-बाय-एन [[मैट्रिक्स (गणित)]] से मिलकर।
-मैट्रिक्स योग और गुणन की सामान्य धारणाओं का उपयोग करके, एक अद्वितीय को परिभाषित किया जा सकता है <sup>*</sup>-ऑपरेशन ताकि एम<sub>''n''</sub>(ए) एक क्लेन बीजगणित बन जाता है।
+मैट्रिक्स योग और गुणन की सामान्य धारणाओं का उपयोग करके, एक अद्वितीय को परिभाषित किया जा सकता है <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>Kleene (1956), p.35</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 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>
 == यह भी देखें ==
 * [[क्रिया बीजगणित]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:51, 5 June 2023

Contents

परिभाषा

उदाहरण

गुण

इतिहास

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

यह भी देखें

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

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:51, 5 June 2023

परिभाषा

उदाहरण

गुण

इतिहास

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

यह भी देखें

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

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories