SCIENCE@home

Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words

Markel Zubia,H. Geuvers

Published 2026 in arXiv.org

ABSTRACT

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: {\sigma} is at least as complex as {\tau} when there exists a cellular automaton mapping {\sigma} to {\tau}. 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-41 of 41 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1