State Complexity of Shifts of the Fibonacci Word

Titolo: Complessità degli Stati degli Spostamenti della Parola di Fibonacci

1. Il Problema

Il paper affronta un problema fondamentale nella teoria della complessità descrittiva e nelle sequenze automatiche: determinare la complessità degli stati (il numero minimo di stati necessari) di un Automato Finito Deterministico con Uscita (DFAO) che genera una sequenza spostata.

Nello specifico, gli autori studiano la parola di Fibonacci infinita $f = (f_i)_{i \ge 0} = 01001010\dots$. Dato un intero $c \ge 0$, si considera la sequenza spostata $(f_{i+c})_{i \ge 0}$. L'obiettivo è calcolare quanti stati sono necessari per un automa che, dato l'indice $i$ in una specifica numerazione, produca il termine $f_{i+c}$.

Il lavoro analizza due varianti di input:

1. Lsd-first (Least Significant Digit first): Lettura delle cifre dalla meno significativa alla più significativa (rappresentazione di Zeckendorf).
2. Msd-first (Most Significant Digit first): Lettura delle cifre dalla più significativa alla meno significativa.

Mentre per le sequenze automatiche in base $k$ standard, lo spostamento comporta spesso una complessità lineare o superiore, il caso della parola di Fibonacci (che utilizza la rappresentazione di Zeckendorf basata sui numeri di Fibonacci) presenta sfide uniche, in quanto non esiste un trasduttore deterministico a un solo passaggio per l'addizione in questo sistema di numerazione.

2. Metodologia

Gli autori combinano tecniche di complessità degli stati, approssimazione diofantea e logica formale.

• Rappresentazione di Zeckendorf: Utilizzano la rappresentazione unica dei numeri naturali come somma di numeri di Fibonacci non consecutivi. Estendono questo sistema per rappresentare anche numeri negativi, definendo una notazione specifica per $-n$ basata su $-F_k + \dots$.
• Analisi Geometrica e Diofantea: Sfruttano una caratterizzazione fondamentale della parola di Fibonacci basata sulle parti frazionarie. La $i$-esima bit è 1 se e solo se $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$, dove $\phi$ è il rapporto aureo.
  • Per la sequenza spostata, la condizione diventa: $f(i+c) = 1 \iff \{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$.
• Partizioni dell'Intervallo $[0, 1)$:
  • Caso Lsd-first: Costruiscono una partizione dell'intervallo $[0, 1)$ indotta dai primi $d$ bit della rappresentazione di Zeckendorf. Dimostrano che i bit a bassa significatività di $n$ determinano in quale sottointervallo cade $\{n\phi\}$. L'automata costruisce stati corrispondenti a questi intervalli finché non si raggiunge una "stato assorbente" (sink state) quando l'intervallo è completamente contenuto nella regione di output desiderata.
  • Caso Msd-first: Definiscono una partizione consistente con la rappresentazione msd-first, basata sugli estremi generati dalle rappresentazioni di $-(c+1)$ e $-(c+2)$ nei numeri di Fibonacci negativi. Utilizzano il fatto che aggiungere un bit a destra nella rappresentazione di Zeckendorf corrisponde a una trasformazione specifica degli intervalli delle parti frazionarie.
• Verifica Automatica: Una parte significativa delle dimostrazioni (in particolare le proprietà delle partizioni e le relazioni tra intervalli) è stata verificata rigorosamente utilizzando il dimostratore di teoremi automatizzato Walnut, che lavora con la logica del primo ordine sulle sequenze automatiche.

3. Risultati Chiave

Teorema Principale (Complessità Logaritmica)

Il risultato centrale del paper è che la complessità degli stati per generare la sequenza spostata $(f_{i+c})$ è $O(\log c)$ sia per l'input lsd-first che per l'input msd-first.

• Caso Lsd-first (Teorema 1): Viene costruita esplicitamente un'automata con $O(\log c)$ stati. La prova mostra che dopo aver letto circa $k$ cifre (dove $F_k \approx c$), l'automata può determinare definitivamente se l'indice cade nella regione di output corretta, entrando in uno stato assorbente.
  • Viene fornita una formula esatta per il numero minimo di stati: $2(|(c)_F| + 1) + 1 - g(c)$, dove $|(c)_F|$ è la lunghezza della rappresentazione di Zeckendorf di $c$ e $g(c)$ è una funzione che dipende dai valori di $f(c-1)$ e $f(c-2)$.
• Caso Msd-first (Teorema 3): Nonostante la difficoltà di invertire le transizioni (che normalmente porterebbe a un'esplosione esponenziale di stati), gli autori dimostrano che è possibile costruire un DFAO con $O(\log c)$ stati. La costruzione si basa sulla partizione $P$ generata combinando gli estremi delle partizioni associate a $-(c+1)$ e $-(c+2)$.

Ottimalità

Il risultato è quasi ottimale dal punto di vista informativo. Per una sequenza aperiodica, una crescita logaritmica è vicina al limite inferiore teorico per l'aumento di complessità dovuto a uno spostamento.

4. Contributi Tecnici

1. Estensione della Rappresentazione di Zeckendorf: Introduzione di un sistema di rappresentazione coerente per i numeri negativi necessario per analizzare gli spostamenti nel contesto msd-first.
2. Costruzione di Partizioni Consistenti: Definizione di partizioni dell'intervallo unitario che sono "consistenti" con la struttura della rappresentazione di Zeckendorf, permettendo di mappare le transizioni dell'automata su operazioni geometriche sugli intervalli.
3. Integrazione di Strumenti Automatici: Uso efficace di Walnut per provare le proprietà combinatorie complesse delle partizioni, garantendo la correttezza dei passaggi tecnici più intricati.
4. Contrasto con Altri Sistemi: Dimostrazione che, a differenza di altre sequenze automatiche (come la sequenza di Thue-Morse in base 10 dove lo spostamento può richiedere $O(c)$ stati), la struttura specifica della parola di Fibonacci permette una compressione molto efficiente.

5. Significato e Implicazioni

• Teoria delle Sequenze Automatiche: Il lavoro chiarisce come la struttura aritmetica sottostante (in questo caso, i numeri di Fibonacci e il rapporto aureo) influenzi drasticamente la complessità descrittiva delle operazioni di spostamento.
• Efficienza Computazionale: Stabilisce che le sequenze basate su Fibonacci sono "facili" da spostare in termini di risorse computazionali (stati dell'automata), il che è rilevante per l'elaborazione di segnali e la generazione di sequenze pseudocasuali.
• Generalizzazioni: Gli autori suggeriscono che questi risultati potrebbero essere generalizzati ad altri irrazionali quadratici e a parole come quella di Tribonacci, aprendo nuove direzioni di ricerca all'intersezione tra teoria dei numeri, combinatoria sulle parole e teoria degli automi.

In sintesi, il paper risolve elegantemente un problema aperto sulla complessità degli spostamenti della parola di Fibonacci, dimostrando che, nonostante la natura aperiodica e la complessità della rappresentazione di Zeckendorf, la complessità degli stati cresce solo logaritmicamente rispetto alla grandezza dello spostamento.