Automatisk sekvens

  Inom matematik och teoretisk datavetenskap är en automatisk sekvens (även kallad en k -automatisk sekvens eller en k -igenkännbar sekvens när man vill ange att basen för de använda siffrorna är k ) en oändlig sekvens av termer som kännetecknas av en finit automat . Den n :e termen i en automatisk sekvens a ( n ) är en avbildning av det slutliga tillståndet som nås i en finit automat som accepterar siffrorna i talet n i någon fast bas k .

   En automatisk mängd är en uppsättning icke-negativa heltal S för vilka sekvensen av värden för dess karakteristiska funktion χ _S är en automatisk sekvens; det vill säga S är k -automatisk om χ _S ( n ) är k -automatisk, där χ _S ( n ) = 1 om n $\in$ S och 0 annars.

Definition

Automatiska sekvenser kan definieras på ett antal sätt, som alla är likvärdiga. Fyra vanliga definitioner är följande.

Automatteoretisk

Låt k vara ett positivt heltal , och låt D = ( Q , Σ _k , δ, q ₀ , Δ, τ) vara en deterministisk finit automat med utgång , där

• Q är den ändliga uppsättningen av tillstånd;
• inmatningsalfabetet Σk _består av mängden {0,1,..., k -1} av möjliga siffror i bas - k -notation;
• δ : Q × Σ _k → Q är övergångsfunktionen;
• q ₀ ∈ Q är initialtillståndet;
• det utgående alfabetet A är en ändlig mängd; och
• τ : Q → Δ är utgångsfunktionens mappning från uppsättningen av interna tillstånd till utgångsalfabetet.

Utöka övergångsfunktionen δ från att verka på ensiffriga till att agera på strängar av siffror genom att definiera verkan av δ på en sträng s som består av siffror s ₁ s ₂ ... s _t som:

5( q , s ) = 5(5 _{( q} , s1s2 ... st - _{1 )} , _st ) .

Definiera en funktion a från uppsättningen positiva heltal till det utgående alfabetet Δ enligt följande:

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

där s ( n ) är n skrivet i basen k . Då är sekvensen a = a (1) a (2) a (3)... en k -automatisk sekvens.

En automat som läser basens k -siffror i s ( n ) som börjar med den mest signifikanta siffran sägs vara direktavläsning , medan en automat som börjar med den minst signifikanta siffran är omvänd läsning . Ovanstående definition gäller om s ( n ) är direkt eller omvänd avläsning.

Utbyte

Låt $\varphi$ vara en k - enhetlig morfism av en fri monoid $\Sigma ^{*}$ och låt $\tau$ vara en kodning (det vill säga en ${\ displaystyle 1}$ -uniform morfism), som i det automatteoretiska fallet. Om $w$ är en fast punkt för $\varphi$ — det vill säga om $w=\varphi (w)$ — då ${ \displaystyle s=\tau (w)}$ är en k -automatisk sekvens. Omvänt kan varje k -automatisk sekvens erhållas på detta sätt. Detta resultat beror på Cobham , och det kallas i litteraturen Cobhams lilla teorem .

k -kärna

Låt k ≥ 2. K-kärnan i sekvensen s ( n ) är uppsättningen av undersekvenser

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

I de flesta fall är k -kärnan i en sekvens oändlig. Men om k -kärnan är finit så är sekvensen s ( n ) k -automatisk, och det omvända är också sant. Detta beror på Eilenberg.

Det följer att en k -automatisk sekvens nödvändigtvis är en sekvens på ett ändligt alfabet.

Formell maktserie

Låt u ( n ) vara en sekvens över ett alfabet Σ och antag att det finns en injektiv funktion β från Σ till det finita fältet F _q , där q = p ⁿ för något primtal p . Den tillhörande formella maktserien är

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

är sekvensen u q -automatisk om och endast om denna formella potensserie är algebraisk över F _q ( X ). Detta resultat beror på Christol, och det kallas i litteraturen för Christols teorem .

Historia

Automatiska sekvenser introducerades av Büchi 1960, även om hans uppsats tog en mer logisk-teoretisk inställning till saken och inte använde den terminologi som finns i denna artikel. Begreppet automatiska sekvenser studerades ytterligare av Cobham 1972, som kallade dessa sekvenser "uniforma tag-sekvenser ".

Termen "automatisk sekvens" dök först upp i en tidning av Deshouillers.

Exempel

Följande sekvenser är automatiska:

Thue–Morse-sekvensen

DFAO genererar Thue–Morse-sekvensen

₀ Thue –Morse-sekvensen t ( n ) ( OEIS : A010060 ) är den fasta punkten för morfismen 0 → 01, 1 → 10. Eftersom den n -te termen i Thue–Morse-sekvensen räknar antalet ettor modulo 2 i bas-2-representation av n , den genereras av den tvåtillståndsdeterministiska finita automaten med utdata som visas här, där att vara i tillstånd q indikerar att det finns ett jämnt antal ettor i representationen av n och att vara i tillstånd q ₁ indikerar att det finns ett udda antal ettor. Därför är Thue–Morse-sekvensen 2-automatisk.

Periodfördubblingssekvens

Den n: e termen i periodfördubblingssekvensen d ( n ) ( OEIS : A096268 ) bestäms av pariteten för exponenten för den högsta potensen av 2 som delar n . Det är också den fasta punkten för morfismen 0 → 01, 1 → 00. Börjar med den initiala termen w = 0 och itererar den 2-enhetliga morfismen φ på w där φ(0) = 01 och φ(1) = 00, det är uppenbart att periodfördubblingssekvensen är fixpunkten för φ( w ) och därför är den 2-automatisk.

Rudin–Shapiro-sekvensen

Den n: e termen i Rudin–Shapiro-sekvensen r ( n ) ( OEIS : A020985 ) bestäms av antalet på varandra följande ettor i bas-2-representationen av n . 2-kärnan i Rudin-Shapiro-sekvensen är

${\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}}$

Eftersom 2-kärnan endast består av r ( n ), r (2 n + 1), r (4 n + 3) och r (8 n + 3), är den ändlig och därför är Rudin–Shapiro-sekvensen 2 -automatisk.

Andra sekvenser

Både Baum–Sweet-sekvensen ( OEIS : A086747 ) och den vanliga pappersvikningssekvensen ( OEIS : A014577 ) är automatiska. Dessutom är den allmänna pappersvikningssekvensen med en periodisk vecksekvens också automatisk.

Egenskaper

Automatiska sekvenser uppvisar ett antal intressanta egenskaper. En icke uttömmande lista över dessa fastigheter presenteras nedan.

• Varje automatisk sekvens är ett morfiskt ord .
• För k ≥ 2 och r ≥ 1 är en sekvens k -automatisk om och endast om den är k ^r -automatisk. Detta resultat beror på Eilenberg.
• För h och k multiplikativt oberoende är en sekvens både h -automatisk och k -automatisk om och endast om den är ytterst periodisk. Detta resultat beror på Cobham även känd som Cobhams teorem , med en multidimensionell generalisering på grund av Semenov.
• Om u ( n ) är en k -automatisk sekvens över ett alfabet Σ och f är en enhetlig morfism från Σ ^∗ till ett annat alfabet Δ ^∗ , då är f ( u ) en k -automatisk sekvens över Δ.
• Om u ( n ) är en k -automatisk sekvens, så är sekvenserna u ( k ⁿ ) och u ( k ⁿ − 1) slutligen periodiska. Omvänt, om u ( n ) är en ytterst periodisk sekvens, då ^är sekvensen v definierad av v ( kn ) = u ( n ) och annars noll k -automatisk.

Bevisa och motbevisa automatik

Givet en kandidatsekvens ${\displaystyle s=(s_{n})_{n\geq 0}} ,$ är det vanligtvis lättare att motbevisa dess automatik än att bevisa den. Genom k ​​-kärnkarakteriseringen av k -automatiska sekvenser räcker det att producera oändligt många distinkta element i k -kärnan $K_{k}(s)$ för att visa att $s$ är inte k -automatisk. Heuristiskt kan man försöka bevisa automatik genom att kontrollera överensstämmelsen mellan termer i k -kärnan, men detta kan ibland leda till felaktiga gissningar. Till exempel, låt

$t=011010011\dots$

vara ordet Thue–Morse. Låt $s$ vara ordet som ges genom att sammanfoga på varandra följande termer i sekvensen av löplängder av $t$ . Sedan börjar $s$

$s=12112221\dots .$ .

Det är känt att $s$ är den fasta punkten $h^{\omega }(1)$ för morfismen

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

Ordet $s$ är inte 2-automatiskt, men vissa delar av dess 2-kärna överensstämmer för många termer. Till exempel, $s_{16n+1}=s_{64n+1}{\text{ för }}0\leq n\leq 1864134$

men inte för $n=1864135$ .

Med tanke på en sekvens som förmodas vara automatisk, finns det några användbara metoder för att bevisa att den faktiskt är det. Ett tillvägagångssätt är att direkt konstruera en deterministisk automat med utdata som ger sekvensen. Låt $(s_{n})_{n\geq 0}$ skrivet i alfabetet $\Delta$ , och låt $(n)_{ k}$ betecknar bas- $k$ expansionen av $n$ . Då är sekvensen $s=(s_{n})_{n\geq 0}$$\displaystyle k}$ { -automatisk om och bara var och en av fibrerna

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

är ett vanligt språk. Kontroll av fibrernas regelbundenhet kan ofta göras med hjälp av pumplemma för vanliga språk .

Om $s_{k}(n)$ summan av siffrorna i bas- $k$ expansionen av $n$ och $p (X)$ är ett polynom med icke-negativa heltalskoefficienter, och om $k\geq 2$ , $m\geq 1$ är heltal, då är sekvensen

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

är $k$ -automatisk om och endast om $\deg p\leq 1$ eller $m\mid k-1$ .

1-automatiska sekvenser

k -automatiska sekvenser definieras normalt endast för k ≥ 2. Begreppet kan utökas till k = 1 genom att definiera en 1-automatisk sekvens till att vara en sekvens vars n -te term beror på den unära notationen för n ; dvs (1) ⁿ . Eftersom en automat med ändligt tillstånd så småningom måste återgå till ett tidigare besökt tillstånd, är alla 1-automatiska sekvenser i slutändan periodiska.

Generaliseringar

Automatiska sekvenser är robusta mot variationer av antingen definitionen eller inmatningssekvensen. Till exempel, som noterats i den automatteoretiska definitionen, förblir en given sekvens automatisk under både direkt och omvänd läsning av inmatningssekvensen. En sekvens förblir också automatisk när en alternativ uppsättning siffror används eller när basen negeras; det vill säga när ingångssekvensen representeras i bas − k istället för i bas k . Men i motsats till att använda en alternativ uppsättning siffror, kan en förändring av basen påverka en sekvenss automatik.

Domänen för en automatisk sekvens kan utökas från de naturliga talen till heltal via tvåsidiga automatiska sekvenser. Detta härrör från det faktum att, givet k ≥ 2, kan varje heltal representeras unikt i formen $\sum _{0\leq i\leq r}a_ {i}(-k)^{i},$ där $a_{i}\in \{0,\dots ,k-1\}$ . Då är en tvåsidig oändlig sekvens a ( n )   _{n $\in \mathbb {Z}$} (− k )-automatisk om och endast om dess underföljder a ( n ) _{n ≥ 0} och a (− n ) _{n ≥ 0} är k -automatiska.

Alfabetet för en k -automatisk sekvens kan utökas från ändlig storlek till oändlig storlek via k -regelbundna sekvenser . De k -reguljära sekvenserna kan karakteriseras som de sekvenser vars k -kärna är ändligt genererad. Varje avgränsad k -regelbunden sekvens är automatisk.

Logiskt förhållningssätt

För många 2-automatiska sekvenser $s=(s_{n})_{n\geq 0}$ , kartan $n\mapsto s_{n}$ har egenskapen att första ordningens teori ${\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})$ är avgörbart . Eftersom många icke-triviala egenskaper hos automatiska sekvenser kan skrivas i första ordningens logik, är det möjligt att bevisa dessa egenskaper mekaniskt genom att utföra beslutsproceduren.

Till exempel kan följande egenskaper hos Thue–Morse-ordet alla verifieras mekaniskt på detta sätt:

• Thue–Morse-ordet är överlappsfritt, dvs det innehåller inte ett ord av formen $cxcxc$ där $c$ är en enkel bokstav och $w$ är ett möjligen tomt ord.
• Ett icke-tomt ord $x$ är kantat om det finns ett icke-tomt ord $w$ och ett möjligen tomt ord $y$ med $x=wyw$ . Thue–Morse-ordet innehåller en kantad faktor för varje längd som är större än 1.
• Det finns en obegränsad faktor av längd $n$ i Thue–Morse-ordet om och endast om $(n)_{2}\notin 1 (01^{*}0)^{*}10^{*}1$ där $(n)_{2}$ anger den binära representationen av $n$ .

Mjukvaran Walnut, utvecklad av Hamoon Mousavi, implementerar en beslutsprocedur för att bestämma många egenskaper hos vissa automatiska ord, som Thue–Morse-ordet. Denna implementering är en konsekvens av ovanstående arbete med det logiska förhållningssättet till automatiska sekvenser.

Se även

• Buchi aritmetik

Anteckningar

•    Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatiska sekvenser: teori, tillämpningar, generaliseringar . Cambridge University Press . ISBN 978-0-521-82332-6 . Zbl 1086.11015 .
•    Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Kombinatorik på ord. Christoffels ord och upprepningar i ord . CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society . ISBN 978-0-8218-4480-9 . Zbl 1161.68043 .
•    Berstel, Jean; Reutenauer, Christophe (2011). Icke-kommutativa rationella serier med tillämpningar . Encyclopedia of Mathematics och dess tillämpningar. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0 . Zbl 1250.68007 .
•   Cobham, Alan (1972). "Enhetliga taggsekvenser". Matematisk systemteori . 6 (1–2): 164–192. doi : 10.1007/BF01706087 . S2CID 28356747 .
•    Lothaire, M. (2005). Tillämpad kombinatorik på ord . Encyclopedia of Mathematics och dess tillämpningar. Vol. 105. Ett kollektivt verk av 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 Schaffer Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche och Valérie Berthé . Cambridge: Cambridge University Press . ISBN 978-0-521-84802-2 . Zbl 1133.68067 .
•    Pytheas Fogg, N. (2002). Substitutioner i dynamik, aritmetik och kombinatorik . Föreläsningsanteckningar i matematik. Vol. 1794. Redaktörer Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag . ISBN 978-3-540-44141-0 . Zbl 1014.11015 .

Vidare läsning

•    Berthé, Valérie; Rigo, Michel, red. (2010). Kombinatorik, automater och talteori . Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9 . Zbl 1197.68006 .
•    Loxton, JH (1988). "13. Automater och transcendens". I Baker, A. (red.). Nya framsteg inom transcendensteori . Cambridge University Press . s. 215 -228. ISBN 978-0-521-33545-4 . Zbl 0656.10032 .
• Rowland, Eric (2015). "Vad är ... en automatisk sekvens?" . Meddelanden från American Mathematical Society . 62 (3): 274–276. doi : 10.1090/noti1218 .
•   Shallit, Jeffrey (1999). "Sifferteori och formella språk". I Hejhal, Dennis A. ; Friedman, Joel; Gutzwiller, Martin C .; Odlyzko, Andrew M. (red.). Nya tillämpningar av talteori. Baserat på handlingar från IMA sommarprogrammet, Minneapolis, MN, USA, 15–26 juli 1996 . IMA-volymerna i matematik och dess tillämpningar. Vol. 109. Springer-Verlag . s. 547–570. ISBN 978-0-387-98824-5 .