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

This article is about the Kleene algebra with a closure operation—a generalization of regular expressions. For the Kleene algebra with involution—a generalization of Kleene's ternary logic—, see Kleene algebra (with involution).

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

परिभाषा

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

एक क्लेन बीजगणित एक समुच्चय (गणित) है जो दो बाइनरी संक्रियाओं के साथ + : 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

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

गुण

शून्य सबसे छोटा अवयव है: 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)^{*</सुप>.}

यदि 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.