Finite automata play a central role in computer science and mathematics. They are used as

  • acceptors, to define languages, and
  • transformers, to transform words.

For finite words, both aspects of automata have been extensively studied. For infinite words (streams), the focus has been on defining streams and languages of streams. The key notions here are that of

  • automatic sequences playing an important role in number theory, and
  • omega automata (e.g. Büchi, Muller, Rabin and parity automata) which form the basis of model checking and formal verification as they allow for describing the (un)acceptable behaviours of non-terminating systems such as operating systems, control systems or hardware.

Surprisingly, finite automata for transforming streams have hardly been studied. The exception are Turing machines, for which the ensuing hierarchy of stream degrees is well-known as Turing degrees. Beyond Turing machines, there has been almost no research on the power of finite automata for transforming streams.

Goal

We are interested in understanding the power of automata for transforming streams, such as finite state transducers and Mealy machines.

For the sake of this exposition, we will focus on finite state transducers. An example finte state transducer is shown in the following picture:

finite state transducer

A label \( a \mid w \) along an edge indicates that the input letter is \( a \) and the output word is \( w \). The transducer reads the input stream letter by letter, in each step producing a piece of the output and changing its state. So the total output word is the concatenation of all the output words encountered along the edges.

For instance, the transducer displayed above transforms the Thue-Morse sequence \( M \) to the period doubling sequence \( P \): \[ \begin{align} & 0 \;\;\; 1 \;\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\; 0 \;\;\; 0 \;\;\; 1 \;\;\ldots &&= \; M \\ \to & \,\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\; 1 \;\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\ldots &&= \; P \end{align} \]

Background info: the period doubling sequence

The period doubling sequence \[ P = 1011 \;1010 \;1011 \;1011 \;1011\cdots \] is the solution of \[ X = 101? \;101? \;101? \;101? \;101?\cdots \] where the subsequence at the positions indicated by question marks is \( X \) itself. The period doubling sequence can also be obtained from the famous Thue-Morse sequence \[ M = 0110 1001 1001 0110 \cdots \] as the stream of differences of consecutive bits.

A Simple Question without Answer

Although finite state transducers are very elegent, simple devices, we hardly understand them. There is a lack of theory about stream transducers. Even for simple examples of streams, there exist no techniques to determine whether one stream can be transformed into the other by a finite automaton. This is illstrated by the following example.

Open Problem

Take the period doubling sequence \( P \) and drop every third element: \[ \begin{align} P &= 1011 \;1010 \;1011 \;1011 \;1011 \cdots \\ Q &= 10\hphantom{1}1 \;1\hphantom{0}10 \;\hphantom{1}01\hphantom{1} \;10\hphantom{1}1 \;1\hphantom{0}11\cdots \end{align} \] It is easy to find a finite state transducer that transforms \( P \) into \( Q \). Is the reverse also possible?

Surprisingly, automata theory is not ready to answer such simple questions.

Degrees of Streams

We are interested in understanding transformations that finite state transducers can realise on streams. That is, we are concerned with the following transducibility relation ≥ on streams:

For streams \( s, t \) we define \( s \ge t \) if there exists a finite state transducer that transforms \( s \) into \( t \).

The transducibility relation \( \ge \) is a preorder on the set of streams. It induces equivalence classes of streams with respect to \( \ge \cap \le \), and a partial order \( > \) on these equivalence classes. We call the equivalence classes degrees, and refer to the partial order as a Transducer degrees.

Transducibility as a complexity measure

The transducibility relation \( \ge \) can be understood as a complexity measure. If \( s \ge t \) then the stream \( s \) is at least as complex as the stream \( t \). Streams \( s, t \) reside in the same degree if they have the same complexity, that is, \( s \) can be transformed into \( t \), and \( t \) can be transformed into \( s \).

Transducer degrees vs. Turing degrees

As finite state transducers are weaker than Turing machines, the ensuing hiearchy of Transducer degrees is much more fine-grained than the Turing degrees (the recursion-theoretic hierarchy) where all computable streams are indentified in the trivial bottom degree.

The hierarchy of stream degrees is a plethora of open questions. The following figure depicts some initial results and open questions about the hiearchy of stream degrees:

hierarchy of stream degrees