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

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

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

परिभाषा

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

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

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

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

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

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

• 1 + ए (ए^*) ≤ ए^* सभी के लिए ए में।
• 1 + (ए^*)ए ≤ ए^* सभी के लिए ए में।
• यदि ए और एक्स, ए में ऐसे हैं कि एएक्स ≤ एक्स, तब ए^*एक्स ≤ एक्स
• यदि ए और एक्सए में ऐसे हैं कि एक्सए ≤ एक्स, तब एक्स(ए^*) ≤ एक्स

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

उदाहरण

Notational correspondence between

Kleene algebras and	+	·	*	0	1
Regular expressions	|	not written	*	∅	ε

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

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

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

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

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

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

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

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

गुण

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

योग 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)^{*</सुप>.}

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

इतिहास

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

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

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

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

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

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

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

क्लेन बीजगणित बंद सेमीरिंग्स का विशेष स्थिति है, जिसे अर्ध-नियमित सेमीरिंग्स या लेहमन सेमिरिंग भी कहा जाता है, जो सेमीरिंग्स हैं जिनमें प्रत्येक तत्व में कम से कम अर्ध-व्युत्क्रम होता है जो समीकरण को संतुष्ट करता है: a* = aa* + 1 = a*a + 1. यह अर्ध-प्रतिलोम आवश्यक रूप से अद्वितीय नहीं है। क्लेन बीजगणित में, a* fixpoint समीकरणों का सबसे कम समाधान है: 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.