Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911407033810944 |
|---|---|
| author | Zubia, Markel Geuvers, Herman |
| author_facet | Zubia, Markel Geuvers, Herman |
| contents | Infinite words, also known as streams, hold significant interest in computer science and mathematics, raising the natural question of how their complexity should be measured. We introduce cellular automaton reducibility as a measure of stream complexity: σ is at least as complex as τ when there exists a cellular automaton mapping σ to τ. This enables the categorization of streams into degrees of complexity, analogous to Turing degrees in computability theory. We investigate the algebraic properties of the hierarchy that emerges from the partial ordering of degrees, showing that it is not well-founded and not dense, that ultimately periodic streams are ordered by divisibility of their period, that sparse streams are atoms, that maximal streams have maximal subword complexity, and that suprema of sets of streams do not generally exist. We also provide a pseudo-algorithm for classifying streams up to this reducibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21862 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words Zubia, Markel Geuvers, Herman Formal Languages and Automata Theory 68Q80 (Primary) 06A06, 68R15 (Secondary) F.1.1 Infinite words, also known as streams, hold significant interest in computer science and mathematics, raising the natural question of how their complexity should be measured. We introduce cellular automaton reducibility as a measure of stream complexity: σ is at least as complex as τ when there exists a cellular automaton mapping σ to τ. This enables the categorization of streams into degrees of complexity, analogous to Turing degrees in computability theory. We investigate the algebraic properties of the hierarchy that emerges from the partial ordering of degrees, showing that it is not well-founded and not dense, that ultimately periodic streams are ordered by divisibility of their period, that sparse streams are atoms, that maximal streams have maximal subword complexity, and that suprema of sets of streams do not generally exist. We also provide a pseudo-algorithm for classifying streams up to this reducibility. |
| title | Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words |
| topic | Formal Languages and Automata Theory 68Q80 (Primary) 06A06, 68R15 (Secondary) F.1.1 |
| url | https://arxiv.org/abs/2601.21862 |