The Degree of Squares Is an Atom

Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, and Hans Zantema

In: Proc. Conf. on Combinatorics on Words (WORDS 2015), pp. 109–121, Springer (2015)
# Abstract

A finite state transducer is a finite automaton that transforms input words into output words.
The transducer reads the input letter by letter, in each step producing an output word and changing its state.

While finite state transducers are very simple and elegant devices,
their power in transforming infinite words is hardly understood.

In this paper we show that the degree of the stream
\[ \prod_{i = 0}^\infty 1\, 0^{i^2} = 1 \, 0^0 \, 1 \, 0^1 \, 1 \, 0^4 \, 1 \, 0^9 \, 1 \, 0^{16} \, \cdots = 1101000010000000001 \cdots \]
is an atom in the hierarchy of streams arising from finite state transduction.

In the paper Degrees of Infinite Words, Polynomials and Atoms
we vastly generalise this result by showing that there is precisely one atom for each polynomial degree.
See research for an introduction to finite state transducers,
an overview of my research and many open questions.

@inproceedings{streams:degrees:squares:2015,
author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri and Zantema, Hans},
title = {{The Degree of Squares is an Atom}},
booktitle = {Proc.\ Conf.\ on Combinatorics on Words (WORDS~2015)},
volume = {9304},
pages = {109--121},
publisher = {Springer},
series = {LNCS},
year = {2015},
doi = {10.1007/978-3-319-23660-5\_10},
keywords = {streams, degrees, automata},
type = {conference}
}