क्लेन बीजगणित

This article is about क्लोजर ऑपरेशन के साथ क्लेन बीजगणित - नियमित अभिव्यक्तियों का सामान्यीकरण. For सम्मिलित होने के साथ क्लेन बीजगणित- क्लेन के त्रिगुट तर्क का सामान्यीकरण-, see क्लेन बीजगणित (यौगिकता के साथ).

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

परिभाषा

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

क्लेन बीजगणित समुच्चय (गणित) 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

सामान्यतः सहज रूप से, किसी को 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 · W = span {v · w | v ∈ V, w ∈ 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 के लिए −∞ के रूप में परिभाषित किया गया है। यह क्लेन बीजगणित है जिसमें शून्य तत्व +∞ और तत्व वास्तविक संख्या शून्य है। इस प्रकार भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है। अतः किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के मध्य सबसे छोटी पथ लंबाई का मूल्यांकन करती है।

गुण

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)^*.

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

इतिहास

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

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

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

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

यह भी देखें

• क्रिया बीजगणित
• बीजगणितीय संरचना
• क्लेन स्टार
• नियमित अभिव्यक्ति
• स्टार सेमिरिंग
• मूल्यांकन बीजगणित

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

• 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.