Complexity of Linear Subsequences of $k$-Automatic Sequences

Dit artikel onderzoekt de toestandcomplexiteit van lineaire deelrijen en basisoperaties op $k$-automatische rijen, legt een verband met de subwoordcomplexiteit en beantwoordt een recente vraag van Zantema en Bosma over het meest-significant-digit-first-formaat.

De kern

De Automatische Toekomst: Een Reis door Getallen, Robots en Patroonjagers

Stel je voor dat je een gigantische, oneindige rij van getallen hebt, zoals een lange trein die nooit stopt. In de wiskunde noemen we dit een sequentie. Sommige van deze treinen zijn heel simpel en voorspelbaar (zoals 1, 2, 3, 4...), maar andere zijn als een mysterieuze code die lijkt te willekeurig te zijn, maar toch een diep verborgen regelmaat volgt. Wiskundigen noemen deze "automatische sequenties".

Deze paper, geschreven door drie onderzoekers, gaat over het bouwen van robots (in de wiskunde: automata) die deze getallenrijen kunnen lezen, begrijpen en zelfs veranderen. Het is alsof je een machine bouwt die een boek in een vreemde taal kan lezen en er een samenvatting van maakt, of een nieuw hoofdstuk in dezelfde stijl schrijft.

Hier is wat ze hebben ontdekt, vertaald in alledaags taal:

1. De Robots en hun "Geheugen"

Stel je een robot voor die een getal leest, bijvoorbeeld het getal 43. Hij leest dit niet als "veertig-drie", maar als een rijtje cijfers in een ander talstelsel (zoals binair: 101011).

• De taak: De robot moet beslissen of een bepaalde regel klopt. Bijvoorbeeld: "Is het getal links plus het getal in het midden gelijk aan het getal rechts?"
• De uitdaging: Hoe groot moet het geheugen (het aantal 'kamers' of toestanden) van deze robot zijn om dit te doen?
  • Voor het optellen van twee getallen is de robot heel slim en heeft hij maar 2 kamers nodig. Hij onthoudt gewoon of er een 'overdracht' (een 'carry') is naar het volgende cijfer.
  • Maar wat als je een vast getal (bijvoorbeeld 1000) optelt bij een willekeurig getal? Dan moet de robot onthouden hoe ver hij al is in het getal 1000. Hoe groter dat vaste getal, hoe meer kamers hij nodig heeft. De onderzoekers hebben precies uitgerekend hoeveel kamers nodig zijn, afhankelijk van hoe groot dat vaste getal is.

2. Het "Sneeuwkristal" van de Getallenrij

Een van de coolste ontdekkingen in dit paper gaat over het nemen van een subsequentie.
Stel je voor dat je een lange rij getallen hebt: $h(0), h(1), h(2), h(3), h(4), h(5)...$
Nu vraag je je af: "Wat gebeurt er als ik alleen de getallen neem op de plekken 0, 2, 4, 6... (elke tweede)?" Of misschien op 0, 3, 6, 9... (elke derde)?

• De vraag: Als de oorspronkelijke rij een robot met 10 kamers nodig had, hoeveel kamers heeft de nieuwe, versnilde rij dan nodig?
• De verrassende ontdekking: De onderzoekers vonden een directe link tussen de grootte van de robot en de complexiteit van de patronen in de rij.
  • Denk aan een muur met bakstenen. Als je een patroon van bakstenen bekijkt, kun je tellen hoeveel unieke blokken van 3 bakstenen er in de muur voorkomen.
  • Ze ontdekten dat de grootte van de robot voor de nieuwe rij (bijvoorbeeld elke 3e steen) precies samenhangt met het aantal unieke blokken van een bepaalde lengte in de oorspronkelijke muur.
  • Dit is als het vinden van een sleutel: als je weet hoe complex de patronen zijn in de originele rij, weet je precies hoe groot de robot moet zijn voor de nieuwe rij. Ze hebben hiermee een vraag opgelost die eerder door anderen (Zantema en Bosma) als onoplosbaar werd gezien.

3. De "Thue-Morse" Magie

Een beroemd voorbeeld van zo'n getallenrij is de Thue-Morse-sequentie. Deze rij is bekend om zijn perfecte balans tussen chaos en orde; hij bevat nooit drie dezelfde stukken achter elkaar.
De onderzoekers hebben deze specifieke rij onder de loep genomen. Ze hebben uitgerekend:

• Hoeveel kamers de robot nodig heeft als je elke $n$-de steen pakt.
• Hoeveel kamers nodig zijn als je de rij een stukje opschuift (bijvoorbeeld beginnen bij $i+100$ in plaats van $i$).
• Ze vonden dat voor het opschuiven van de rij, de robot soms heel groot moet worden, maar dat er een ondergrens is: hij kan niet zomaar klein blijven. Het is alsof je een puzzel opschuift; soms moet je de doos groter maken om de nieuwe vorm te bevatten.

4. De Rekenmachine in de Wolken (Büchi-aritmetiek)

Tot slot kijken ze naar de snelheid. Hoe lang duurt het om deze robots te bouwen met behulp van software (zoals een programma genaamd Walnut)?

• Ze vergelijken dit met het bouwen van een huis. Je kunt het huis zelf bouwen (de minimale robot), maar je kunt ook een bouwbedrijf inhuren dat een generieke methode gebruikt.
• De onderzoekers hebben berekend hoe lang het duurt voordat de bouwplannen (de automaten) klaar zijn voor complexe taken, zoals vermenigvuldigen of het optellen van een groot getal. Ze vonden dat het bouwen van deze robots voor grote getallen heel snel gaat (polynomiale tijd), wat betekent dat computers dit probleem goed aankunnen, zelfs voor grote getallen.

Samenvattend

Dit paper is als een handleiding voor het bouwen van slimme robots die getallenrijen lezen.

1. Ze hebben de minimale grootte van deze robots bepaald voor basisrekenen.
2. Ze hebben een nieuwe wet ontdekt die de grootte van een robot voor een "versnilde" rij koppelt aan de complexiteit van patronen in de originele rij.
3. Ze hebben bewezen dat dit allemaal snel te berekenen is voor computers.

Het is een stukje wiskunde dat laat zien hoe we complexe patronen in getallen kunnen doorgronden, met als doel om betere software te bouwen die deze patronen kan herkennen en gebruiken. Het is de brug tussen abstracte wiskunde en de computers van morgen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Complexity of Linear Subsequences of k-Automatic Sequences" van Delaram Moradi, Narad Rampersad en Jeffrey Shallit, in het Nederlands.

Titel: Complexiteit van Lineaire Subsequenties van k-Automatische Sequenties

Auteurs: Delaram Moradi, Narad Rampersad, Jeffrey Shallit
Instituut: Universiteit van Waterloo en Universiteit van Winnipeg
Datum: 10 maart 2026

---

1. Probleemstelling

Het artikel richt zich op de toestandscomplexiteit (state complexity) van automata die specifieke talen en automatische sequenties herkennen. De auteurs onderzoeken hoe de grootte van een minimale deterministische eindige automaat met output (DFAO) verandert bij het uitvoeren van basisoperaties op $k$-automatische sequenties, met name:

• Het herkennen van rekenkundige relaties (zoals optelling en vermenigvuldiging) in basis $k$.
• Het genereren van lineaire subsequenties van de vorm $(h(ni + c))_{i \geq 0}$, waarbij $h$ een $k$-automatische sequentie is en $n, c$ constante gehele getallen zijn.
• Het analyseren van de complexiteit van deze operaties voor zowel MSD-first (meest significante cijfer eerst) als LSD-first (minst significante cijfer eerst) invoerformaten.

Een specifiek open probleem dat wordt aangepakt, is de vraag van Zantema en Bosma over de toestandscomplexiteit van lineaire subsequenties bij MSD-first invoer, waarvoor tot nu toe geen scherpe bovengrens bekend was.

2. Methodologie

De auteurs combineren methoden uit de theorie van formele talen, automata en getaltheorie:

• Constructie van Automata: Er worden expliciete constructies gegeven voor DFA's en DFAO's die rekenkundige relaties herkennen (optellen, aftrekken, vermenigvuldigen met een constante).
• Interne Sequenties: Er wordt een link gelegd tussen de oorspronkelijke sequentie $h$ en de interne sequentie $h'$, gegenereerd door de intrinsieke DFAO (waarbij de outputfunctie de identiteitsafbeelding is). De complexiteit van $h'$ is cruciaal voor het begrijpen van de complexiteit van $h$.
• Subwoordcomplexiteit: De auteurs gebruiken de subwoordcomplexiteitsfunctie $\rho_x(n)$ (het aantal unieke subwoorden van lengte $n$ in een woord $x$) om bovengrenzen voor de toestandscomplexiteit af te leiden.
• Büchi-aritmetiek en Walnut: De paper analyseert hoe deze automata worden geconstrueerd via interpretaties van Büchi-aritmetiek (zoals geïmplementeerd in de software Walnut). Hierbij wordt de runtime-complexiteit van de constructieprocessen (productconstructie, projectie, determinisering) geëvalueerd.
• Myhill-Nerode Theorema: Een aangepaste versie van dit theorema voor DFAO's wordt gebruikt om ondergrenzen voor de toestandscomplexiteit te bewijzen.

3. Belangrijkste Resultaten en Bijdragen

A. Herkenning van Rekenkundige Relaties

• Optelling: Voor zowel MSD- als LSD-first invoer is er een automaat met slechts 2 toestanden die de relatie $[x]_k + [y]_k = [z]_k$ herkent.
• Optellen/Aftrekken met een constante: Voor de relatie $[x]_k + c = [y]_k$ (of $[x]_k - c = [y]_k$) is de toestandscomplexiteit $O(\log_k c)$. De auteurs geven een exacte formule voor het minimale aantal toestanden bij MSD-first invoer, afhankelijk van de $k$-adicische waardatie van $c$ en de startcijfers van de representatie van $c$.
• Vermenigvuldiging: Voor de relatie $n[x]_k + c = [y]_k$ wordt een automaat met $O(n)$ toestanden geconstrueerd.

B. Lineaire Subsequenties en de Link met Subwoordcomplexiteit (Kernbijdrage)

Dit is het meest significante deel van het artikel. De auteurs beantwoorden een open vraag van Zantema en Bosma over MSD-first invoer.

• Theorema 10: Er wordt een directe relatie gevonden tussen de toestandscomplexiteit van een lineaire subsequence $(h(ni+c))$ en de subwoordcomplexiteit van de interne sequentie $h'$.
  • Als $c < n$, is de complexiteit maximaal $\rho_{h'}(n)$.
  • Als $c \geq n$, is de complexiteit maximaal $\rho_{h'}(c+1)$.
• Corollary 11: Gezien een $m$-toestands DFAO voor $h$, is de complexiteit voor MSD-first invoer begrensd door $O(k^n m^2)$ (voor $c<n$) of $O(k^{c+1} m^2)$. Dit is een aanzienlijke verbetering en verduidelijking ten opzichte van eerdere resultaten.
• Thue-Morse Sequentie: De theorie wordt toegepast op de beroemde Thue-Morse-sequentie. De auteurs geven exacte formules voor het aantal toestanden nodig voor $(t(ni))$ en $(t(i+c))$, en tonen aan dat de constructie voor $(t(ni))$ optimaal is voor oneven $n$.

C. Runtime Complexiteit van Constructie

De auteurs analyseren de tijd die nodig is om deze automata te construeren via Büchi-aritmetiek (zoals in Walnut):

• Het construeren van een automaat voor $[x]_k = c$ kost $O((\log^2 c)(\log \log c))$ tijd.
• Het construeren van een automaat voor $n[x]_k + c = [z]_k$ kost $O(\log^2 c \log \log c + n \log^2 n + \dots)$ tijd.
• Het construeren van een DFAO voor $(h(ni+c))$ vanuit een $m$-toestands DFAO kost $O(m^2(n+c) \log(m^2(n+c)))$ tijd, wat de kosten van de tussenstappen (productconstructie en determinisering) meeneemt.

D. Ondergrenzen

• Voor LSD-first invoer wordt bewezen dat de bovengrens van $2m$toestanden voor de verschuiving$(h(i+1))$niet scherp is; er zijn voorbeelden die$2m-1$ toestanden vereisen.
• Voor MSD-first invoer wordt een ondergrens van $\Omega(c^{0.694})$ bewezen voor de complexiteit van $(t(i+c))$ (Thue-Morse), wat aangeeft dat de complexiteit sublineair maar significant groeit met $c$.

4. Significatie

• Oplossing van Open Problemen: Het artikel lost een specifiek open probleem op van Zantema en Bosma door een nieuwe, nauwe connectie te leggen tussen de toestandscomplexiteit van lineaire subsequenties en de subwoordcomplexiteit van de interne sequentie.
• Praktische Toepassing voor Software: De analyse van de runtime-complexiteit is direct relevant voor gebruikers van systemen zoals Walnut. Gebruikers willen weten hoe groot de gegenereerde automata zullen zijn en hoe lang de berekening duurt bij het modelleren van problemen in combinatoriek op woorden.
• Fundamenteel Inzicht: Het werk verduidelijkt het fundamentele verschil tussen MSD-first en LSD-first representaties voor automatische sequenties. Waar LSD-first vaak efficiënter is voor optelling, blijkt MSD-first complexer te zijn voor het hanteren van lineaire subsequenties, maar wel beheersbaar via subwoordcomplexiteit.
• Exacte Formules: Voor specifieke gevallen (zoals de Thue-Morse-sequentie) worden exacte formules voor de toestandscomplexiteit afgeleid, wat zeldzaam is in dit domein waar vaak alleen asymptotische grenzen worden gegeven.

Conclusie

De paper levert een grondige analyse van de complexiteit van operaties op $k$-automatische sequenties. Door de brug te slaan tussen automata-theorie, subwoordcomplexiteit en de implementatiedetails van Büchi-aritmetiek, bieden de auteurs zowel theoretische grenzen als praktische inzichten voor de constructie en optimalisatie van automata in dit domein. De resultaten zijn essentieel voor het begrijpen van de schaalbaarheid van algoritmen die werken met automatische sequenties in software zoals Walnut.