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

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

परिभाषा

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

ऑटोमेटा-सैद्धांतिक

मान लीजिए k एक धनात्मक पूर्णांक है, और मान लीजिए D = (Q, Σ_k, डी, क्यू₀, Δ, τ) आउटपुट के साथ एक निर्धारक परिमित automaton बनें, जहां

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

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

δ (क्यू, एस) = δ (δ (क्यू, एस₁s₂...एस_t-1), एस_t).

एक फ़ंक्शन को सकारात्मक पूर्णांक के सेट से आउटपुट वर्णमाला Δ में निम्नानुसार परिभाषित करें:

ए (एन) = τ (δ (क्यू₀, एस (एन))),

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

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

प्रतिस्थापन

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

के-कर्नेल

मान लीजिए 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-कर्नेल परिमित है, तो अनुक्रम s(n) k-स्वचालित है, और इसका विलोम भी सत्य है। यह ईलेनबर्ग के कारण है। यह इस प्रकार है कि एक के-स्वचालित अनुक्रम आवश्यक रूप से एक परिमित वर्णमाला पर एक अनुक्रम है।

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

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

$\sum _{i\geq 0}\beta (u(i))X^{i}.$ तब अनुक्रम u q-स्वचालित है यदि और केवल यदि यह औपचारिक शक्ति श्रृंखला 'F' पर बीजगणितीय कार्य है_q(एक्स)। यह परिणाम क्रिस्टोल के कारण है, और इसे साहित्य में क्रिस्टोल के प्रमेय के रूप में जाना जाता है।

इतिहास

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$. स्वचालित होने का अनुमान लगाने वाले अनुक्रम को देखते हुए, वास्तव में यह साबित करने के लिए कुछ उपयोगी दृष्टिकोण हैं। एक दृष्टिकोण सीधे आउटपुट के साथ एक नियतात्मक automaton का निर्माण करना है जो अनुक्रम देता है। होने देना $(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)^एन. चूंकि एक परिमित राज्य automaton अंततः पहले देखी गई स्थिति में वापस आना चाहिए, सभी 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.