Equalizers of free monoid morphisms, supports of rational power series and a question of Pin

In this mathoverflow question, J.-E. Pin asked if it is decidable whether the support of a \mathbb Z-rational power series in non-commuting variables is a regular language. I pointed out that the answer is no and will elaborate here because it is fairly cute.

Let M be a monoid and \Bbbk a commutative ring with unit. Then a mapping f\colon M\to \Bbbk is called a representative function if it is a linear combination of matrix coefficients m\mapsto \rho_{ij}(m) of some representation \rho\colon M\to M_n(\Bbbk). Equivalently, f is representative if the \Bbbk M-submodule of \Bbbk^M generated by f is contained in a finitely generated \Bbbk-submodule. The representative functions \mathrm{Rep(M)} form a \Bbbk-algebra with pointwise operations. In fact \mathrm{Rep(M)} is properly speaking a bialgebra and is the dual to the bialgebra \Bbbk M.

Now let A be a finite set and let A^* be the free monoid on A. We abbreviate \Bbbk A^* to \Bbbk\langle A\rangle. We can identify a mapping f\colon A^*\to \Bbbk with the formal power series s= \sum_{w\in A^*}f(w)w\in \Bbbk\langle\!{\langle} A\rangle\!{\rangle}. Schützenberger defined a power series to be recognizable if the corresponding mapping f is representative and proved a power series is recognizable if and only if it is rational (i.e., is in the smallest \Bbbk-subalgebra of \Bbbk\langle\!{\langle} A\rangle\!{\rangle} containing all polynomials and closed under inversion of power series with non-zero constant term). We remark that the product of representative functions corresponds to the Hadamard product of power series and not the (Cauchy) product.

The support of a rational series \sum_{w\in A^*}f(w)w is the set of w\in L^* with f(w)\neq 0.

Pin’s question. Is there an algorithm which given a rational power series s over \mathbb Z (expressed as a linear combination of matrix coefficients of a representation), determines whether the support of s is a regular languagae (i.e., recognized by a finite automaton)?

The answer is no. This is not surprising because it is known to be undecidable whether the support is all words. The proof is based on the following idea, which goes back to Samuel Eilenberg in his Volume A of Automata, Machines and Languages. Recall that if f,g\colon A^*\to B^* are homomorphisms of free monoids (assumed finitely generated here), then the equalizer E(f,g) is the submonoid \{w\in A^*\mid f(w)=g(w)\}. The famous Post correspondence problem says that it is undecidable whether E(f,g) is the trivial submonoid. In Theorem 5.2 of this paper it is shown by Salomaa that it is both undecidable whether E(f,g) is regular and whether it is context-free. Basically, given f,g, he constructs f',g' such that if E(f,g) is trivial, then E(f',g') is trivial and otherwise E(f',g') is not context-free. Note that E(f,g) always is context sensitive. Since B^* is a submonoid of \{a,b\}^*, we may always assume without loss of generality that B^*=\{a,b\}^*.

Here is Eilenberg’s result, although he did not state it this way.

Theorem (Eilenberg). Let f,g\colon A^*\to \{a,b\}^* be homomorphisms. Then there is a rational power series over A with coefficients in \mathbb Z whose support is the complement of E(f,g).

Proof. The proof relies on a faithful representation of \{a,b\}^* over \mathbb Z. My favorite is the following one: \rho\colon \{a,b\}^*\to M_2(\mathbb Z) given by \rho(a)=\begin{bmatrix} 1 & 0\\ 0 & 2\end{bmatrix} and \rho(b)=\begin{bmatrix} 1 & 1\\ 0 & 2\end{bmatrix}. If you think of a as representing the bit 0 and b as representing the bit 1, then \rho(w) = \begin{bmatrix} 1 & d\\ 0 & 2^{|w|}\end{bmatrix} where d is the binary number represented by w. See Exercise 5.2.

Now let f,g\colon A^*\to \{a,b\}^* be homomorphisms. Then \rho\circ f, \rho\circ g are \mathbb Z-linear representations of A^*. As the representative functions form a ring with pointwise operations, we obtain the representative function s(w)=\sum_{1\leq i,j\leq 2}\left[\rho_{ij}(f(w))-\rho_{ij}(g(w))\right]^2. Clearly, s(w)=0 if and only if \rho(f(w))=\rho(g(w)), if and only if w\in E(f,g). Thus the support of the rational series \sum_{w\in A^*}s(w) is the complement of E(f,g), as required.

Corollary. It is undecidable whether the support of a \mathbb Z-rational power series is:

  1. all words;
  2. regular;
  3. co-context free.

Update. Stefan Göllar has pointed out to me that this result is proved (in essentially the same way) in D. Kirsten and K. Quaas, Recognizablity of the support of recognizable series over the semiring of integers is undecidable, Inf. Process. Lett. 111(10):500-502 (2011). The main difference is that the authors of this paper don’t seem to be aware of Salomaa’s result and so they reprove it.

Update. I’ve since discovered that this questions is an exercise in A. Salomaa and M. Soittola, “Automata-theoretic aspects of formal power series”. Texts and Monographs in Computer Science. Springer-Verlag, New York-Heidelberg, 1978. Presumably, they had in mind a reduction to Hilbert’s tenth problem since this is used for all the decidability results of that section.


About Benjamin Steinberg

Mathematician interested in semigroups, groups and automata.
This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s