अर्धसमूह क्रिया

बीजगणित और सैद्धांतिक कंप्यूटर विज्ञान में, सेट (सम्मुच्य) पर एक सेमीग्रुप की एक्शन (क्रिया) या एक्ट (कृत्य) नियम है जो सेमीग्रुप के प्रत्येक तत्व को सेट के एक परिवर्तन से जोड़ता है, इस तरह से कि सेमीग्रुप के दो तत्वों का उत्पाद (सेमिग्रुप ऑपरेशन का उपयोग करके) दो संबंधित परिवर्तनों के सम्मिश्रण से जुड़ा हुआ है। शब्दावली इस विचार को व्यक्त करती है कि सेमीग्रुप के तत्व सेट के रूपांतरण के रूप में कार्य कर रहे हैं। बीजगणितीय परिप्रेक्ष्य से, एक अर्धसमूह क्रिया समूह सिद्धांत में समूह क्रिया की धारणा का सामान्यीकरण है। कंप्यूटर विज्ञान के दृष्टिकोण से, अर्ध समूह क्रियाएं ऑटोमेटा से निकटता से संबंधित हैं: इनपुट के जवाब में सेट मॉडल स्वचालित की स्थिति और उस स्थिति के क्रिया मॉडल परिवर्तन।

एक महत्वपूर्ण विशेष मामला एक मोनोइड क्रिया या एक्ट है, जिसमें सेमिग्रुप एक मोनोइड है और मोनोइड का तत्समक अवयव सेट के तत्समक रूपांतरण के रूप में कार्य करता है। एक श्रेणी-सैद्धांतिक दृष्टिकोण से, एक मोनॉयड एक वस्तु के साथ एक श्रेणी है, और एक एक्ट उस श्रेणी से सेट की श्रेणी के लिए एक फ़ंक्टर है। यह तुरंत सेट की श्रेणी के अलावा अन्य श्रेणियों में वस्तुओं पर मोनॉइड क्रियाओं का सामान्यीकरण प्रदान करता है।

एक अन्य महत्वपूर्ण विशेष मामला एक परिवर्तन अर्धसमूह है। यह एक समुच्चय के परिवर्तनों का एक अर्धसमूह है, और इसलिए उस समुच्चय पर एक अनुश्रवणात्मक क्रिया होती है। यह अवधारणा केली के प्रमेय के अनुरूप एक अर्धसमूह की अधिक सामान्य धारणा से जुड़ी हुई है।

(शब्दावली पर एक नोट: इस क्षेत्र में प्रयुक्त शब्दावली कभी-कभी एक लेखक से दूसरे लेखक में भिन्न होती है। विवरण के लिए लेख देखें।)

औपचारिक परिभाषाएँ

मान लीजिए कि S एक अर्धसमूह है। तब S का एक (बायाँ) सेमीग्रुप एक्शन (या एक्ट) एक सेट X है जिसमें एक ऑपरेशन • : S × X → X है जो सेमीग्रुप ऑपरेशन के साथ संगत है ∗ निम्नानुसार है:

सभी s, t in S और x in X, s • (t • x) = (s ∗ t) • x के लिए।

यह एक (बाएं) समूह क्रिया के सेमीग्रुप सिद्धांत में एनालॉग है और X पर कार्यों के सेट में एक सेमीग्रुप समरूपता के बराबर है। सही सेमीग्रुप क्रियाओं को एक ऑपरेशन का उपयोग करके इसी तरह परिभाषित किया गया है • : X × S → X समाधानप्रद (x • a) • b = x • (a ∗ b)।

यदि M एक मोनॉइड है, तो M का एक (बायाँ) मोनोइड एक्शन (या एक्ट) अतिरिक्त संपत्ति के साथ M का एक (बायाँ) सेमीग्रुप क्रिया है

X में सभी x के लिए: X: e • x = x

जहाँ e, M का तत्समक अवयव है। यह तदनुरूप एक मोनोइड समरूपता देता है। सही मोनोइड क्रियाओं को एक समान तरीके से परिभाषित किया गया है। एक सेट पर क्रिया के साथ एक मोनॉयड M को एक ऑपरेटर मोनोइड भी कहा जाता है।

X पर S की एक सेमीग्रुप क्रिया को एक तत्समक को सेमीग्रुप से जोड़कर और X पर तत्समक समरूपता के रूप में कार्य करने की आवश्यकता के द्वारा एक मोनोइड एक्ट में बनाया जा सकता है।

शब्दावली और अंकन

यदि S एक सेमीग्रुप या मोनॉयड है, तो एक सेट X जिस पर S ऊपर के रूप में कार्य करता है (बाएं, कहते हैं) को (बाएं) 'S-एक्ट', 'S-सेट', 'S-एक्शन', 'S-ऑपरेंड' या S के ऊपर एक्ट के रूप में भी जाना जाता है। कुछ लेखक सेमीग्रुप और मोनॉइड क्रियाओं के बीच अंतर नहीं करते हैं, तत्समक स्वयंसिद्ध (e • x = x) के संबंध में जब कोई तत्समक तत्व नहीं होता है, या तत्समक के साथ S- एक्ट के लिए एकात्मक S-एक्ट शब्द का उपयोग करते हैं।^[1]

एक एक्ट की परिभाषित संपत्ति सेमिग्रुप ऑपरेशन की सहयोगीता के समान है और इसका मतलब है कि सभी कोष्ठकों को छोड़ा जा सकता है। यह सामान्य अभ्यास है, विशेष रूप से कंप्यूटर विज्ञान में, परिचालनों को छोड़ने के लिए भी ताकि सेमीग्रुप ऑपरेशन और क्रिया दोनों को संसर्ग द्वारा दर्शाया जा सके। इस प्रकार S से स्ट्रिंग X पर कार्य करते हैं, जैसा कि अभिव्यक्ति stx में s, t में S और x में X के लिए है।

बायीं क्रियाओं के बदले दाएं कार्यों के साथ काम करना भी काफी सामान्य है।^[2] हालांकि, प्रत्येक सही एस-अधिनियम को विपरीत अर्धसमूह पर एक बाएं अधिनियम के रूप में व्याख्या किया जा सकता है, जिसमें एस के समान तत्व हैं, लेकिन जहां गुणन को कारकों को उलट कर परिभाषित किया गया है,s • t = t • s, इसलिए दो धारणाएं अनिवार्य रूप से समकक्ष हैं। यहाँ हम मुख्य रूप से वामपंथी कृत्यों के दृष्टिकोण को अपनाते हैं।

एक्ट और रूपांतरण

यह अक्सर सुविधाजनक होता है (उदाहरण के लिए यदि विचाराधीन एक से अधिक कार्य हैं) फलन को निरूपित करने के लिए $T$ जैसे अक्षर का उपयोग करना

T\colon S\times X\to X

को परिभाषित करना $S$ -एक्ट और इसलिए लिखें $T(s,x)$ की जगह $s\cdot x$ . फिर किसी के लिए $s$ में $S$ द्वारा निरूपित करते हैं

T_{s}\colon X\to X

का परिवर्तन $X$ द्वारा परिभाषित

T_{s}(x)=T(s,x).

एक की परिभाषित संपत्ति द्वारा $S$ -एक्ट , $T$ संतुष्ट

T_{s*t}=T_{s}\circ T_{t}.

इसके अलावा, एक समारोह पर विचार करें $s\mapsto T_{s}$ . यह समान है $\operatorname {curry} (T):S\to (X\to X)$ (कर्र्यींग देखें)। क्योंकि $\operatorname {curry}$ एक आक्षेप है, सेमीग्रुप क्रियाओं को कार्यों के रूप में परिभाषित किया जा सकता है $S\to (X\to X)$ जो संतुष्ट करता है

\operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).

अर्थात्, $T$ , $X$ पर $S$ की एक अर्धसमूह क्रिया है यदि और केवल यदि $\operatorname {curry} (T)$ , $S$ से $X$ के पूर्ण रूपांतरण मोनोइड के लिए एक अर्धसमूह समरूपता है।

S-समरूपता

मान लीजिए कि X और X' S-एक्ट हैं। तब X से X' तक का S-समरूपता एक मानचित्र होता है

F\colon X\to X'

ऐसा है कि

F(sx)=sF(x)

सभी के लिए

s\in S

और

x\in X

.

ऐसे सभी S-समरूपताओं के समुच्चय को सामान्यतः इस प्रकार लिखा जाता है $\mathrm {Hom} _{S}(X,X')$ .

एम-एक्ट के एम-होमोमोर्फिज्म, एम मोनोइड के लिए, ठीक उसी तरह परिभाषित किए गए हैं।

S-एक्ट और M-एक्ट

एक निश्चित सेमिग्रुप एस के लिए, बाएं S-एक्ट एक श्रेणी की वस्तुएं हैं, जो S-एक्ट को निरूपित करती हैं, जिनके आकारिकी S-समरूपता हैं। सही S-एक्ट की संगत श्रेणी को कभी-कभी अधिनियम-एस द्वारा दर्शाया जाता है। (यह एक रिंग के ऊपर बाएँ और दाएँ मॉड्यूल के R-मॉड और मॉड-R की श्रेणियों के अनुरूप है।)

मोनोइड एम के लिए, M-एक्ट और एक्ट-M श्रेणियों को उसी तरह परिभाषित किया गया है।

उदाहरण

किसी भी अर्धसमूह $(S,*)$ की $S$ पर क्रिया होती है, जहाँ $\cdot =*$ है। क्रिया गुण $*$ की साहचर्यता के कारण धारण करती है।
अधिक आम तौर पर, किसी भी अर्धसमूह समाकारिता $F\colon (S,*)\rightarrow (T,\oplus )$ के लिए, सेमीग्रुप $(S,*)$ में $T$ पर एक क्रिया होती है जो $s\cdot t=F(s)\oplus t$ द्वारा दी जाती है।
किसी भी सेट $X$ के लिए, $X^{*}$ को $X$ के तत्वों के अनुक्रमों का सेट होने दें। सेमीग्रुप $(\mathbb {N} ,\times )$ में $X^{*}$ पर $n\cdot s=s^{n}$ (जहाँ $s^{n}$ $s$ दोहराए गए $n$ बार को दर्शाता है) पर एक क्रिया होती है।
सेमीग्रुप $(\mathbb {N} ,\times )$ , में एक सही क्रिया $(\mathbb {N} ,\cdot )$ है, जो $x\cdot y=x^{y}$ द्वारा दी गई है।

रूपांतरण अर्धसमूह

रूपांतरण सेमीग्रुप और सेमीग्रुप क्रियाओं के बीच एक पत्राचार नीचे वर्णित है। यदि हम इसे विश्वसनीय अर्धसमूह क्रियाओं तक सीमित रखते हैं, तो इसमें अच्छे गुण होते हैं।

किसी भी रूपांतरण अर्धसमूह को निम्न निर्माण द्वारा एक अर्धसमूह क्रिया में बदला जा सकता है। $X$ के किसी भी ट्रांसफॉर्मेशन सेमिग्रुप $S$ के लिए, $X$ पर $S$ के सेमीग्रुप एक्शन $T$ को $T(s,x)=s(x)$ के लिए $s\in S,x\in X$ के रूप में परिभाषित करें। यह क्रिया वफ़ादार है, जो कि $curry(T)$ के अन्तःक्षेपण के बराबर है।

इसके विपरीत, $X$ पर $S$ की किसी भी सेमीग्रुप क्रिया $T$ के लिए, एक रूपांतरण सेमीग्रुप $S'=\{T_{s}\mid s\in S\}$ परिभाषित करें। इस निर्माण में, हम समुच्चय $S$ को "भूल" जाते हैं। $S'$ $curry(T)$ की छवि के बराबर है। संक्षिप्तता के लिए हम $curry(T)$ को $f$ के रूप में निरूपित करते हैं। यदि $f$ अंतःक्षेपी है, तो यह $S$ से $S'$ तक एक अर्धसमूह समरूपता है। दूसरे शब्दों में, यदि $T$ विश्वासयोग्य है, तो हम कोई महत्वपूर्ण बात नहीं भूलते। इस दावे को निम्नलिखित अवलोकन द्वारा सटीक बनाया गया है: यदि हम $S'$ को $X$ पर $S'$ की एक अर्धसमूह क्रिया $T'$ में बदल देते हैं, तो $T'(f(s),x)=T(s,x)$ सभी के लिए $s\in S,x\in X$ । $T$ और $T'$ $f$ के माध्यम से "आइसोमोर्फिक" हैं, यानी, हमने अनिवार्य रूप से $T$ को पुनर्प्राप्त किया है। इस प्रकार कुछ लेखक^[3] विश्वासयोग्य अर्धसमूह क्रियाएं और रूपांतरण सेमीग्रुप के बीच कोई अंतर नहीं देखते हैं।

कंप्यूटर विज्ञान के लिए अनुप्रयोग

अर्ध-स्वचालित

ऑटोमेटा सिद्धांत में परिमित राज्य मशीनों के संरचना सिद्धांत के लिए परिवर्तन सेमिग्रुप आवश्यक महत्व के हैं। विशेष रूप से, एक सेमीऑटोमेटन एक ट्रिपल (Σ, एक्स, टी) है, जहां Σ एक गैर-खाली सेट है जिसे इनपुट वर्णमाला कहा जाता है, एक्स एक गैर-खाली सेट है जिसे राज्यों का सेट कहा जाता है और टी एक फलन है

T\colon \Sigma \times X\to X

संक्रमण समारोह कहा जाता है। सेमियाटोमेटा प्रारंभिक अवस्था और स्वीकृत राज्यों के सेट की अनदेखी करके नियतात्मक परिमित ऑटोमेटन से उत्पन्न होता है।

एक सेमीऑटोमेटन को देखते हुए, टी_a: X → X, ∈ Σ के लिए, T द्वारा परिभाषित X के परिवर्तन को निरूपित करता है_a(एक्स) = टी (ए, एक्स)। तब {T द्वारा उत्पन्न X के परिवर्तनों का अर्धसमूह_a : a ∈ Σ} को (Σ,X,T) का अभिलाक्षणिक अर्धसमूह या संक्रमण तंत्र कहा जाता है। यह सेमीग्रुप एक मोनोइड है, इसलिए इस मोनोइड को विशेषता या संक्रमण मोनोइड कहा जाता है। इसे कभी-कभी Σ के रूप में भी देखा जाता है^∗- X पर कार्य करें, जहां Σ^∗ वर्णमाला Σ द्वारा उत्पन्न स्ट्रिंग्स का मुक्त मोनोइड है,^{[note 1]} और स्ट्रिंग्स की एक्ट संपत्ति के माध्यम से Σ की एक्ट का विस्तार करती है

T_{vw}=T_{w}\circ T_{v}.

क्रोहन-रोड्स सिद्धांत

क्रोहन-रोड्स सिद्धांत, जिसे कभी-कभी बीजगणितीय ऑटोमेटा सिद्धांत भी कहा जाता है, सरल घटकों को कैस्केडिंग करके परिमित परिवर्तन अर्धसमूहों के लिए शक्तिशाली अपघटन परिणाम देता है।

संदर्भ

↑ Kilp, Knauer and Mikhalev, 2000, pages 43–44.
↑ Kilp, Knauer and Mikhalev, 2000.
↑ Arbib, Michael A., ed. (1968). Algebraic Theory of Machines, Languages, and Semigroups. New York and London: Academic Press. p. 83.

A. H. Clifford and G. B. Preston (1961), The Algebraic Theory of Semigroups, volume 1. American Mathematical Society, ISBN 978-0-8218-0272-4.
A. H. Clifford and G. B. Preston (1967), The Algebraic Theory of Semigroups, volume 2. American Mathematical Society, ISBN 978-0-8218-0272-4.
Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.
Rudolf Lidl and Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8

[4] The monoid operation is concatenation; the identity element is the empty string.

[1] Kilp, Knauer and Mikhalev, 2000, pages 43–44.

[2] Kilp, Knauer and Mikhalev, 2000.

[3] Arbib, Michael A., ed. (1968). Algebraic Theory of Machines, Languages, and Semigroups. New York and London: Academic Press. p. 83.

[1]

[2]

[3]

[note 1]

Anonymous

Search

अर्धसमूह क्रिया

Namespaces

More

Page actions

Contents