Infinite words, or “streams”, appear everywhere in our field, for example in formal language theory, automata theory, number theory, and dynamical systems. It has also been a main scientific and recreational interest of Hans Zantema, who passed away recently. A natural question is how streams can be compared in terms of their complexity.
Here we introduce the concept of “cellular automaton reducibility” as a measure of stream complexity: A stream σ is deemed as least as complex as another stream τ if there is a cellular automaton that takes σ as input and produces τ as output.
Using this we can categorize streams with similar complexity into “degrees”. We study the hierarchical structure that emerges from the partial ordering of degrees with respect to cellular automaton reducibility. We show that the hierarchy is not well-founded, is not dense, ultimately periodic streams are ordered by the divisibility of their period, and sparse streams are generally atoms (they can only be reduced to the trivial stream). We also compare this hierarchy with the one that is induced by starting from FST-reducibility (finite state transducers), a notion that Hans Zantema has studied (and many others).

This is joint work with Markel Zubia.