Automatická sekvence - Automatic sequence

v matematika a teoretická informatika, an automatická sekvence (také nazývaný a k-automatická sekvence nebo a k-rozpoznatelná sekvence když někdo chce naznačit, že základ použitých číslic je k) je nekonečný sekvence termínů charakterizovaných a konečný automat. The n-tý termín automatické sekvence A(n) je mapování konečného stavu dosaženého v konečném automatu přijímajícím číslice čísla n v některých pevné základna  k.^[1][2]

An automatické nastavení je sada nezáporných celých čísel S pro které posloupnost hodnot jeho charakteristické funkce χ_S je automatická sekvence; to je S je k-automatické, pokud χ_S(n) je k-automatický, kde χ_S(n) = 1 pokud n ${displaystyle in}$ S a 0 jinak.^[3][4]

Definice

Automatické sekvence mohou být definovány mnoha způsoby, které jsou ekvivalentní. Čtyři běžné definice jsou následující.

Teorie automatů

Nechat k být pozitivní celé číslo a nechte D = (Q, Σ_k, δ, q₀, Δ, τ) být a deterministický konečný automat s výstupem, kde

• Q je konečný soubor států;
• vstupní abeceda Σ_k sestává ze sady {0,1, ...,k-1} možných číslic v základna -k notace;
• δ: Q × Σ_k → Q je přechodová funkce;
• q₀ ∈ Q je počáteční stav;
• výstupní abeceda Δ je konečná množina; a
• τ: Q → Δ je výstupní funkce mapující ze sady interních stavů na výstupní abecedu.

Rozšířením přechodové funkce δ z působení na jednotlivé číslice na působení na řetězce číslic definováním působení δ na řetězec s skládající se z číslic s₁s₂...s_t tak jako:

δ (q,s) = δ (δ (q₀, s₁s₂...s_t-1), s_t).

Definujte funkci A ze sady kladných celých čísel do výstupní abecedy Δ následujícím způsobem:

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

kde s(n) je n napsáno v základně k. Pak sekvence A = A(1)A(2)A(3) ... je a k-automatická sekvence.^[1]

Automat na čtení základny k číslice s(n) počínaje nejvýznamnější číslicí se říká přímé čtení, zatímco automat začínající nejméně významnou číslicí je zpětné čtení.^[4] Výše uvedená definice platí, zda s(n) je přímé nebo obrácené čtení.^[5]

Střídání

Nechat ${displaystyle varphi}$ být k-jednotný morfismus a volný monoid ${displaystyle Sigma ^ {*}}$ a nechte ${displaystyle au}$ být kódování (tj ${displaystyle 1}$-uniformní morfismus), jako v případě automatů-teoretický případ. Li ${displaystyle w}$ je pevný bod z ${displaystyle varphi}$- to je, pokud ${displaystyle w = varphi (w)}$-pak ${displaystyle s = au (w)}$ je k-automatická sekvence.^[6] Naopak každý k-automatickou sekvenci lze získat tímto způsobem.^[4] Tento výsledek je způsoben Cobhamem a v literatuře je označován jako Cobhamova malá věta.^[2][7]

k-jádro

Nechat k ≥ 2. The k-jádro sekvence s(n) je sada podsekcí

${displaystyle K_ {k} (s) = {s (k ^ {e} n + r): egeq 0 {ext {and}} 0leq rleq k ^ {e} -1}.}$

Ve většině případů k-jádro sekvence je nekonečné. Pokud však k-kernel je konečný, pak sekvence s(n) je k-automatický, a obrácený je také pravdivý. Je to způsobeno Eilenbergem.^[8][9][10]

Z toho vyplývá, že a k-automatická sekvence je nutně sekvence na konečné abecedě.

Formální výkonová řada

Nechat u(n) být posloupnost nad abecedou Σ a předpokládejme, že existuje injekční funkce β od Σ do konečné pole F_q, kde q = strⁿ pro některé prime str. Přidružené formální mocenské řady je

${displaystyle sum _ {igeq 0} eta (u (i)) X ^ {i}.}$

Pak sekvence u je q-automatické, jen když je tato formální mocenská řada algebraický přes F_q(X). Tento výsledek je způsoben Christolem a v literatuře je označován jako Christolova věta.^[11]

Dějiny

Automatické sekvence byly zavedeny Buči v roce 1960,^[12] ačkoli jeho práce zaujala logičtější přístup k věci a nepoužila terminologii nalezenou v tomto článku. Pojem automatických sekvencí dále studoval Cobham v roce 1972, který tyto sekvence nazval „uniformní“ sekvence značek ".^[7]

Pojem „automatická sekvence“ se poprvé objevil v příspěvku Deshouillers.^[13]

Příklady

Následující sekvence jsou automatické:

Sekvence Thue – Morse

DFAO generující sekvenci Thue-Morse

The Sekvence Thue – Morse t(n) (OEIS: A010060) je pevný bod morfismu 0 → 01, 1 → 10. Protože n-tý člen sekvence Thue – Morse počítá počet těch modulo 2 v reprezentaci základny 2 n, je generován dvoustavovým deterministickým konečným automatem s výstupem zobrazeným zde, kde je ve stavu q₀ označuje, že v reprezentaci je sudý počet n a být ve stavu q₁ označuje, že existuje lichý počet jedniček. Sekvence Thue – Morse je tedy 2-automatická.

Sekvence zdvojnásobení období

The n-tý termín sledu zdvojnásobení období d(n) (OEIS: A096268) je dána paritou exponenta nejvyšší síly 2 dělení n. Je také pevným bodem morfismu 0 → 01, 1 → 00.^[14] Počínaje počátečním obdobím w = 0 a iterace 2-uniformního morfismu φ on w kde φ (0) = 01 a φ (1) = 00, je zřejmé, že perioda zdvojnásobující sekvenci je pevným bodem φ (w), a proto je 2-automatický.

Sekvence Rudin – Shapiro

The n-té funkční období Sekvence Rudin – Shapiro r(n) (OEIS: A020985) je určen počtem po sobě jdoucích v reprezentaci základny-2 n. 2-jádro sekvence Rudin-Shapiro^[15] je

${displaystyle {egin {zarovnáno} r (2n) & = r (n), r (4n + 1) & = r (n), r (8n + 7) & = r (2n + 1), (16n + 3) & = r (8n + 3), r (16n + 11) & = r (4n + 3). End {zarovnáno}}}$

Protože 2-jádro se skládá pouze z r(n), r(2n + 1), r(4n + 3) a r(8n + 3), je konečný a sekvence Rudin – Shapiro je tedy 2-automatická.

Další sekvence

Oba Baum – sladká sekvence^[16] (OEIS: A086747) a běžná sekvence skládání papíru^[17][18][19] (OEIS: A014577) jsou automatické. Obecná sekvence skládání papíru s periodickou řadou přehybů je také automatická.^[20]

Vlastnosti

Automatické sekvence vykazují řadu zajímavých vlastností. Níže je uveden neúplný seznam těchto vlastností.

• Každá automatická sekvence je a morfické slovo.^[21]
• Pro k ≥ 2 a r ≥ 1, sekvence je k-automatické, jen když je k^r-automatický. Tento výsledek je způsoben Eilenbergem.^[22]
• Pro h a k multiplikativně nezávislé, sekvence je obojí h-automatické a k-automatické, jen když je to nakonec periodické.^[23] Tento výsledek je způsoben Cobhamem,^[24] s vícerozměrným zevšeobecněním kvůli Semenovovi.^[25][26]
• Li u(n) je k-automatická sekvence nad abecedou Σ a F je jednotný morfismus od Σ^∗ do jiné abecedy Δ^∗, pak F(u) je k-automatická sekvence nad Δ.^[27]
• Li u(n) je k-automatická sekvence, pak sekvence u(kⁿ) a u(kⁿ - 1) jsou nakonec periodické.^[28] Naopak, pokud u(n) je nakonec periodická sekvence, pak sekvence proti definován proti(kⁿ) = u(n) a jinak je nula k-automatický.^[29]

Prokazování a vyvracení automatičnosti

Daná kandidátní sekvence ${displaystyle s = (s_ {n}) _ {ngeq 0}}$, je obvykle snazší vyvrátit jeho automatičnost než dokázat. Podle k- charakterizace jádra k-automatické sekvence, stačí vytvořit nekonečně mnoho odlišných prvků v k-jádro ${displaystyle K_ {k} (y)}$ ukázat to ${displaystyle s}$ není k-automatický. Heuristicky by se člověk mohl pokusit dokázat automatičnost kontrolou shody podmínek v k- jádro, ale to může občas vést k chybným odhadům. Například pojďme

${displaystyle t = 011010011dots}$

být slovo Thue – Morse. Nechat ${displaystyle s}$ být slovo dané zřetězením po sobě jdoucích výrazů v pořadí délky běhu ${displaystyle t}$. Pak ${displaystyle s}$ začíná

${displaystyle s = 12112221 bodů.}$.

Je známo že ${displaystyle s}$ je pevný bod ${displaystyle h ^ {omega} (1)}$ morfismu

${displaystyle h (1) = 121, h (2) = 12221.}$

Slovo ${displaystyle s}$ není 2-automatický, ale některé prvky jeho 2-jádra souhlasí s mnoha termíny. Například,${displaystyle s_ {16n + 1} = s_ {64n + 1} {ext {for}} 0leq nleq 1864134}$

ale ne pro ${displaystyle n = 1864135}$.^[30]

Vzhledem k tomu, že posloupnost je považována za automatickou, existuje několik užitečných přístupů k prokázání, že ve skutečnosti je. Jedním z přístupů je přímá konstrukce deterministického automatu s výstupem, který dává posloupnost. Nechat ${displaystyle (s_ {n}) _ {ngeq 0}}$ psaný v abecedě ${displaystyle Delta}$a nechte ${displaystyle (n) _ {k}}$ označit základnu${displaystyle k}$ expanze ${displaystyle n}$. Pak sekvence ${displaystyle s = (s_ {n}) _ {ngeq 0}}$ je ${displaystyle k}$-automatické, pokud a pouze každé z vláken

${displaystyle I_ {k} (s, d): = {(n) _ {k} střední s_ {n} = d}}$

je běžný jazyk.^[31] Pravidelnost vláken lze kontrolovat často pomocí čerpání lemmatu pro běžné jazyky.

Li ${displaystyle s_ {k} (n)}$ označuje součet číslic v základně${displaystyle k}$ expanze ${displaystyle n}$ a ${displaystyle p (X)}$ je polynom s nezápornými celočíselnými koeficienty, a pokud ${displaystyle kgeq 2}$, ${displaystyle mgeq 1}$ jsou celá čísla, pak sekvence

${displaystyle (s_ {k} (p (n)) {pmod {m}}) _ {ngeq 0}}$

je ${displaystyle k}$-automatické právě tehdy ${displaystyle deg pleq 1}$ nebo ${displaystyle mmid k-1}$.^[32]

1-automatické sekvence

k-automatické sekvence jsou obvykle definovány pouze pro k ≥ 2.^[1] Koncept lze rozšířit na k = 1 definováním 1-automatické sekvence jako sekvence, jejíž n-tý termín závisí na unární notace pro n; to znamená, (1)ⁿ. Protože se automat konečného stavu musí nakonec vrátit do dříve navštíveného stavu, jsou všechny 1-automatické sekvence nakonec periodické.

Zobecnění

Automatické sekvence jsou robustní proti variacím definice nebo vstupní sekvence. Například, jak je uvedeno v teoretické definici automatů, daná sekvence zůstává automatická při přímém i zpětném čtení vstupní sekvence. Sekvence také zůstane automatická, když se použije alternativní sada číslic nebo když je základna negována; to znamená, když je vstupní sekvence reprezentována v base -k místo v základně k.^[33] Avšak na rozdíl od použití alternativní sady číslic může změna základny ovlivnit automatičnost sekvence.

Doménu automatické sekvence lze rozšířit z přirozených čísel na celá čísla pomocí oboustranný automatické sekvence. To vyplývá ze skutečnosti, že vzhledem k tomu k ≥ 2, každé celé číslo může být reprezentováno jedinečně ve formě ${displaystyle sum _ {0leq ileq r} a_ {i} (- k) ^ {i},}$ kde ${displaystyle a_ {i} v {0, tečky, k-1}}$. Pak oboustranný nekonečný sled A(n)_{n ${displaystyle v mathbb {Z}}$} je (-k) -automatická právě tehdy, pokud jsou její podsekvence A(n)_{n ≥ 0} a A(−n)_{n ≥ 0} jsou k-automatický.^[34]

Abeceda a k-automatická sekvence může být prodloužena z konečné velikosti na nekonečnou velikost pomocí k-pravidelné sekvence.^[35] The k-pravidelné sekvence lze charakterizovat jako ty sekvence, jejichž k-kernel je definitivně generován. Každý omezený k-pravidelná sekvence je automatická.^[36]

Logický přístup

Pro mnoho 2-automatických sekvencí ${displaystyle s = (s_ {n}) _ {ngeq 0}}$, mapa ${displaystyle nmapsto s_ {n}}$ má tu vlastnost, že teorie prvního řádu ${displaystyle {ext {FO}} (mathbb {N}, +, 0,1, nmapsto s_ {n})}$ je rozhodnutelné. Protože mnoho netriviálních vlastností automatických sekvencí lze zapsat do logiky prvního řádu, je možné tyto vlastnosti mechanicky dokázat provedením rozhodovacího postupu.^[37]

Například následující vlastnosti slova Thue – Morse lze všechny mechanicky ověřit tímto způsobem:

• Slovo Thue – Morse je bez překrytí, tj. Neobsahuje slovo ve formě ${displaystyle cxcxc}$ kde ${displaystyle c}$ je jedno písmeno a ${displaystyle w}$ je možná prázdné slovo.
• Neprázdné slovo ${displaystyle x}$ je ohraničený pokud existuje neprázdné slovo ${displaystyle w}$ a možná prázdné slovo ${displaystyle y}$ s ${displaystyle x = wyw}$. Slovo Thue – Morse obsahuje ohraničený faktor pro každou délku větší než 1.^[38]
• Existuje neomezený faktor délky ${displaystyle n}$ ve slově Thue – Morse právě tehdy ${displaystyle (n) _ {2} otin 1 (01 ^ {*} 0) ^ {*} 10 ^ {*} 1}$ kde ${displaystyle (n) _ {2}}$ označuje binární vyjádření ${displaystyle n}$.^[39]

Software Walnut,^[40][41] vyvinutý Hamoonem Mousavim, implementuje rozhodovací postup pro rozhodování o mnoha vlastnostech určitých automatických slov, jako je slovo Thue – Morse. Tato implementace je důsledkem výše uvedené práce na logickém přístupu k automatickým sekvencím.

Viz také

• Büchiho aritmetika

Poznámky

Reference

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatické sekvence: Teorie, Aplikace, Zobecnění. Cambridge University Press. ISBN  978-0-521-82332-6. Zbl  1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Kombinatorika slov. Christoffel slova a opakování slov. Série monografií CRM. 27. Providence, RI: Americká matematická společnost. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
• Berstel, Jean; Reutenauer, Christophe (2011). Nekomutativní racionální řady s aplikacemi. Encyklopedie matematiky a její aplikace. 137. Cambridge: Cambridge University Press. ISBN  978-0-521-19022-0. Zbl  1250.68007.
• Cobham, Alan (1972). Msgstr "Jednotné sekvence značek". Matematika. Teorie systémů. 6 (1–2): 164–192. doi:10.1007 / BF01706087.
• Lothaire, M. (2005). Aplikovaná kombinatorika na slova. Encyklopedie matematiky a její aplikace. 105. Kolektivní dílo 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 a Valérie Berthé. Cambridge: Cambridge University Press. ISBN  978-0-521-84802-2. Zbl  1133.68067.
• Pytheas Fogg, N. (2002). Substituce v dynamice, aritmetice a kombinatorice. Přednášky z matematiky. 1794. Redaktoři Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlín: Springer-Verlag. ISBN  978-3-540-44141-0. Zbl  1014.11015.

Další čtení

• Berthé, Valérie; Rigo, Michel, eds. (2010). Kombinatorika, automaty a teorie čísel. Encyklopedie matematiky a její aplikace. 135. Cambridge: Cambridge University Press. ISBN  978-0-521-51597-9. Zbl  1197.68006.
• Loxton, J. H. (1988). "13. Automaty a transcendence". v Baker, A. (vyd.). Nové pokroky v teorii transcendence. Cambridge University Press. str.215 –228. ISBN  978-0-521-33545-4. Zbl  0656.10032.
• Rowland, Eric (2015), „Co je to ... automatická sekvence?“, Oznámení Americké matematické společnosti, 62 (3): 274–276, doi:10.1090 / noti1218.
• Shallit, Jeffrey (1999). "Teorie čísel a formální jazyky". v Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. (eds.). Nové aplikace teorie čísel. Na základě jednání z letního programu IMA, Minneapolis, MN, USA, 15. – 26. Července 1996. Objemy IMA v matematice a jejích aplikacích. 109. Springer-Verlag. 547–570. ISBN  978-0-387-98824-5.