शिफ्ट स्पेस

प्रतीकात्मक गतिशीलता और गणित की संबंधित शाखाओं में, शिफ्ट स्पेस या सबशिफ्ट अनंत स्ट्रिंग (कंप्यूटर विज्ञान) का एक सेट है जो एक अलग प्रणाली के विकास का प्रतिनिधित्व करता है। वास्तव में, शिफ्ट स्पेस और प्रतीकात्मक गतिशीलता को अक्सर पर्यायवाची माना जाता है। सबसे व्यापक रूप से अध्ययन किए गए शिफ्ट स्थान परिमित प्रकार और सोफ़िक बदलाव के उपशिफ्ट हैं।

1. शास्त्रीय ढांचे में शिफ्ट स्पेस कोई उपसमुच्चय है $\Lambda$ का $A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}$, कहाँ $A$ एक परिमित समुच्चय है, जो टाइकोनोव टोपोलॉजी के लिए बंद है और अनुवादों द्वारा अपरिवर्तनीय है। अधिक आम तौर पर कोई शिफ्ट स्पेस को बंद और अनुवाद-अपरिवर्तनीय उपसमुच्चय के रूप में परिभाषित कर सकता है $A^{\mathbb {G} }$, कहाँ $A$ क्या कोई गैर-रिक्त सेट है और $\mathbb {G}$ कोई मोनोइड है.

परिभाषा

होने देना $\mathbb {G}$ एक मोनॉइड बनें, और दिया गया $g,h\in \mathbb {G}$, के संचालन को निरूपित करें $g$ साथ $h$ उत्पाद द्वारा $gh$. होने देना $\mathbf {1} _{\mathbb {G} }$ की पहचान निरूपित करें $\mathbb {G}$. एक गैर-रिक्त सेट पर विचार करें $A$ (एक वर्णमाला) असतत टोपोलॉजी के साथ, और परिभाषित करें $A^{\mathbb {G} }$ सभी पैटर्न के सेट के रूप में $A$ द्वारा अनुक्रमित $\mathbb {G}$. के लिए $\mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }$ और एक उपसमुच्चय $N\subset \mathbb {G}$, हम के प्रतिबंध को निरूपित करते हैं $\mathbf {x}$ के सूचकांकों को $N$ जैसा $\mathbf {x} _{N}:=(x_{i})_{i\in N}$.

पर $A^{\mathbb {G} }$, हम विलक्षण टोपोलॉजी पर विचार करते हैं, जो बनाता है $A^{\mathbb {G} }$ एक हॉसडॉर्फ और पूरी तरह से अलग किया गया टोपोलॉजिकल स्पेस। के मामले में $A$ परिमित होने के कारण, यह उसका अनुसरण करता है $A^{\mathbb {G} }$ सघन है. हालांकि, यदि $A$ तो फिर, यह परिमित नहीं है $A^{\mathbb {G} }$ स्थानीय स्तर पर भी सघन नहीं है.

यह टोपोलॉजी मेट्रिज़ेबल होगी यदि और केवल यदि $\mathbb {G}$ गणनीय है, और, किसी भी स्थिति में, इस टोपोलॉजी के आधार में खुले/बंद सेट (सिलेंडर कहा जाता है) का एक संग्रह होता है, जिसे निम्नानुसार परिभाषित किया गया है: सूचकांकों का एक सीमित सेट दिया गया है $D\subset \mathbb {G}$, और प्रत्येक के लिए $i\in D$, होने देना $a_{i}\in A$. सिलेंडर ने दिया $D$ और $(a_{i})_{i\in D}\in A^{|D|}$ सेट है ${\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.$ कब $D=\{g\}$, हम प्रतीक को ठीक करने वाले सिलेंडर को निरूपित करते हैं $b$ द्वारा अनुक्रमित प्रविष्टि पर $g$ बस के रूप में $[b]_{g}$.

दूसरे शब्दों में, एक सिलेंडर ${\big [}(a_{i})_{i\in D}{\big ]}_{D}$ के सभी अनंत पैटर्न के सभी सेट का सेट है $A^{\mathbb {G} }$ जिसमें परिमित पैटर्न शामिल है $(a_{i})_{i\in D}\in A^{|D|}$.

दिया गया $g\in \mathbb {G}$, g-शिफ्ट मैप पर $A^{\mathbb {G} }$ द्वारा निरूपित किया जाता है $\sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }$ और के रूप में परिभाषित किया गया है

$\sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }$.

वर्णमाला के ऊपर स्थान बदलें $A$ एक सेट है $\Lambda \subset A^{\mathbb {G} }$ जो कि टोपोलॉजी के अंतर्गत बंद है $A^{\mathbb {G} }$ और अनुवाद के अंतर्गत अपरिवर्तनीय, अर्थात्, $\sigma ^{g}(\Lambda )\subset \Lambda$ सभी के लिए $g\in \mathbb {G}$. हम शिफ्ट स्पेस में विचार करते हैं $\Lambda$ से प्रेरित टोपोलॉजी $A^{\mathbb {G} }$, जिसमें बेसिक ओपन के रूप में सिलिंडर सेट होते हैं ${\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda$.

प्रत्येक के लिए $k\in \mathbb {N} ^{*}$, परिभाषित करना ${\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}$, और ${\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}$. शिफ्ट स्पेस को परिभाषित करने का एक समकक्ष तरीका निषिद्ध पैटर्न का एक सेट लेना है $F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}$ और शिफ्ट स्पेस को सेट के रूप में परिभाषित करें $X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.$ सहज रूप से, एक स्थान परिवर्तन $X_{F}$ सभी अनंत पैटर्न का सेट है जिसमें कोई भी निषिद्ध परिमित पैटर्न शामिल नहीं है $F$.

शिफ्ट स्पेस की भाषा

शिफ्ट की जगह दी गई $\Lambda \subset A^{\mathbb {G} }$ और सूचकांकों का एक सीमित सेट $N\subset \mathbb {G}$, होने देना $W_{\emptyset }(\Lambda ):=\{\epsilon \}$, कहाँ $\epsilon$ खाली शब्द के लिए खड़ा है, और के लिए $N\neq \emptyset$ होने देना

$W_{N}(\Lambda )\subset A^{N}$ के सभी परिमित विन्यासों का समुच्चय हो $A^{N}$ जो कुछ अनुक्रम में दिखाई देते हैं $\Lambda$, अर्थात।, 

$W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.$ ध्यान दें, तब से $\Lambda$ एक शिफ्ट स्पेस है, यदि $M\subset \mathbb {G}$ का अनुवाद है $N\subset \mathbb {G}$, अर्थात।, $M=gN$ कुछ के लिए $g\in \mathbb {G}$, तब $(w_{j})_{j\in M}\in W_{M}(\Lambda )$ यदि और केवल यदि अस्तित्व है $(v_{i})_{i\in N}\in W_{N}(\Lambda )$ ऐसा है कि $w_{j}=v_{i}$ अगर $j=gi$. दूसरे शब्दों में, $W_{M}(\Lambda )$ और $W_{N}(\Lambda )$ समान कॉन्फ़िगरेशन मॉड्यूलो अनुवाद शामिल करें। हम सेट को कॉल करेंगे

$W(\Lambda ):=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }W_{N}(\Lambda )$ की भाषा $\Lambda$. यहां बताए गए सामान्य संदर्भ में, शिफ्ट स्पेस की भाषा का मतलब औपचारिक भाषा सिद्धांत के समान नहीं है, लेकिन #शास्त्रीय ढांचे में जो वर्णमाला पर विचार करता है $A$ परिमित होना, और $\mathbb {G}$ प्राणी $\mathbb {N}$ या $\mathbb {Z}$ सामान्य जोड़ के साथ, शिफ्ट स्पेस की भाषा एक औपचारिक भाषा है।

शास्त्रीय रूपरेखा

शिफ्ट स्पेस के लिए शास्त्रीय ढांचे में वर्णमाला पर विचार करना शामिल है $A$ परिमित के रूप में, और $\mathbb {G}$ गैर-ऋणात्मक पूर्णांकों के समुच्चय के रूप में ($\mathbb {N}$) सामान्य जोड़ के साथ, या सभी पूर्णांकों का सेट ($\mathbb {Z}$) सामान्य जोड़ के साथ। दोनों ही मामलों में, पहचान तत्व $\mathbf {1} _{\mathbb {G} }$ संख्या 0 से मेल खाती है। इसके अलावा, जब $\mathbb {G} =\mathbb {N}$, सब के बाद $\mathbb {N} \setminus \{0\}$ संख्या 1 से उत्पन्न किया जा सकता है, यह द्वारा दिए गए एक अद्वितीय शिफ्ट मानचित्र पर विचार करने के लिए पर्याप्त है $\sigma (\mathbf {x} )_{n}=x_{n+1}$ सभी के लिए $n$. दूसरी ओर, के मामले के लिए $\mathbb {G} =\mathbb {Z}$, सब के बाद $\mathbb {Z}$ संख्या {-1, 1} से उत्पन्न किया जा सकता है, सभी के लिए दिए गए दो शिफ्ट मानचित्रों पर विचार करना पर्याप्त है $n$ द्वारा $\sigma (\mathbf {x} )_{n}=x_{n+1}$ और तक $\sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}$.

इसके अलावा, जब भी $\mathbb {G}$ है $\mathbb {N}$ या $\mathbb {Z}$ सामान्य जोड़ के साथ (स्वतंत्र रूप से कार्डिनैलिटी से $A$), इसकी बीजगणितीय संरचना के कारण, यह केवल सिलेंडर के रूप में ही विचार करने के लिए पर्याप्त है

$[a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.$ इसके अलावा, एक शिफ्ट स्थान की भाषा $\Lambda \subset A^{\mathbb {G} }$ द्वारा दिया जाएगा

$W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),$ कहाँ $W_{0}:=\{\epsilon \}$ और $\epsilon$ खाली शब्द के लिए खड़ा है, और

$W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.$

उसी तरह, विशेष मामले के लिए $\mathbb {G} =\mathbb {Z}$, यह एक शिफ्ट स्पेस को परिभाषित करने के लिए इस प्रकार है $\Lambda =X_{F}$ हमें इसका सूचकांक निर्दिष्ट करने की आवश्यकता नहीं है $\mathbb {G}$ जिस पर वर्जित शब्द हैं $F$ परिभाषित हैं अर्थात् हम केवल विचार कर सकते हैं $F\subset \bigcup _{n\geq 1}A^{n}$ और तब

$X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.$ हालांकि, यदि $\mathbb {G} =\mathbb {N}$, यदि हम एक शिफ्ट स्पेस को परिभाषित करते हैं $\Lambda =X_{F}$ जैसा कि ऊपर दिया गया है, उस सूचकांक को निर्दिष्ट किए बिना जहां शब्द निषिद्ध हैं, तो हम केवल शिफ्ट रिक्त स्थान को कैप्चर करेंगे जो कि शिफ्ट मैप के माध्यम से अपरिवर्तनीय हैं, अर्थात, जैसे कि $\sigma (X_{F})=X_{F}$. वास्तव में, एक शिफ्ट स्पेस को परिभाषित करने के लिए $X_{F}\subset A^{\mathbb {N} }$ ऐसा है कि $\sigma (X_{F})\subsetneq X_{F}$ यह निर्दिष्ट करना आवश्यक होगा कि शब्दों पर कौन सा सूचकांक है $F$ वर्जित हैं.

विशेष रूप से, के शास्त्रीय ढांचे में $A$ परिमित होना, और $\mathbb {G}$ प्राणी $\mathbb {N}$) या $\mathbb {Z}$ सामान्य जोड़ के साथ, यह उसका अनुसरण करता है $M_{F}$ यदि और केवल यदि ही परिमित है $F$ परिमित है, जो उन स्थान परिवर्तन के रूप में परिमित प्रकार के बदलाव की शास्त्रीय परिभाषा की ओर ले जाता है $\Lambda \subset A^{\mathbb {G} }$ ऐसा है कि $\Lambda =X_{F}$ कुछ सीमित के लिए $F$.

कुछ प्रकार के शिफ्ट स्थान

कई प्रकार के शिफ्ट स्पेस में, सबसे व्यापक रूप से अध्ययन किया गया परिमित प्रकार का सबशिफ्ट और सोफिक शिफ्ट है।

मामले में जब वर्णमाला $A$ परिमित है, एक परिवर्तनशील स्थान $\Lambda$ यह एक परिमित प्रकार का बदलाव है यदि हम निषिद्ध पैटर्न का एक सीमित सेट ले सकते हैं $F$ ऐसा है कि $\Lambda =X_{F}$, और $\Lambda$ यदि यह स्लाइडिंग ब्लॉक कोड के अंतर्गत परिमित प्रकार के बदलाव की छवि है तो यह एक सोफ़िक बदलाव है(अर्थात् एक मानचित्र $\Phi$ वह सबके लिए सतत एवं अपरिवर्तनीय है $g$-शिफ्ट मानचित्र ). अगर $A$ परिमित है और $\mathbb {G}$ है $\mathbb {N}$ या $\mathbb {Z}$ सामान्य जोड़ के साथ, फिर बदलाव $\Lambda$ यह एक सामाजिक बदलाव है यदि और केवल यदि $W(\Lambda )$ एक नियमित भाषा है.

सोफ़िक नाम किसके द्वारा गढ़ा गया था? Weiss (1973), हिब्रू भाषा के शब्द סופי पर आधारित जिसका अर्थ परिमित है, इस तथ्य को संदर्भित करने के लिए कि यह एक परिमितता संपत्ति का सामान्यीकरण है। कब $A$ अनंत है, परिमित प्रकार की शिफ्ट को शिफ्ट स्पेस के रूप में परिभाषित करना संभव है $\Lambda$ उनके लिए कोई एक सेट ले सकता है $F$ ऐसे वर्जित शब्दों का $M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},$ परिमित है और $\Lambda =X_{F}$. अनंत वर्णमाला के इस संदर्भ में, एक सॉफिक शिफ्ट को स्लाइडिंग ब्लॉक कोड के एक विशेष वर्ग के तहत परिमित प्रकार की शिफ्ट की छवि के रूप में परिभाषित किया जाएगा।दोनों, की परिमितता $M_{F}$ और स्लाइडिंग ब्लॉक कोड की अतिरिक्त शर्तें, जब भी तुच्छ रूप से संतुष्ट होती हैं $A$ परिमित है.

शिफ्ट स्पेस पर टोपोलॉजिकल डायनेमिक सिस्टम

शिफ्ट स्पेस टोपोलॉजिकल स्पेस है जिस पर प्रतीकात्मक गतिशीलता आमतौर पर परिभाषित की जाती है।

शिफ्ट की जगह दी गई $\Lambda \subset A^{\mathbb {G} }$ और ए $g$-शिफ्ट मानचित्र $\sigma ^{g}:\Lambda \to \Lambda$ यह इस प्रकार है कि जोड़ी $(\Lambda ,\sigma ^{g})$ एक टोपोलॉजिकल डायनेमिक सिस्टम है।

दो शिफ्ट स्थान $\Lambda \subset A^{\mathbb {G} }$ और $\Gamma \subset B^{\mathbb {G} }$ यदि प्रत्येक के लिए स्थलाकृतिक रूप से संयुग्मित (या बस संयुग्मित) कहा जाता है $g$-शिफ्ट मैप यह इस प्रकार है कि टोपोलॉजिकल डायनेमिक सिस्टम $(\Lambda ,\sigma ^{g})$ और $(\Gamma ,\sigma ^{g})$ टोपोलॉजिकल संयुग्मता हैं, अर्थात, यदि कोई सतत मानचित्र मौजूद है $\Phi :\Lambda \to \Gamma$ ऐसा है कि $\Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi$. ऐसे मानचित्रों को सामान्यीकृत स्लाइडिंग ब्लॉक कोड या केवल स्लाइडिंग ब्लॉक कोड के रूप में जाना जाता है $\Phi$ समान रूप से निरंतर है.

यद्यपि कोई भी सतत मानचित्र $\Phi$ से $\Lambda \subset A^{\mathbb {G} }$ अपने आप में एक टोपोलॉजिकल डायनेमिक सिस्टम को परिभाषित करेगा $(\Lambda ,\Phi )$, प्रतीकात्मक गतिशीलता में केवल निरंतर मानचित्रों पर विचार करना सामान्य है $\Phi :\Lambda \to \Lambda$ जो सभी के साथ आवागमन करता है $g$-शिफ्ट मानचित्र, i. ई., मानचित्र जो सामान्यीकृत स्लाइडिंग ब्लॉक कोड हैं। गतिशील प्रणाली $(\Lambda ,\Phi )$ इसे एक सामान्यीकृत सेलुलर ऑटोमेटन के रूप में जाना जाता है (या जब भी एक सेलुलर ऑटोमेटन के रूप में जाना जाता है) $\Phi$ समान रूप से निरंतर है)।

उदाहरण

शिफ्ट स्पेस (परिमित प्रकार का) का पहला तुच्छ उदाहरण पूर्ण शिफ्ट है $A^{\mathbb {N} }$.

होने देना $A=\{a,b\}$. A के ऊपर सभी अनंत शब्दों का समूह जिसमें अधिकतम एक b हो, एक सोफिक सबशिफ्ट है, परिमित प्रकार का नहीं। ए पर सभी अनंत शब्दों का सेट जिसका बी अभाज्य लंबाई के ब्लॉक बनाता है, सोफ़िक नहीं है (इसे पम्पिंग लेम्मा का उपयोग करके दिखाया जा सकता है)।

दो अक्षरों में अनंत तारों का स्थान, $\{0,1\}^{\mathbb {N} }$ बर्नौली प्रक्रिया कहलाती है। यह कैंटर सेट के समरूपी है।

दो अक्षरों में तारों का द्वि-अनंत स्थान, $\{0,1\}^{\mathbb {Z} }$ इसे आमतौर पर बेकर के मानचित्र के रूप में जाना जाता है, या यूं कहें कि यह बेकर के मानचित्र का समरूप है।

यह भी देखें

• तम्बू का नक्शा
• बिट शिफ्ट मानचित्र
• ग्रे कोड

अग्रिम पठन

• Ceccherini-Silberstein, T.; Coornaert, M. (2010). Cellular automata and groups Springer Monographs in Mathematics. Springer Verlag. ISBN 978-3-642-14034-1.
• Lind, Douglas; Marcus, Brian (1995). An Introduction to Symbolic Dynamics and Coding. Cambridge UK: Cambridge University Press. ISBN 0-521-55900-6.
• Lothaire, M. (2002). "Finite and Infinite Words". Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0-521-81220-8. Retrieved 2008-01-29.
• Morse, Marston; Hedlund, Gustav A. (1938). "Symbolic Dynamics". American Journal of Mathematics. 60 (4): 815–866. doi:10.2307/2371264. JSTOR 2371264.
• Sobottka, M. (2022). "Some Notes on the Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts". Bulletin of the Brazilian Mathematical Society. New Series. 53 (3): 981–1031. arXiv:2010.10595. doi:10.1007/s00574-022-00292-x. S2CID 254048586.