Sequência automática

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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 π:EA 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 s1s2...st 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[editar | editar código-fonte]

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 A7 : esse é o teorema de Cobham2 . Reciprocamente toda k-sequência automática é obtida desse modo4 .

Dizimação[editar | editar código-fonte]

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[editar | editar código-fonte]

k-sequências automáticas são normalmente definidas apenas para k ≥ 21 . 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)n. 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[editar | editar código-fonte]

Para uma dado k e r, um conjunto é k-automático se, e somente se, for kr-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ódico11 .

Se u(n) é uma sequência k-automática então a sequência u(kn) e u(kn−1) são fundamentalmente periódicas12 . Reciprocamente, se v(n) é fundamentalmente periódica então uma sequência u definida por u(kn) = 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 B14 .

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 Fq. 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 fu for algébrica sobre o campo das funções racionais Fq(z).

Exemplos[editar | editar código-fonte]

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ática1 2 15 16 . O 2-kernel consiste na própria sequência e seu complemento17 . A serie de potencias associada T(z) satisfaz :: (1+z)^3 T^2 + (1+z)^2 T + z = 0 \ sobre o campo F2(z)18 .
  • Sequência de Rudin–Shapiro15 19
  • Sequência de Baum–Sweet20
  • Sequência regular de dobragem de papel16 21 22 e a genérica sequência de dobragem de papel com uma sequência periódica de dobras23 .
  • 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 → 0024 .

Número real automático[editar | editar código-fonte]

Um número real automático é um numero real no qual a expansão da base b é uma sequência automática25 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[editar | editar código-fonte]

  1. a b c Allouche & Shallit (2003) p.152
  2. a b c Berstel et al (2009) p.78
  3. Allouche & Shallit (2003) p.168
  4. a b c Pytheas Fogg (2002) p.13
  5. Pytheas Fogg (2002) p.15
  6. Allouche & Shallit (2003) p.212
  7. Allouche & Shallit (2003) p.175
  8. Allouche & Shallitt (2003) p.185
  9. Lothaire (2005) p.527
  10. Berstel & Reutenauer (2011) p.91
  11. Allouche & Shallit (2003) pp.345-350
  12. Lothaire (2005) p.529
  13. Berstel & Reutenauer (2011) p.103
  14. Lothaire (2005) p.532
  15. a b Lothaire (2005) p.525
  16. a b Berstel & Reutenauer (2011) p.92
  17. Lothaire (2005) p.528
  18. Berstel & Reutenauer (2011) p.94
  19. Allouche & Shallit (2003) p.154
  20. Allouche & Shallit (2003) p.156
  21. Allouche & Shallit (2003) p.155
  22. Lothaire (2005) p.526
  23. Allouche & Shallit (2003) p.183
  24. Allouche & Shallit (2003) p.176
  25. Shallitt (1999) p.556
  26. Allouche & Shallit (2003) p.379