Research: Automata

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

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

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; here key notions 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 behaviors 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. The Turing degrees are usually described as a hierarchy of degrees of sets of natural numbers (or functions over natural numbers). They can equivalently be described as a hierarchy of stream degrees since a set of natural numbers correspond to a stream (via its characteristic function). In this view, the Turing degrees arise by Turing machines transforming streams into streams. 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 finite 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 \) (top) the period doubling sequence \( P \) (bottom): \[ \begin{align} & 0 \;\;\; 1 \;\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\; 0 \;\;\; 0 \;\;\; 1 \;\;\ldots \\ \to & \,\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\; 1 \;\;\; 1 \;\;\; 0 \;\;\; 1 \;\;\ldots \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.

Mealy machines are a restricted form of finite state transducers where the output words along the edges always have length 1. So a Mealy machine outputs precisely one letter in each step, that is, for each input letter. For a finite state transducer, the output words along the edges can have arbitrary length, in particular, they can be empty.

A Simple Question

Although finite state transducers are very elegant, 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 illustrated by the following example.

~~Open~~ Problem (Solved)

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?

First stated in [1] (2015).

Solution

No. No finite state transducer transforms \( Q \) into \( P \), so \( Q \) lies strictly below \( P \) in the hierarchy. This problem was solved by Marcel Horbach with the help of ChatGPT: M. Horbach, A strict finite-state transducer image of the Thue–Morse word, unpublished, 2026. See further Theorem 4.9 of the note and the accompanying Lean formalization.

Surprisingly, automata theory offered no techniques to answer such simple questions, and this one stayed open for years. It has now been solved; see the solution above.

Degrees of Streams

We are interested in understanding transformations that finite state transducers can realize 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.

So the Transducer degrees are a hierarchy of stream degrees entirely analogous to the well-known Turing degrees. The only difference is the device realizing the stream transformation.

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 hierarchy of Transducer degrees is much more fine-grained than the Turing degrees (the recursion-theoretic hierarchy) where all computable streams are identified in the trivial bottom degree.

As mentioned before, we hardly understand the power of finite state transducers for transforming streams. So there is a plethora of open questions about the hierarchy of Transducer degrees. The following figure depicts some initial results [2] [3] [1] [4] and open questions about this hierarchy:

hierarchy of stream degrees

Some open problems are indicated in red. The green nodes are degrees (sets of streams). The arrows \( \to \) between degrees represent the partial order on the Transducer degrees. So an arrow \( A \to B \) means that the degree \( A \) is above \( B \) in the hierarchy. Thus every stream in \( A \) can be transformed to every stream in \( B \) by a finite state transducer, but the reverse transformation is not possible by a finite state transducer.

Notation in the figure

In the figure appear the following streams:

\( \mathbf{0} \) is the bottom degree of the hierarchy (see below),
\( M \) is the Thue-Morse sequence and \( P \) is the period doubling sequence (see above); they are in the same degree,
\( Q \) is obtained from \( P \) by dropping every third element (see above),
\( W \) is the Mephisto Waltz sequence (see the open questions below),
\( C \) is the top degree of the computable streams.

Moreover, we use the following notation: for \( f : \mathbb{N} \to \mathbb{N} \) we define the stream \[ \langle f \rangle = \prod_{i = 0}^{\infty} 0^{f(i)}1 = 0^{f(0)} \, 1 0^{f(1)} \, 1 0^{f(2)} \, \cdots\, \] and we write \( \langle f(n) \rangle \) to denote the sequence \( \langle n \mapsto f(n) \rangle \). For instance: \[ \begin{aligned} \langle n \rangle &= 1\;10\;100\;1000\;10000\;\cdots \\ \langle n^2 \rangle &= 1\;10\;10000\;1000000000\;\cdots \end{aligned} \]

Bottom degree

The bottom degree \( \mathbf{0} \) is a degree that is less or equal to all other degrees:

bottom degree

For the Transducer degrees, it consists of all ultimately periodic streams, streams of the form \( uvvvv\cdots \) for finite words \( u,v \). (For the Turing degrees the bottom degree consists of all computable streams.)

Atom degrees

An interesting concept is that of an atom degree, that is, a degree that is directly above the bottom degree with nothing in-between:

atom degree

Thus the atom degrees reduce only to \( \mathbf{0} \) or themselves.

Atoms in the Turing degrees

In the Turing degrees, atoms are usually referred to as minimal degrees. A famous result about Turing degrees, obtained by Spector in 1956, is the existence of an atom degree strictly below the first Turing jump (the degree of the halting problem). In 1971, Lacombe has extended the construction of Spector to show that there are continuum many atoms in the Turing degrees.

Open questions

To mention a few open questions (there are many more):

Formalization

Many of the problems below were solved, or partially solved, with the help of Claude (Anthropic) in October 2026, and the results are formalized in the proof assistant Lean 4. The note Results on the transducer degrees, formalized in Lean 4 (Claude and Jörg Endrullis, 2026) states these results with proof sketches and references to the formalization. The Lean sources are available as transducer-degrees-lean.zip; the included script verify.sh builds them and checks that no proof is missing and that only the standard axioms of Lean are used.

~~Open~~ Problem (Solved)

Is the degree of Thue-Morse an atom?

First stated in [2] (2011).

Solution

No. This was shown by Marcel Horbach with the help of ChatGPT (see the reference in the section A Simple Question above). It also follows from the solution of the problem in that section: the Thue-Morse sequence \( M \) and the period doubling sequence \( P \) are in the same degree, and \( Q \) is not ultimately periodic. So \( \mathbf{0} < Q < P \), and the degree of \( M \) is not an atom.

Open Problem (since 2018)

Does there exist a non-computable atom in the Transducer degrees?

First stated in [5] (2018).

Partial Progress

There is a non-computable degree that has only non-computable degrees and the bottom degree below itself (Corollary 37 in [5]). Moreover:

Every atom is either equivalent to a stream \( \langle g \rangle \) with \( g \) unbounded, or asymptotically uniformly recurrent (every word that occurs infinitely often occurs with bounded gaps).
If \( f \) is spiralling (that is, \( f(n) \to \infty \) and \( f(n) \bmod m \) is ultimately periodic for every \( m \ge 1 \)) and \( f(n+1)/f(n) \to \infty \), for example \( f(n) = n! \), then there is no atom below \( \langle f \rangle \). This generalizes Theorem 4.27 of [3] (no atom below \( \langle 2^n \rangle \)).
Among the streams \( \langle q \rangle \) with \( q \) eventually a quasi-polynomial, the atoms are exactly the degrees of the streams \( \langle p_k \rangle \) (see below).

See further Theorems 4.1, 4.4 and 4.5 of the note and the accompanying Lean formalization.

Open Problem (since 2011)

Are there continuum many atoms in the Transducer degrees?

First stated in [2] (2011), as the question how many atoms exist.

~~Open~~ Problem (Solved)

Are the degrees of Thue-Morse \( M \) and Mephisto Waltz \( W \) incomparable? Here \( W \) is the morphic stream obtained as the limit of iterating the morphism \( 0\mapsto 001 \), \( 1\mapsto 110 \) on the starting word \( 0 \). A transducer transforming \( M \) into \( W \), or \( W \) into \( M \), would have to be erasing, since non-erasing transducers preserve \( \alpha \)-substitutivity [6].

First stated in [2] (2011).

Solution

Yes. No finite state transducer transforms \( M \) into \( W \), and none transforms \( W \) into \( M \). See further Theorem 4.11 of the note and the accompanying Lean formalization.

Open Problem (since 2015)

Does every degree have a minimal cover, that is, a degree directly above with nothing in-between?

First stated in [1] (2015).

Partial Progress

The degree of \( \langle \mathit{fzip}(n,n^2) \rangle \) is a minimal cover of both atoms \( \langle n \rangle \) and \( \langle n^2 \rangle \) (Kaufmann, see the problem on degrees with precisely two or three degrees below them). The atom \( \langle p_3 \rangle \) has infinitely many pairwise incomparable minimal covers; among cubics \( c_3 n^3 + c_2 n^2 + c_1 n + c_0 \), the minimal covers of \( \langle p_3 \rangle \) are exactly those with \( c_1/c_3 - c_2^2/(3c_3^2) = 3/4 \), for example \( \langle 16 n^3 + 12 n \rangle \). See further Theorem 6.2 of the note and the accompanying Lean formalization.

Open Problem (since 2015)

When does a pair of degrees have a least upper (greatest lower) bound?

First stated in [1] and [3] (2015); the existence of pairs without supremum was conjectured already in [2].

Partial Solution

Least upper bounds: a pair of degrees has a least upper bound if and only if the two degrees are comparable.
Greatest lower bounds: for every sequence of streams \( g_0, g_1, \ldots \) over a common finite alphabet there is an exact pair, two streams whose common lower bounds are exactly the streams below some \( g_j \); this pair has a greatest lower bound if and only if \( \{ g_j \} \) has a greatest element (up to equivalence).

For greatest lower bounds the question remains open; there are pairs without a greatest lower bound (Jörg Endrullis, Jan Willem Klop and Rena Bakhshi, Transducer Degrees: Atoms, Infima and Suprema, Acta Informatica 57, 2020). See further Theorems 3.1 and 3.4 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Are there infinite ascending (descending) sequences having a least upper (greatest lower) bound?

First stated in [1] (2015).

Solution

Descending sequences can have a greatest lower bound, but ascending sequences cannot have a least upper bound.

For every degree \( d \) there is a strictly descending sequence of degrees whose greatest lower bound is \( d \). A concrete example: for rational \( \rho > 0 \) let \( d_\rho \) be the degree of \( \langle 2^{\lfloor \rho n \rfloor} \rangle \). Then \( d_{1/2} > d_{2/3} > d_{3/4} > \cdots \) has the greatest lower bound \( d_1 \), the degree of \( \langle 2^n \rangle \).
No strictly ascending sequence of degrees has a least upper bound. More precisely, for every ascending sequence \( \sigma_0 \le \sigma_1 \le \cdots \) there is an exact pair: two upper bounds \( v_1, v_2 \) such that every stream below both \( v_1 \) and \( v_2 \) is below some \( \sigma_k \) (an analogue of Spector’s exact pair theorem for the Turing degrees).

The formalization covers sequences of streams over a common finite alphabet; the concrete example \( d_{1/2} > d_{2/3} > \cdots \) is not formalized. See further Theorems 3.5 and 3.6 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Are there interesting dense substructures?

First stated in [1] (2015).

Solution

Yes. For the degrees \( d_\rho \) of \( \langle 2^{\lfloor \rho n \rfloor} \rangle \) (see the previous problem) we have \( d_\rho \ge d_{\rho’} \) if and only if \( \rho \le \rho’ \), for all rational \( \rho, \rho’ > 0 \). So these degrees form a dense chain without endpoints. Moreover, the degrees below \( \langle 2^n \rangle \) are exactly \( \mathbf{0} \) and the degrees \( d_\rho \) with \( \rho \ge 1 \). The same holds for every base \( b \ge 2 \) in place of \( 2 \): the degrees below \( \langle b^n \rangle \) form a dense chain, without atoms, that is ordered like the rationals in \( (0, 1] \). Only the first statement is formalized. See further Theorem 3.7 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Can every finite partial order be embedded in the hierarchy? Can every finite distributive lattice be embedded in the hierarchy?

First stated in [1] and [3] (2015).

Solution

Every finite partial order can be embedded, but only chains can be embedded as lattices.

For a finite set \( S \subseteq \{1,2,3,\ldots\} \) let \( \sigma_S \) be the stream \( \langle \mathit{fzip}_{k \in S}\, n^k \rangle \) whose blocks of zeros cycle through the polynomials \( n^k \) for \( k \in S \). Then \( \sigma_S \ge \sigma_T \) if and only if \( T \subseteq S \). Hence every finite partial order can be embedded. Moreover, every finite partial order can be embedded into the degrees strictly above any given degree.
A finite lattice can be embedded preserving least upper bounds if and only if it is a chain. In particular, no finite distributive lattice other than a chain can be embedded as a lattice. On the other hand, every finite lattice can be embedded such that greatest lower bounds are preserved (not formalized).

See further Theorem 3.9 and Corollary 3.2 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

How complex is the first-order theory in the language \( ( \ge, = ) \) ?

First stated in [1] (2015).

Solution

The first-order theory of the transducer degrees in the language \( ( \ge, = ) \) is recursively isomorphic to second-order arithmetic (the analogue of Simpson’s theorem (1977) for the Turing degrees). In particular, it is undecidable and not even arithmetical (in fact, not even analytical). See further Theorem 3.12 of the note and the accompanying Lean formalization.

Open Problem (since 2015)

How many degrees exist among polynomials of order \( k \)? What is the structure of the degrees of polynomials?

First stated in [1] (2015).

Partial Progress

Noah Kaufmann, Classifying all transducer degrees below n³, Journal of Logic and Computation 33(5) (2023), classifies the degrees of cubic polynomials below \( \langle n^3 \rangle \). Moreover:

There is exactly one degree of polynomials of order 1 and one of order 2; for every order \( k \ge 3 \) there are countably infinitely many. Polynomials of different orders are incomparable.
For \( k \ge 3 \): \( \langle (an+1)^k \rangle \ge \langle (bn+1)^k \rangle \) if and only if \( a \) divides \( b \).
The degrees of cubic polynomials are classified completely, and both equivalence and order between cubics are decidable. For example, \( \langle n^3 - n \rangle > \langle n^3 \rangle \), and \( \langle n^3 + n \rangle \) is incomparable to \( \langle n^3 \rangle \).
The degrees below \( \langle n^3 \rangle \) are exactly \( \mathbf{0} \), \( \langle p_3 \rangle \), and the degrees of the streams obtained from \( \langle n^3 \rangle \) by keeping only the blocks \( 0^{n^3} 1 \) for \( n \) in a non-empty periodic set.

See further Theorems 5.1, 5.2, 5.4, 5.6 and 5.8 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Is every degree the greatest lower bound of a pair of (other) degrees?

First stated in [1] (2015).

Solution

Yes. Every degree \( d \) is the greatest lower bound of two incomparable degrees strictly above \( d \). For example, for every polynomial \( p \), the degree \( \langle p \rangle \) is the greatest lower bound of \( \langle \mathit{fzip}(p, 2^n) \rangle \) and \( \langle \mathit{fzip}(p, 3^n) \rangle \) (with \( \mathit{fzip} \) as defined in the next problem); this example is not formalized. See further Theorem 3.3 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Is there a degree that has precisely two degrees below itself? Is there a degree that has precisely three degrees below itself: two incomparable degrees and the bottom degree?

First stated in [2] (2011).

Solution

Both questions have a positive answer.

The degree of \( \langle 16n^3 + 12n \rangle \) has precisely two degrees below itself, namely the atom \( \langle p_3 \rangle \) and \( \mathbf{0} \). Note that \( 16n^3 + 12n = (2n-1)^3 + (2n+1)^3 \). More generally, a cubic polynomial \( c_3 n^3 + c_2 n^2 + c_1 n + c_0 \) has this property if and only if \( c_1/c_3 - c_2^2/(3c_3^2) = 3/4 \), and there are infinitely many pairwise incomparable degrees of this kind. See further Theorems 6.1 and 6.2 of the note and the accompanying Lean formalization.
The only degrees below \( \langle \mathit{fzip}(n,n^2) \rangle \) are \( \langle n \rangle \), \( \langle n^2 \rangle \) and \( \mathbf{0} \), see Noah Kaufmann, A Diamond Structure in the Transducer Hierarchy, Discrete Mathematics & Theoretical Computer Science 27:3 (2025). Here \( \mathit{fzip}(f,g) \) alternates between \( f \) and \( g \): \( \mathit{fzip}(f,g)(2n) = f(n) \) and \( \mathit{fzip}(f,g)(2n+1) = g(n) \).

Further open questions raised in our papers:

~~Open~~ Problem (Solved)

Is the degree of the Mephisto Waltz \( W \) an atom?

First stated in [2] (2011).

Solution

No. The stream \( E \) defined by \( E(n) = \big( W(2n) + W(2n+1) \big) \bmod 2 \) satisfies \( \mathbf{0} < E < W \). Similarly, the prime generated streams \( v_{\{p\}} \) are not atoms (see the next problem). See further Theorem 4.10 of the note and the accompanying Lean formalization.

Open Problem (since 2011)

For a set \( A \) of primes, the prime generated stream \( v_A \) is defined by \( v_A(n) = \big( \sum_{p \in A} v_p(n) \big) \bmod 2 \) for \( n \ge 1 \), where \( v_p(n) \) is the multiplicity of the prime \( p \) in the prime factorization of \( n \). Up to exchanging 0 and 1, \( v_{\{2\}} \) is the period doubling sequence \( P \), so it is not an atom (see above). Is \( v_{\{p\}} \) an atom for every odd prime \( p \)? Is there a set \( A \) of primes such that the degree of \( v_A \) is an atom?

First stated in [2], Question 50 and Section 8 (2011).

Partial Solution

The first question has a negative answer.

\( v_A \) is not an atom for every finite non-empty set \( A \) of primes, and for \( A = N_p \) and \( A = \{p\} \cup N_p \), where \( N_p \) is the set of primes that are quadratic non-residues modulo \( p \) (the Mephisto Waltz corresponds to \( \{3\} \cup N_3 \)). For example, for every odd prime \( p \), the stream \( y_p(n) = v_p(2n+1) \bmod 2 \) satisfies \( \mathbf{0} < y_p < v_{\{p\}} \).
The degrees below \( v_{\{p\}} \) are rich: for \( m, m’ \) not divisible by \( p \), the decimation \( \big( v_{\{p\}}(mn+1) \big)n \) can be transformed into \( \big( v{\{p\}}(m’n+1) \big)n \) if and only if \( m \mid m’ \). This yields an infinite antichain, an infinite descending chain, and embeddings of all finite partial orders below \( v{\{p\}} \).

Whether \( v_A \) is an atom for some infinite set \( A \) is still open. See further Theorems 8.1 and 8.2 of the note and the accompanying Lean formalization.

Open Problem (since 2011)

Does \( v_A \ge v_B \) imply \( A = B \), for all non-empty sets \( A, B \) of primes?

First stated in [2], Conjecture 51 (2011).

Partial Progress

We have \( M \equiv v_{\{2\}} \) and \( W \equiv v_A \) for \( A = \{3\} \cup \{ p \text{ prime} \mid p \equiv 2 \pmod 3 \} \) [2], so the solution of the problem about \( M \) and \( W \) above confirms the conjecture for this pair of sets.

Open Problem (since 2011)

How can we prove that a stream \( s \) cannot be transformed into a stream \( t \) by a finite state transducer? In particular, how can we prove this for morphic streams?

First stated in [2] (2011).

Open Problem (since 2011)

Can fractal curves, drawn from streams by turtle graphics, be used as a tool to distinguish degrees?

First stated in [2] (2011).

Open Problem (since 2015)

Is transducibility \( \ge \) decidable for automatic (or morphic) sequences? Is equivalence decidable for automatic (or morphic) sequences? Is it decidable whether an automatic sequence can be transformed into, or is equivalent to, the Thue-Morse sequence?

First stated in [1] (2015).

~~Open~~ Problem (Solved)

Can every countable partial order be embedded in the hierarchy? For the Turing degrees this holds by a theorem of Sacks.

First stated in [1] (2015).

Solution

Yes. Every countable partial order can be embedded, even into the degrees strictly above any given degree. Only the case of finite partial orders is formalized. See further Theorem 3.9 of the note and the accompanying Lean formalization.

Open Problem (since 2015)

For spiralling functions \( f \) and \( g \) (defined above), whether \( \langle g \rangle \ge \langle f \rangle \) holds can be characterized by weighted products [5]. What preorder does transducibility induce on the streams \( \langle f \rangle \) for spiralling functions \( f \), and in particular for polynomials?

First stated in [1] (2015).

~~Open~~ Problem (Solved)

For \( k \ge 3 \), is there a degree strictly between \( \langle n^k \rangle \) and the polynomial atom \( \langle p_k \rangle \)?

First stated in [4] (2016).

Solution

Yes. For \( k = 3 \) this follows from Kaufmann’s classification (see the problem on polynomials above). For every \( k \ge 3 \) we have \( \langle n^k \rangle > \langle (2n+1)^k \rangle > \langle (4n+1)^k \rangle > \langle (8n+1)^k \rangle > \cdots > \langle p_k \rangle \). See further Theorem 5.2 of the note and the accompanying Lean formalization.

~~Open~~ Problem (Solved)

Corollary 36 of [5] states: every countable set \( C \) of degrees with pairwise almost disjoint cones (that is, the only degree below two different degrees in \( C \) is \( \mathbf{0} \)) can be extended to an uncountable set of degrees with pairwise almost disjoint cones. Can ‘uncountable’ be replaced by ‘continuum’?

First stated in [5] (2018).

Solution

Yes. There are continuum many degrees with pairwise almost disjoint cones and without atoms below them, and every countable set \( C \) as above can be extended by continuum many of these degrees. See further Theorem 7.1 of the note and the accompanying Lean formalization.

Open Problem (since 2020)

Are there suitable notions of Kolmogorov complexity that are related to the Transducer degrees?

First stated in [7] (2020).

Open Problem (since 2013)

What is the structure of the degrees restricted to particular families of streams, for example the computable or the morphic streams?

First stated in [8] (2013).

Open Problem (since 2014)

Non-erasing transducers preserve \( \alpha \)-substitutivity [6]. As a consequence, an \( \alpha \)-substitutive and a \( \beta \)-substitutive sequence, for multiplicatively independent \( \alpha \) and \( \beta \), have no common non-erasing transducts except for the ultimately periodic sequences. Which of these results remain valid for general finite state transducers, which can erase?

First stated in [6] (2014).

Open Problem (since 2011)

How do the degrees of well-known streams compare? For example, are the Thue-Morse sequence \( M \) and the Sierpiński stream \( S \) of the same degree? (The Sierpiński stream is in the degree of the Mephisto Waltz \( W \) [2].)

First stated in [2] (2011).

Partial Progress

The example is solved: \( M \) and \( S \equiv W \) are incomparable (see the problem about \( M \) and \( W \) above). Moreover:

The Thue-Morse sequence \( M \), the paperfolding sequence \( \mathit{PF} \) and the Rudin-Shapiro sequence \( \mathit{RS} \) are pairwise incomparable, and \( \mathit{RS} \) is equivalent to the letterwise sum \( \mathit{PF} \oplus P \) modulo 2.
The stream \( Q \) from A Simple Question is incomparable with \( \mathit{PF} \) and with \( \mathit{RS} \).
The characteristic sequences of the squares and of the powers of 2 are incomparable with each other and with each of \( M \), \( P \), \( \mathit{PF} \), \( \mathit{RS} \), \( Q \), \( W \), the Fibonacci word and the Chacón word; none of these eight streams can be transformed into the Baum-Sweet sequence.

See further Theorem 4.12 of the note and the accompanying Lean formalization.

Open Problem (since 2013)

The fingerprint of a stream \( \sigma \) over \( \{0,1\} \) is the infinite matrix with rows \( \sigma, \delta(\sigma), \delta^2(\sigma), \ldots \), where the finite state transducer \( \delta \) maps a stream to the stream of sums modulo 2 of consecutive bits; all rows are in the same degree as \( \sigma \). What information about the complexity of a stream can be derived from its fingerprint? The fingerprint of the Fibonacci word looks rather ‘quiet’. Is this so for all Sturmian streams?

First stated in [8] (2013).

~~Open~~ Problem (Solved)

The degrees of \( \langle n \rangle \) and \( \langle n^2 \rangle \) are atoms. Is the degree of \( \langle n^k \rangle \) an atom for every \( k \ge 1 \)? For this it would suffice to show that \( \langle p(n) \rangle \ge \langle n^k \rangle \) for every polynomial \( p \) of order \( k \).

First stated in [3] (2015).

Solution

No. For every \( k \ge 3 \) the degree of \( \langle n^k \rangle \) is not an atom; the unique atom among the degrees of polynomials of order \( k \) is \( \langle p_k \rangle \) (see below) [4].

~~Open~~ Problem (Solved)

Every stream \( \langle a n^2 + b n + c \rangle \) with integers \( a > 0 \) and \( b, c \ge 0 \) can be transformed into \( \langle n^2 \rangle \) [3]. Conversely, can \( \langle n^2 \rangle \) be transformed into \( \langle a n^2 + b n + c \rangle \), so that all quadratic polynomials have the same degree? Is there a relation to the geometric fact that all parabolas coincide up to translation and scaling?

First stated in [1] (2015).

Solution

Yes. \( \langle n^2 \rangle \) can be transformed into \( \langle a n^2 + b n + c \rangle \), so all these streams have the same degree. The transduction amounts to ‘completing the square’, the algebraic counterpart of the fact that parabolas coincide up to translation and scaling. See further Theorem 5.1 of the note and the accompanying Lean formalization.

Automatic and morphic sequences

Mix-automatic sequences are generated by finite automata with output whose input alphabet (the base of the next digit) depends on the current state [9]; equivalently, they are the sequences defined by zip-mix specifications [10].

Open Problem (since 2013)

(Question of J.-P. Allouche.) Characterize the sequences that are both mix-automatic and morphic. All automatic sequences are both; there are mix-automatic sequences that are not morphic, and morphic sequences that are not mix-automatic.

First stated in [8] and [9] (2013).

Partial Progress

Hans Zantema, Characterizing morphic sequences (2023), shows that the morphic sequences are exactly the sequences generated by the same kind of automata when they read the digits in the opposite direction (most significant digit first). The interleaving \( \mathit{zip}(\gamma_2, \gamma_3) \) of a 2-automatic and a 3-automatic sequence is mix-automatic but not morphic, where \( \gamma_p(n) = v_p(n+1) \bmod 2 \); so morphic sequences are not closed under interleaving. The formalization assumes a theorem of Fabien Durand (2013) as a hypothesis: uniformly recurrent morphic sequences are primitive substitutive. See further Theorem 10.3 of the note and the accompanying Lean formalization.

Open Problem (since 2012)

Is it decidable whether two mix-automata (equivalently, two zip-mix specifications) generate the same sequence? For zip-specifications with zips of a single arity \( k \), that is, for \( k \)-automatic sequences, equivalence is decidable, and adding projections makes it undecidable [10].

First stated in [10] (2012).

Open Problem (since 2013)

Cobham’s theorem says that if \( k, \ell \ge 2 \) are multiplicatively independent, then every sequence that is both \( k \)-automatic and \( \ell \)-automatic is ultimately periodic. Can Cobham’s theorem be generalized to mix-automatic sequences, with a suitable notion of multiplicative independence?

First stated in [8] and [9] (2013).

Partial Progress

If the product of the bases along every cycle of the base determiner (the part of the automaton that determines the base of the next digit) is a power of \( k \), then the sequences generated with it are exactly the \( k \)-automatic sequences. For example, alternating the bases 2 and 3 yields exactly the 6-automatic sequences. See further Theorem 10.1 of the note and the accompanying Lean formalization.

Open Problem

Is it decidable whether two morphic words, given by morphisms and codings, are equal? For words generated by periodically iterated morphisms this is undecidable [11].

A long-standing open problem; stated in [11] (2014).

Open Problem

The Kolakoski word \( K = 1221121221221121122\cdots \) is the sequence of its own run lengths. It is not purely morphic. Is it morphic, that is, the image under a coding of a fixed point of a morphism?

A well-known open problem; stated in [8] (2013).

~~Open~~ Problem (Solved)

For a number representation \( r : \mathbb{N} \to \Sigma^* \), a sequence \( \sigma \) is \( r \)-automatic if there is a finite automaton with output \( A \) such that \( \sigma(n) = A(r(n)) \) for all \( n \). There is a bijective representation \( r \) such that every morphic sequence is \( r \)-automatic [12]. Is there a computable bijective representation \( r \) such that precisely the morphic sequences are \( r \)-automatic?

First stated in [12] (2015).

Solution

No, not even for non-computable representations: for every \( r \), the \( r \)-automatic sequences are closed under pairing \( n \mapsto (\sigma(n), \tau(n)) \), but the characteristic sequences of the powers of 2 and of the powers of 3 are morphic while their pairing is not. The formalization assumes two classical results as hypotheses: uniformly recurrent morphic words are primitive substitutive (Fabien Durand, Decidability of uniform recurrence of morphic sequences, 2013), and \( \log 2/\log 6 \) is transcendental (Gelfond–Schneider). See further Theorem 11.1 of the note and the accompanying Lean formalization.

Finite automata

Open Problem (since 2013)

Can finite state transducers be decomposed into elementary, ‘prime’ transducers with respect to composition (feeding the output of one transducer into the next)? For Mealy machines such a prime decomposition is given by the Krohn-Rhodes theorem.

First stated in [8] (2013).

Open Problem (since 2015)

Given a finite automaton that reads pairs of base-\( k \) digits, is it decidable whether it accepts the base-\( k \) representations of numbers \( p, q \) such that \( p/q \) is an integer? The variant asking whether some \( p/q \) is a power of \( k \) is undecidable [13].

Posed by Eric Rowland and Jeffrey Shallit, Automatic sets of rational numbers, IJFCS 26 (2015); stated in [13] (2017).

Open Problem (since 2017)

Given a deterministic finite automaton over \( \{0,1\} \), is it decidable whether it accepts the base-2 representation of some prime number? A decision procedure would settle whether there is a Fermat prime \( 2^{2^k}+1 \) with \( k > 4 \).

First stated in [13] (2017).

Open Problem (since 2017)

Given a deterministic finite automaton over \( \{0,1\} \), is it decidable whether it accepts the base-2 representation of some square \( n^2 \)?

First stated in [13] (2017).

Open Problem (since 2015)

For a bijective encoding \( f : \Sigma^* \to \Gamma^* \) let \( \mathcal{L}_f \) be the class of languages \( L \subseteq \Sigma^* \) such that \( f[L] \) is regular. For every countable class of languages there is a bijective \( f \) such that \( \mathcal{L}_f \) contains the class, but in general \( f \) is not computable [12]. Which classes \( \mathcal{L}_f \) can be obtained by computable bijective encodings \( f \)? For example, is there a computable bijective encoding that makes precisely the context-free languages regular?

First stated in [12] (2015).

Partial Progress

A class \( C \) of languages is contained in \( \mathcal{L}_f \) for some computable bijective encoding \( f \) if and only if \( C \) is contained in a family of languages with uniformly computable membership for which it is decidable whether a finite Boolean combination of members is infinite. Which classes are exactly of the form \( \mathcal{L}_f \) is still open. See further Theorem 12.6 of the note and the accompanying Lean formalization.

Relevant papers

In [2] we perform an initial investigation of the hierarchy of Transducer degrees. We show that the hierarchy is not dense and not well-founded (there are infinite descending and infinite ascending sequences). The main result in this paper is

The degree of the stream \( \langle n \rangle \) is an atom: \[ \langle n \rangle = 1\;10\;100\;1000\;10000\;100000\;\cdots \] See `Notation in the figure’ (above) for an explanation of the notation \( \langle f \rangle \).

In [3] we show that also

The degree of the stream \( \langle n^2 \rangle \) is an atom: \[ \langle n^2 \rangle = 1\;10\;10000\;1000000000\;\cdots \]

This suggests that all degrees of \( \langle n \rangle, \langle n^2 \rangle, \langle n^3 \rangle, \langle n^4\rangle,\ldots \) are atoms. Surprisingly, this is not the case, as we show in [4].

In [4] we show that techniques from continuous mathematics can be used to reason about finite state transducers. To be precise, we use the following methods from linear algebra and analysis:

continuity,
Vandermonde matrices,
invertibility of matrices, and
the generalized mean inequality.

To our best knowledge, we are the first to apply these techniques to finite state transducers – note that finite state transducers as well as streams are discrete objects. We employ these techniques to obtain both positive and negative results on transducibility. We have used (1)–(3) to establish that there exist transducers that realize certain transformations on streams. This allowed us to conclude that there is an infinite number of atoms (non-trivial, minimal degrees) in the Transducer degrees. We have employed (4) to reason about limitations of finite state transducers, to show that certain transductions are impossible. For instance, we have shown that the stream \( \langle n^3 + n^2 + n \rangle \) cannot be transformed into \( \langle n^3 \rangle \).

The main results of [4] are:

For \( k \ge 3 \), the degree of \( \langle n^k \rangle \) is not an atom.

For every \( k \ge 1 \), there is a polynomial \( p_k \) of order \( k \) such that the degree of \( \langle p_k \rangle \) is an atom. Here \[ p_k(n) = \sum_{i = 0}^{k - 1} a_i (k n + i)^k \] for some \( a_0,\ldots,a_{k-1} > 0 \). The degree \( \langle p_k \rangle \) is the unique atom among and the infimum of all the degrees of polynomials of order \( k \). For \( a_0 = \cdots = a_{k-1} = 1 \), see further Theorem 4.3 of the note and the accompanying Lean formalization.

Thus there is an infinite number of atoms in the Transducer degrees. It remains open whether there are continuum many atoms.

In [7] we show that there are pairs of degrees without supremum and pairs without infimum. The former result is somewhat surprising: every finite set of degrees has a supremum if we strengthen the machine model to Turing machines, and also if we weaken it to Mealy machines.

The survey paper [1] compares the hierarchies of stream degrees arising from stream transduction as realized by

Turing machines (Turing degrees),
finite state transducers (Transducer degrees), and
Mealy machines (Mealy degrees).

We compare central properties of these hierarchies. We summarize our main results on Transducer degrees and also related results on Turing degrees and Mealy degrees.

In [6] we show that non-erasing transductions (no empty words along the edges) preserve a condition called alpha-substitutivity. Roughly, a sequence is alpha-substitutive if the sequence can be obtained as the limit of iterating a substitution with dominant eigenvalue alpha. This result can be applied to prove that certain transformations are not possible using non-erasing transducers. Unfortunately, this result does not not generalise to general finite state transducers (which can have empty words along the edges), and therefore cannot be applied to reason about the Transducer degrees.

In [13] we consider finite automata (not finte state transducers). Most properties of finite automata are decidable. In [13] we give some examples of undecidable properties.

A Simple Question

Degrees of Streams

Bottom degree

Atom degrees

Open questions

Automatic and morphic sequences

Finite automata

Relevant papers

References

Summary

Bibtex

Digital Object Identifier

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Bibtex

Digital Object Identifier

Bibtex

Digital Object Identifier

Bibtex

Digital Object Identifier

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier

Summary

Bibtex

Digital Object Identifier