State Complexity of Shifts of the Fibonacci Word

Resumo Técnico: Complexidade de Estados de Deslocamentos da Palavra de Fibonacci

1. Problema Investigado

O artigo aborda a complexidade de estados (state complexity) de sequências automáticas, especificamente focando na operação de deslocamento (shifting) da famosa Palavra de Fibonacci ($f$).

• Objetivo: Determinar o tamanho do autômato finito determinístico com saída (DFAO) mínimo necessário para gerar a sequência deslocada $(f(i+c))_{i \ge 0}$, onde $c$ é um inteiro fixo e $f$ é a palavra de Fibonacci infinita.
• Contexto: A palavra de Fibonacci é um objeto central na combinatória sobre palavras e é gerada por um DFAO simples (5 estados para entrada LSD-first, 2 estados para MSD-first). O problema é entender como a complexidade cresce quando a sequência é deslocada por $c$ posições.
• Desafio Específico: Em sistemas de numeração padrão (como base $k$), o deslocamento pode ser tratado com transdutores, resultando em complexidade $O(m \log c)$. No entanto, para a representação de Zeckendorf (base Fibonacci), não existe um transdutor determinístico de uma única passagem para realizar adição, tornando a análise mais complexa. Além disso, o comportamento pode diferir drasticamente entre leitura LSD-first (menos significativo primeiro) e MSD-first (mais significativo primeiro).

2. Metodologia

Os autores utilizam uma abordagem híbrida combinando Teoria da Complexidade de Estados, Aproximação Diofantina e Lógica Formal.

• Definição da Palavra de Fibonacci: A palavra $f$ é definida de várias formas equivalentes, sendo crucial para a prova a definição baseada em partes fracionárias: $f(i) = 1$ se e somente se $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$, onde $\phi$ é a razão áurea.
• Representação de Zeckendorf: O trabalho utiliza a representação de números naturais como somas de Fibonacci não consecutivas. Para lidar com o deslocamento $i+c$, os autores desenvolvem uma representação estendida para números negativos usando dígitos $\{-1, 0, 1\}$.
• Partição do Intervalo $[0, 1)$:
  • Caso LSD-first: Os autores definem uma partição do intervalo unitário baseada nos bits de baixa ordem da representação de Zeckendorf. Eles demonstram que os bits inferiores de $n$ determinam em qual intervalo de uma partição específica o ponto $\{n\phi\}$ reside.
  • Caso MSD-first: Introduzem uma partição consistente com a representação MSD-first, baseada em pontos de extremidade derivados de inteiros negativos ($r_k$), garantindo que a transição de estados preserve a consistência da partição ao ler dígitos da esquerda para a direita.
• Prova Automatizada: Parte das demonstrações técnicas, especialmente as lemas sobre o comportamento das partes fracionárias sob operações de adição e remoção de dígitos, foi verificada usando o provador de teoremas automatizado Walnut, que opera sobre lógica de primeira ordem para sequências automáticas.

3. Principais Resultados e Contribuições

O artigo estabelece resultados fundamentais sobre a complexidade de estados para deslocamentos da palavra de Fibonacci:

• Teorema 1 (Caso LSD-first): Para qualquer deslocamento $c \ge 0$, existe um DFAO LSD-first que gera $(f(i+c))_{i \ge 0}$ com $O(\log c)$ estados.

  • Mecanismo: O autômato lê os dígitos de Zeckendorf de baixo para cima. Após ler aproximadamente $k$ dígitos (onde $F_k \approx c$), o autômato determina em qual intervalo da partição o valor $\{n\phi\}$ se encontra e entra em um estado "sorvedouro" (sink state) que produz a saída correta para todos os dígitos subsequentes.
  • Fórmula Exata: O número mínimo de estados é dado por $2(|(c)_F| + 1) + 1 - g(c)$, onde $|(c)_F|$ é o comprimento da representação de Zeckendorf de $c$ e $g(c)$ depende dos valores de $f(c-1)$ e $f(c-2)$.

• Teorema 3 (Caso MSD-first): Para qualquer deslocamento $c \ge 0$, existe um DFAO MSD-first que gera $(f(i+c))_{i \ge 0}$ com $O(\log c)$ estados.

  • Mecanismo: Ao contrário de outras sequências (como a sequência de Thue-Morse, onde o deslocamento MSD-first pode exigir $O(c)$ estados), a estrutura da palavra de Fibonacci permite uma partição consistente que cresce apenas logaritmicamente com $c$. A construção utiliza a partição $P$ combinada das extremidades de $P(-(c+1))$ e $P(-(c+2))$.

• Ótimo Assintótico: O resultado de $O(\log c)$ é próximo do mínimo teórico possível para sequências não periódicas. Argumentos de contagem mostram que, para sequências automáticas aperiódicas, a complexidade deve exceder $\Omega(\frac{\log c}{\log \log c})$ infinitas vezes. Portanto, o crescimento logarítmico encontrado é quase o menor crescimento possível ("blow-up").

4. Significado e Implicações

• Raridade de Crescimento Logarítmico: O artigo destaca que o crescimento logarítmico de complexidade para deslocamentos é raro. A maioria das sequências automáticas (como Thue-Morse) apresenta crescimento linear ou super-linear no caso MSD-first. A Palavra de Fibonacci é um caso especial onde a estrutura geométrica (relacionada à razão áurea e aproximações diofantinas) permite uma compressão eficiente mesmo após o deslocamento.
• Generalizações: Os autores sugerem que esses resultados podem ser generalizados para outras irracionalidades quadráticas e, potencialmente, para números irracionais mais gerais, abrindo caminho para futuras pesquisas na interseção entre teoria da linguagem formal, combinatória de palavras e teoria dos números.
• Ferramentas Computacionais: O uso bem-sucedido do provador Walnut para verificar propriedades complexas de sequências automáticas reforça a utilidade de métodos de prova automatizada nesta área.

Conclusão

O trabalho demonstra que, apesar da dificuldade inerente à adição na representação de Zeckendorf, a complexidade de estados para deslocar a Palavra de Fibonacci é surpreendentemente baixa ($O(\log c)$) tanto para entrada MSD-first quanto LSD-first. Isso contrasta fortemente com outros exemplos famosos e sugere propriedades estruturais únicas da palavra de Fibonacci que permitem uma representação automata muito eficiente mesmo após transformações aritméticas.