शिफ्ट स्पेस

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

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

परिभाषा

मान लीजिए कि $\mathbb {G}$ एक मोनॉइड है, और दिए गए $g,h\in \mathbb {G}$, उत्पाद $gh$ द्वारा $h$ के साथ $g$ के संचालन को निरूपित करते हैं। मान लीजिए कि $\mathbf {1} _{\mathbb {G} }$ की पहचान दर्शाता है। असतत टोपोलॉजी के साथ एक गैर-रिक्त समुच्च्य $A$ (एक वर्णमाला) पर विचार करें, और $A^{\mathbb {G} }$ द्वारा अनुक्रमित $A$ पर सभी पैटर्न के समुच्च्य $\mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }$ के रूप में परिभाषित करें। और एक उपसमुच्चय के लिए $\mathbb {G}$, हम $N$ के सूचकांकों पर $\mathbf {x}$ के प्रतिबंध को $\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$ दें। $D$ और $a_{i}\in A$ द्वारा दिया गया सिलेंडर समुच्चय $(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\}$ हम सिलेंडर को $g$ द्वारा अनुक्रमित प्रविष्टि पर प्रतीक $b$ को ठीक से $[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$ के ऊपर एक शिफ्ट स्पेस एक समुच्चय है जो कि टोपोलॉजी के अनुसार संवृत $A^{\mathbb {G} }$ है और अपरिवर्तनीय है। अनुवाद, अर्थात, सभी के लिए $\sigma ^{g}(\Lambda )\subset \Lambda$ हम शिफ्ट स्पेस $\Lambda$ में विचार करते हैं $g\in \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}$ और शिफ्ट स्पेस को समुच्चय के रूप में परिभाषित करें

प्रत्येक $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$ रिक्त शब्द के लिए है, और $W_{N}(\Lambda )\subset A^{N}$ के लिए $N\neq \emptyset$ के सभी परिमित कॉन्फ़िगरेशन का समुच्चय है जो $\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_{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}$.

शिफ्ट स्पेस के लिए मौलिक रुपरेखा में वर्णमाला $A$ को परिमित माना जाता है, और $\mathbb {G}$ को सामान्य जोड़ के साथ गैर-नकारात्मक पूर्णांक ($\mathbb {N}$) के समुच्चय के रूप में माना जाता है, या सभी पूर्णांकों का समुच्चय ($\mathbb {Z}$} ) सामान्य जोड़ के साथ। दोनों मामलों में, पहचान तत्व संख्या 0 से मेल खाता है। सभी $\mathbb {N} \setminus \{0\}$ को संख्या $\mathbf {1} _{\mathbb {G} }$ से उत्पन्न किया जा सकता है, यह एक अद्वितीय शिफ्ट मैप पर विचार करने के लिए पर्याप्त है जो कि दिया गया है। $\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_{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$ परिमित है और $g$ सामान्य जोड़ के साथ $\mathbb {N}$ या $\mathbb {G}$ है, तो शिफ्ट $\Lambda$ एक सोफ़िक शिफ्ट है यदि और केवल यदि $W(\Lambda )$ है

"सोफिक" नाम वेइस (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 )$, प्रतीकात्मक गतिशीलता में यह सामान्य है केवल सतत मानचित्रों पर विचार करने के लिए, जो सभी $g$-शिफ्ट मानचित्रों के साथ आवागमन करते हैं। $\Phi :\Lambda \to \Lambda$ मानचित्र जो सामान्यीकृत स्लाइडिंग ब्लॉक कोड हैं। गतिशील प्रणाली को एक सामान्यीकृत सेलुलर ऑटोमेटन $(\Lambda ,\Phi )$ के रूप में जाना जाता है (या जब भी $\Phi$ समान रूप से निरंतर होता है तो एक सेलुलर ऑटोमेटन के रूप में जाना जाता है)।

उदाहरण

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

मान लीजिए $A=\{a,b\}$ 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.