PROFILPELAJAR.COM

Uma sequência automática (ou k-sequência automática) é uma sequência infinita de termos caracterizado por um autômato finito. O enésimo termo da sequência é um mapeamento do estado final do autômato quando a sua entrada de n dígitos tem como base um valor fixo k. ^[1]^[2] Um conjunto k-automático é um conjunto não negativo de inteiros no qual cada sequência de valores é uma sequência automática de uma função característica, ou seja, um conjunto n da sequência pode ser determinado por um autômato finito de dígitos n na base k.^[3]^[4]

Um autômato lendo dígitos de base k a partir da mais significante é chamado de leitura direta, e uma leitura a partir do menos significante é chamada de leitura reversa.^[4] No entanto as duas direções conduzem a mais classes de sequências.^[5]

Cada sequência automática é uma palavra mórfica.

Ponto de vista do autômato

Seja k um número inteiro positivo e D = (E, φ, e) seja um autômato determinístico onde

E é um conjunto finito de estados
φ : E×[0,k − 1] → E é um estado de transição
$e\in E$ é o estado inicial

E também seja A um conjunto finito, e π:E → A uma projeção em A. Estenda a função de transição φ de atuando em dígitos únicos para atuando em “string” de dígitos, definindo a ação de φ em uma string s de forma s₁s₂...s_t como:

Defina a função m a partir de um conjunto positivo de inteiro para o conjunto A na forma:

m(n)=\pi (\phi (e,s(n)))\,,

Onde, s(n) é n escrito na base k. Então a sequência m = m(1)m(2)m(3)... é chamada de uma k-sequência automática.

Substituição de pontos de vista

Seja σ um k-morfismo uniforme de monoide livre E^∗ , então $\sigma (E)\subseteq E^{k}$ e no qual é prolongável para $e\in E$ ,^[6] ou seja, σ(e) começa com e. Seja A e π definido como acima. Então se w é um ponto fixo de σ, ou seja, w = σ(w), então m = π(w) é uma k-sequência automática sobre A^[7]: esse é o teorema de Cobham.^[2] Reciprocamente toda k-sequência automática é obtida desse modo.^[4]

Dizimação

Para um k fixo e k > 1. Para uma sequência w, definimos uma k-dizimação de w para r=0,1,...,k-1 sendo uma subsequência consistindo em letras das posições congruentes a r mod k. O kernel da dizimação de w consiste em um conjunto de palavras obtidas por todas as possíveis dizimações repetições de w. Uma sequência é k-automática se, e somete se, o kernel da k-dizimação for finito.^[8]^[9]^[10]

1-sequência automática

k-sequências automáticas são normalmente definidas apenas para k ≥ 2.^[1] O conceito pode ser estendido para k = 1 definido uma 1-sequência automática sendo uma sequências na qual o enésimo termo depende da notação unária para n, que é (1)ⁿ. Como um autômato finito tem que retornar eventualmente para um estado já visitado, todas as 1-sequências automáticas são eventualmente periódicas.

Propriedades

Para uma dado k e r, um conjunto é k-automático se, e somente se, for k^r-automático. Caso contrario, para h e k multiplicável independentemente, então um conjunto é h-automático e k-automático se, e somente se, for 1-automático, ou seja, for fundamentalmente periódico.^[11]

Se u(n) é uma sequência k-automática então a sequência u(kⁿ) e u(kⁿ−1) são fundamentalmente periódicas.^[12] Reciprocamente, se v(n) é fundamentalmente periódica então uma sequência u definida por u(kⁿ) = v(n)) e caso contrário 0, é k-automática.^[13]

Seja u(n) uma sequência k-automática sobre o alfabeto A. Se f é um morfismo uniforme de A^∗ para B^∗ então a palavra f(u) é uma k-sequência automática sobre o alfabeto B.^[14]

Seja u(n) uma sequência sobre o alfabeto A e supondo que há uma função injetiva j de A para uma área finita F_q. Então a serie formal de potências associadas é : : $f_{u}(z)=\sum _{n}j(u(n))z^{n}\ .$

A sequência u é q-automática se, e somente se, a serie de potencias f_u for algébrica sobre o campo das funções racionais F_q(z).

Exemplos

As seguintes sequências são automáticas:

Sequência de Thue-Morse: Seja E = A = {0, 1}, e = 0, π = id e σ da forma que σ(0) = 01, σ(1) = 10; Pegando o ponto fixo 01101001100101101001011001101001..., que é de fato a palavras de Thue-Morse. O enésimo termo é a paridade da representação da base 2 de n e a sequência é 2-automática.^[1]^[2]^[15]^[16] O 2-kernel consiste na própria sequência e seu complemento.^[17] A serie de potencias associada T(z) satisfaz :: $(1+z)^{3}T^{2}+(1+z)^{2}T+z=0\$ sobre o campo F₂(z).^[18]
Sequência de Rudin–Shapiro^[15]^[19]
Sequência de Baum–Sweet^[20]
Sequência regular de dobragem de papel^[16]^[21]^[22] e a genérica sequência de dobragem de papel com uma sequência periódica de dobras.^[23]
A sequência de duplicação periódica, definida pela paridade das potencias de 2 dividindo por n; e o ponto fixo do morfismo 0 → 01, 1 → 00.^[24]

Número real automático

Um número real automático é um numero real no qual a expansão da base b é uma sequência automática.^[25]^[26] Tais números são racionais ou transcendentais, mas não são números-U. Números racionais são k-automáticos na base b para todo k e b.

References

↑ ^a ^b ^c Allouche & Shallit (2003) p.152
↑ ^a ^b ^c Berstel et al (2009) p.78
↑ Allouche & Shallit (2003) p.168
↑ ^a ^b ^c Pytheas Fogg (2002) p.13
↑ Pytheas Fogg (2002) p.15
↑ Allouche & Shallit (2003) p.212
↑ Allouche & Shallit (2003) p.175
↑ Allouche & Shallitt (2003) p.185
↑ Lothaire (2005) p.527
↑ Berstel & Reutenauer (2011) p.91
↑ Allouche & Shallit (2003) pp.345-350
↑ Lothaire (2005) p.529
↑ Berstel & Reutenauer (2011) p.103
↑ Lothaire (2005) p.532
↑ ^a ^b Lothaire (2005) p.525
↑ ^a ^b Berstel & Reutenauer (2011) p.92
↑ Lothaire (2005) p.528
↑ Berstel & Reutenauer (2011) p.94
↑ Allouche & Shallit (2003) p.154
↑ Allouche & Shallit (2003) p.156
↑ Allouche & Shallit (2003) p.155
↑ Lothaire (2005) p.526
↑ Allouche & Shallit (2003) p.183
↑ Allouche & Shallit (2003) p.176
↑ Shallitt (1999) p.556
↑ Allouche & Shallit (2003) p.379

Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. [S.l.]: 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. Col: CRM Monograph Series. 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. Col: Encyclopedia of Mathematics and Its Applications. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007
Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Col: Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006
Shallit, Jeffrey (1999). «Number theory and formal languages». In: Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15--26, 1996. Col: The IMA volumes in mathematics and its applications. 109. [S.l.]: Springer-Verlag. pp. 547–570. ISBN 0-387-98824-6
Lothaire, M. (2005). Applied combinatorics on words. Col: Encyclopedia of Mathematics and Its Applications. 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 0-521-84802-4. Zbl 1133.68067
Loxton, J. H. (1988). «13. Automata and transcendence». In: Baker, A. New Advances in Transcendence Theory. [S.l.]: Cambridge University Press. pp. 215–228. ISBN 0-521-33545-0. Zbl 0656.10032
Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Col: Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015

[as1-1] Allouche & Shallit (2003) p.152

[BLRS78-2] Berstel et al (2009) p.78

[3] Allouche & Shallit (2003) p.168

[PF13-4] Pytheas Fogg (2002) p.13

[PF15-5] Pytheas Fogg (2002) p.15

[AS212-6] Allouche & Shallit (2003) p.212

[AS175-7] Allouche & Shallit (2003) p.175

[AS185-8] Allouche & Shallitt (2003) p.185

[ApCOw527-9] Lothaire (2005) p.527

[BR91-10] Berstel & Reutenauer (2011) p.91

[as345-11] Allouche & Shallit (2003) pp.345-350

[ApCoW529-12] Lothaire (2005) p.529

[BR103-13] Berstel & Reutenauer (2011) p.103

[ApCoW532-14] Lothaire (2005) p.532

[LotIII525-15] Lothaire (2005) p.525

[BR92-16] Berstel & Reutenauer (2011) p.92

[ApCoW528-17] Lothaire (2005) p.528

[BR94-18] Berstel & Reutenauer (2011) p.94

[AS154-19] Allouche & Shallit (2003) p.154

[AS156-20] Allouche & Shallit (2003) p.156

[AS155-21] Allouche & Shallit (2003) p.155

[LotIII526-22] Lothaire (2005) p.526

[AS183-23] Allouche & Shallit (2003) p.183

[AS176-24] Allouche & Shallit (2003) p.176

[hejhal556-25] Shallitt (1999) p.556

[AS379-26] Allouche & Shallit (2003) p.379

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

PROFILPELAJAR.COM

Sequência automática

Ponto de vista do autômato

Substituição de pontos de vista

Dizimação

1-sequência automática

Propriedades

Exemplos

Número real automático

References

Read other articles:

Drew Binsky

Luigi Gonzaga

Eksarkat Apostolik Khadki

Feza Gürsey

Agostino Casaroli

Pontefract

Huang Gai

Turistas

趙家驤

Dash

Ruff (clothing)

1810 en musique classique

ソー (オー＝ド＝セーヌ県)

Gothic and Vandal warfare

Rainie Cross

Bal Mabille

1994 United States Senate election in Washington

Assemblée de Londres

Fußballclub Hansa Rostock 1999-2000

Coliseum Burgos