स्वचालित अनुक्रम

गणित और सैद्धांतिक कंप्यूटर विज्ञान में, एक स्वचालित अनुक्रम (जिसे k-स्वचालित अनुक्रम या k-पहचानने योग्य अनुक्रम भी कहा जाता है, जब कोई यह इंगित करना चाहता है कि उपयोग किए गए अंकों का आधार k है ) एक परिमित स्वचल प्ररूप की विशेषता वाले शब्दों का एक अनंत क्रम है। एक स्वचालित अनुक्रम a(n) का n-वाँ शब्द अंतिम अवस्था का मानचित्रण है, जो कुछ में संख्या n के अंकों को स्वीकार करने वाले परिमित स्वचल प्ररूप में पहुंचा है। निश्चित मूलांक क। एक स्वचालित सम्मुच्चय गैर-ऋणात्मक पूर्णांक S का एक सम्मुच्चय है, जिसके लिए इसकी विशेषता फलन χ_S के मानों का क्रम एक स्वचालित अनुक्रम है; अर्थात्, यदि χ_S(n) है तो S k-स्वचालित है, जहां χ_S(n) = 1 अगर n $\in$ s और अन्यथा 0 है।

परिभाषा

स्वचालित अनुक्रमों को कई तरीकों से परिभाषित किया जा सकता है, जो सभी समतुल्य हैं। चार सामान्य परिभाषाएँ इस प्रकार हैं।

स्वचल प्ररूप-सैद्धांतिक

मान लीजिए k एक धनात्मक पूर्णांक है, और मान लीजिए D = (Q, Σ_k, δ, q₀, Δ, τ) प्रक्षेपण के साथ एक निर्धारक परिमित स्वचल प्ररूप बनें, जहां

• q स्थिति का परिमित सम्मुच्चय (गणित) है;
• निविष्ट वर्णमाला Σ_k मूलांक-के चिन्हांकन में संभावित अंकों के सम्मुच्चय {0,1,...,k-1} सम्मिलित हैं;
• δ : q × Σ_k → q संक्रमण फलन है;
• q₀∈ q प्रारंभिक अवस्था है;
• प्रक्षेपण वर्णक्रम Δ एक परिमित सम्मुच्चय है; और
• τ : q → Δ आंतरिक स्थिति के सम्मुच्चय से प्रक्षेपण वर्णमाला में प्रक्षेपण फलन प्रतिचित्रण है।

एक श्रृंखला s₁s₂...s_t पर δ की क्रिया को परिभाषित करके फलन δ को एकल अंकों पर अभिनय से अंकों के तारों पर अभिनय करने तक बढ़ाएं। जैसे:

δ (q, S) = δ (δ (q, S₁s₂...S_t-1), S_t).

एक फलन को सकारात्मक पूर्णांक के सम्मुच्चय से प्रक्षेपण वर्णमाला Δ में निम्नानुसार परिभाषित करें:

a(n) = τ(δ(q₀,s(n))),

जहाँ s(n) को आधार k में लिखा गया है। तब अनुक्रम a = a(1)a(2)a(3)... एक k-स्वचालित अनुक्रम है।

सबसे महत्वपूर्ण अंक से प्रारम्भ होने वाले s(n) के आधार k अंकों को पढ़ने वाला स्वचल प्ररूप प्रत्यक्ष पठन कहा जाता है, जबकि कम से कम महत्वपूर्ण अंक से प्रारम्भ होने वाला स्वचल प्ररूप पंट पठन है। उपरोक्त परिभाषा यह मानती है कि s(n) प्रत्यक्ष या विपरीत पठन है या नहीं है।

प्रतिस्थापन

मान लीजिए $\varphi$ मुक्त मोनॉइड $\Sigma ^{*}$ का k-समान आकारिकी है और $\tau$ एक कूटलेखन हो (यानी, a $1$-समान रूपवाद), जैसा कि स्वचल प्ररूप-सैद्धांतिक स्तिथि में है। यदि $w$ $\varphi$ का एक निश्चित बिंदु है - अर्थात, यदि $w=\varphi (w)$ तो $s=\tau (w)$ एक k-स्वचालित क्रम है। इसके विपरीत, प्रत्येक k-स्वचालित अनुक्रम इस तरह से प्राप्य है। यह परिणाम एलन कोभम (गणितज्ञ) के कारण है, और इसे साहित्य में कोभम की छोटी प्रमेय के रूप में संदर्भित किया जाता है।

के-कर्नेल

मान लीजिए k ≥ 2 है। अनुक्रम s(n) का k-कर्नेल अनुगामी का समुच्चय है

$K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.$

अधिकतर स्तिथियों में, अनुक्रम का k-कर्नेल अनंत है। हालाँकि, यदि k-कर्नेल परिमित है, तो अनुक्रम s(n) k-स्वचालित है, और इसका विलोम भी सत्य है। यह ईलेनबर्ग के कारण है।

यह इस प्रकार है कि एक k-स्वचालित अनुक्रम आवश्यक रूप से एक परिमित वर्णमाला पर एक अनुक्रम है।

औपचारिक शक्ति श्रृंखला

मान लीजिए u(n) एक वर्णमाला Σ पर अनुक्रम है और मान लें कि Σ से सीमित क्षेत्र F_q तक एक अंतःक्षेपक फलन β है, जहां कुछ अभाज्य p के लिए q = pⁿ है। संबंधित औपचारिक शक्ति श्रृंखला निम्न है

$\sum _{i\geq 0}\beta (u(i))X^{i}$

तब अनुक्रम u q-स्वचालित है यदि और केवल यदि यह औपचारिक शक्ति श्रृंखला F_q(X) पर बीजगणितीय कार्य है। यह परिणाम क्रिस्टोल के कारण है, और इसे साहित्य में क्रिस्टोल के प्रमेय के रूप में जाना जाता है।

इतिहास

1960 में जूलियस रिचर्ड बुची द्वारा स्वचालित अनुक्रम प्रस्तुत किए गए, हालांकि उनके लेख ने इस स्तिथि में अधिक तार्किक-सैद्धांतिक दृष्टिकोण अपनाया और इस लेख में पाई जाने वाली शब्दावली का उपयोग नहीं किया। 1972 में कोभम द्वारा स्वचालित अनुक्रमों की धारणा का और अध्ययन किया गया, जिन्होंने इन अनुक्रमों को एकसमान टैग प्रणाली कहा था।

स्वत: अनुक्रम शब्द पहली बार देशोइलर्स के एक लेख में दिखाई दिया।

उदाहरण

निम्नलिखित क्रम स्वचालित हैं:

थू-मोर्स क्रम

File:ThueMorseAutomaton.png

डीएफएओ थू-मोर्स अनुक्रम उत्पन्न करता है

थू-मोर्स अनुक्रम टी(एन) (OEIS: A010060) रूपवाद 0 → 01, 1 → 10 का निश्चित बिंदु (गणित) है। चूंकि थ्यू-मोर्स अनुक्रम का n-वाँ पद n के आधार-2 प्रतिनिधित्व में मोडुलो ऑपरेशन 2 की संख्या की गणना करता है, यह यहाँ चित्रित प्रक्षेपण के साथ दो-राज्य नियतात्मक परिमित स्वचल प्ररूप द्वारा उत्पन्न होता है, जहाँ राज्य q में होता है₀ इंगित करता है कि n के प्रतिनिधित्व में और राज्य q में होने की संख्या भी है₁ इंगित करता है कि विषम संख्याएँ हैं।

इसलिए, थ्यू-मोर्स अनुक्रम 2-स्वचालित है।

अवधि-दोहरीकरण अनुक्रम

अवधि-दोहरीकरण अनुक्रम का n-वाँ पद d(n) (OEIS: A096268) 2 विभाजक n की उच्चतम शक्ति के घातांक की समानता से निर्धारित होता है। यह आकृतिवाद 0 → 01, 1 → 00 का निश्चित बिंदु भी है। प्रारंभिक शब्द w = 0 से प्रारम्भ करना और 2-समान आकारिकी φ को w पर पुनरावृत्त करना जहां φ(0) = 01 और φ(1) = 00, यह स्पष्ट है कि अवधि-दोहरीकरण अनुक्रम φ का निश्चित-बिंदु है ( डब्ल्यू) और इस प्रकार यह 2-स्वचालित है।

रुडिन-शापिरो अनुक्रम

रुडिन-शापिरो अनुक्रम का n-वाँ पद r(n) (OEIS: A020985) n के आधार-2 प्रतिनिधित्व में लगातार लोगों की संख्या से निर्धारित होता है। रुडिन-शापिरो अनुक्रम का 2-कर्नेल है

${\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}$

चूँकि 2-कर्नेल में केवल r(n), r(2n + 1), r(4n + 3), और r(8n + 3) होते हैं, यह परिमित है और इस प्रकार रुडिन-शापिरो अनुक्रम 2-स्वचालित है।

अन्य अनुक्रम

बॉम-स्वीट सीक्वेंस दोनों (OEIS: A086747) और नियमित पेपरफोल्डिंग अनुक्रम (OEIS: A014577) स्वचालित हैं। इसके अलावा, फोल्ड के आवधिक अनुक्रम के साथ सामान्य लेख फोल्डिंग अनुक्रम भी स्वचालित होता है।

गुण

स्वचालित अनुक्रम कई दिलचस्प गुण प्रदर्शित करते हैं। इन संपत्तियों की एक गैर-संपूर्ण सूची नीचे प्रस्तुत की गई है।

• प्रत्येक स्वचालित अनुक्रम एक रूपात्मक शब्द है।
• k ≥ 2 और r ≥ 1 के लिए, एक अनुक्रम k-स्वचालित होता है यदि और केवल यदि यह k है^आर-स्वचालित। यह परिणाम ईलेनबर्ग के कारण है।
• एच और के गुणक स्वतंत्रता के लिए, एक अनुक्रम एच-स्वचालित और के-स्वचालित दोनों होता है यदि और केवल यदि यह अंततः आवधिक होता है। यह परिणाम Cobham के कारण है जिसे Cobham's theorem के नाम से भी जाना जाता है, सेमेनोव के कारण बहुआयामी सामान्यीकरण के साथ।
• यदि यू(एन) एक वर्णमाला Σ पर एक के-स्वचालित अनुक्रम है और एफ Σ से एक समान आकारिकी है^∗ दूसरे अक्षर Δ में^∗, तो f(u) Δ पर एक k-स्वचालित अनुक्रम है।
• यदि यू(एन) एक के-स्वचालित अनुक्रम है, तो अनुक्रम यू(के^एन) और यू (केⁿ − 1) अंततः आवधिक हैं। इसके विपरीत, यदि यू(एन) एक अंततः आवधिक अनुक्रम है, तो अनुक्रम वी वी(के) द्वारा परिभाषित किया गया हैⁿ) = u(n) और अन्यथा शून्य k-स्वचालित है।

स्वचलितता को सिद्ध और अस्वीकृत करना

एक उम्मीदवार अनुक्रम दिया $s=(s_{n})_{n\geq 0}$, आमतौर पर इसकी स्वचालितता को साबित करने की तुलना में इसका खंडन करना आसान होता है। के-स्वचालित अनुक्रमों के के-कर्नेल लक्षण वर्णन द्वारा, यह के-कर्नेल में असीमित रूप से कई अलग-अलग तत्वों का उत्पादन करने के लिए पर्याप्त है $K_{k}(s)$ उसे दिखाने के लिए $s$ के-स्वचालित नहीं है। स्वाभाविक रूप से, कोई के-कर्नेल में शर्तों के समझौते की जाँच करके स्वचालितता साबित करने का प्रयास कर सकता है, लेकिन यह कभी-कभी गलत अनुमान लगा सकता है। उदाहरण के लिए, चलो

$t=011010011\dots$

थ्यू-मोर्स शब्द हो। होने देना $s$ रन-लेंथ के क्रम में क्रमिक शब्दों को जोड़कर दिया गया शब्द हो $t$. तब $s$ प्रारम्भ करना

$s=12112221\dots .$.

ह ज्ञात है कि $s$ नियत बिन्दु है $h^{\omega }(1)$ रूपवाद का

$h(1)=121,h(2)=12221.$

शब्द $s$ 2-स्वचालित नहीं है, लेकिन इसके 2-कर्नेल के कुछ तत्व कई शर्तों के लिए सहमत हैं। उदाहरण के लिए, $s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134$ लेकिन के लिए नहीं $n=1864135$. स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह साबित करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे प्रक्षेपण के साथ एक नियतात्मक स्वचल प्ररूप का निर्माण करना है जो अनुक्रम देता है। होने देना $(s_{n})_{n\geq 0}$ वर्णमाला में लिखा है $\Delta$, और जाने $(n)_{k}$ आधार को निरूपित करें-$k$ का विस्तार $n$. फिर क्रम $s=(s_{n})_{n\geq 0}$ है $k$-स्वचालित अगर और केवल प्रत्येक फाइबर

$I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}$

नियमित भाषा है। तंतुओं की नियमितता की जाँच अक्सर नियमित भाषाओं के लिए पम्पिंग लेम्मा का उपयोग करके की जा सकती है।

अगर $s_{k}(n)$ आधार में अंकों के योग को दर्शाता है-$k$ का विस्तार $n$ और $p(X)$ गैर-ऋणात्मक पूर्णांक गुणांक वाला एक बहुपद है, और यदि $k\geq 2$, $m\geq 1$ पूर्णांक हैं, तो क्रम

$(s_{k}(p(n)){\pmod {m}})_{n\geq 0}$

है $k$-स्वचालित अगर और केवल अगर $\deg p\leq 1$ या $m\mid k-1$.

1-स्वचालित अनुक्रम

k-स्वचालित क्रम सामान्य रूप से केवल k ≥ 2 के लिए परिभाषित किए जाते हैं।1-स्वचालित अनुक्रम को एक अनुक्रम के रूप में परिभाषित करके अवधारणा को k = 1 तक बढ़ाया जा सकता है जिसका n-वाँ पद n के लिए एकात्मक अंक प्रणाली पर निर्भर करता है; अर्थात्, (1)^एन. चूंकि एक परिमित राज्य स्वचल प्ररूप अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 1-स्वचालित अनुक्रम अंततः आवधिक होते हैं।

सामान्यीकरण

परिभाषा या निविष्ट अनुक्रम में भिन्नता के खिलाफ स्वचालित अनुक्रम मजबूत होते हैं। उदाहरण के लिए, जैसा कि स्वचल प्ररूप-सैद्धांतिक परिभाषा में उल्लेख किया गया है, एक दिया गया अनुक्रम निविष्ट अनुक्रम के प्रत्यक्ष और पंट पठन दोनों के तहत स्वचालित रहता है। जब अंकों के एक वैकल्पिक सम्मुच्चय का उपयोग किया जाता है या जब आधार को नकारा जाता है तो अनुक्रम भी स्वचालित रहता है; वह है, जब निविष्ट अनुक्रम को आधार k के बजाय आधार -k में दर्शाया जाता है। हालांकि, अंकों के वैकल्पिक सम्मुच्चय का उपयोग करने के विपरीत, आधार में परिवर्तन अनुक्रम की स्वचालितता को प्रभावित कर सकता है।

स्वचालित अनुक्रम के डोमेन को दो तरफा स्वचालित अनुक्रमों के माध्यम से प्राकृतिक संख्याओं से पूर्णांक तक बढ़ाया जा सकता है। यह इस तथ्य से उपजा है कि, दिए गए k ≥ 2, प्रत्येक पूर्णांक को रूप में विशिष्ट रूप से दर्शाया जा सकता है $\sum _{0\leq i\leq r}a_{i}(-k)^{i},$ कहाँ $a_{i}\in \{0,\dots ,k-1\}$. फिर एक दो तरफा अनंत अनुक्रम a(n)_{n $\in \mathbb {Z}$} is (−k)-स्वचालित अगर और केवल अगर इसके बाद a(n)_{n ≥ 0} और एक (−n)_{n ≥ 0} के-स्वचालित हैं। के-स्वचालित अनुक्रम के वर्णमाला को के-नियमित अनुक्रम | के-नियमित अनुक्रमों के माध्यम से परिमित आकार से अनंत आकार तक बढ़ाया जा सकता है। के-नियमित अनुक्रमों को उन अनुक्रमों के रूप में वर्णित किया जा सकता है जिनके के-कर्नेल सूक्ष्म रूप से उत्पन्न होते हैं। प्रत्येक घिरा हुआ के-नियमित अनुक्रम स्वचालित है।

तार्किक दृष्टिकोण

कई 2-स्वचालित अनुक्रमों के लिए $s=(s_{n})_{n\geq 0}$, वो नक्शा $n\mapsto s_{n}$ संपत्ति है कि प्रथम-क्रम सिद्धांत ${\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})$ निर्णायकता (तर्क) है। चूंकि स्वचालित अनुक्रमों के कई गैर-तुच्छ गुणों को प्रथम-क्रम तर्क में लिखा जा सकता है, इसलिए इन गुणों को यांत्रिक रूप से निर्णय प्रक्रिया को निष्पादित करके सिद्ध करना संभव है। उदाहरण के लिए, थ्यू-मोर्स शब्द के निम्नलिखित गुणों को यांत्रिक रूप से इस तरह से सत्यापित किया जा सकता है:

• थू-मोर्स शब्द ओवरलैप-फ्री है, यानी इसमें फॉर्म का कोई शब्द नहीं है $cxcxc$ कहाँ $c$ एक अक्षर है और $w$ संभवतः खाली शब्द है।
• एक गैर-खाली शब्द $x$ अगर कोई गैर-खाली शब्द है तो सीमाबद्ध है $w$ और संभवतः खाली शब्द $y$ साथ $x=wyw$. थ्यू-मोर्स शब्द में 1 से अधिक प्रत्येक लंबाई के लिए सीमाबद्ध कारक होता है।
• लंबाई का एक असंबद्ध कारक है $n$ थ्यू-मोर्स शब्द में अगर और केवल अगर $(n)_{2}\notin 1(01^{*}0)^{*}10^{*}1$ कहाँ $(n)_{2}$ के द्विआधारी प्रतिनिधित्व को दर्शाता है $n$.

सॉफ्टवेयर अखरोट, Hamoon Mousavi द्वारा विकसित, कुछ स्वचालित शब्दों के कई गुणों को तय करने के लिए एक निर्णय प्रक्रिया को लागू करता है, जैसे कि थ्यू-मोर्स शब्द। यह कार्यान्वयन स्वचालित अनुक्रमों के तार्किक दृष्टिकोण पर उपरोक्त कार्य का परिणाम है।

यह भी देखें

• अंकगणित पुस्तक

संदर्भ

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Cobham, Alan (1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. S2CID 28356747.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 978-0-521-84802-2. Zbl 1133.68067.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 978-3-540-44141-0. Zbl 1014.11015.

अग्रिम पठन

• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Loxton, J. H. (1988). "13. Automata and transcendence". In Baker, A. (ed.). New Advances in Transcendence Theory. Cambridge University Press. pp. 215–228. ISBN 978-0-521-33545-4. Zbl 0656.10032.
• Rowland, Eric (2015). "What is ... an automatic sequence?". Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
• Shallit, Jeffrey (1999). "Number theory and formal languages". In Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. (eds.). Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996. The IMA volumes in mathematics and its applications. Vol. 109. Springer-Verlag. pp. 547–570. ISBN 978-0-387-98824-5.