Degrees of infinite words, polynomials and atoms

Abstract

<p>Our objects of study are finite state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words.</p><p>We use methods from linear algebra and analysis to show that there is an infinite number of atoms in the transducer degrees, that is, minimal non-trivial degrees.</p>