In this mathoverflow question, J.-E. Pin asked if it is decidable whether the support of a -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 be a monoid and a commutative ring with unit. Then a mapping is called a representative function if it is a linear combination of matrix coefficients of some representation . Equivalently, is representative if the -submodule of generated by is contained in a finitely generated -submodule. The representative functions form a -algebra with pointwise operations. In fact is properly speaking a bialgebra and is the dual to the bialgebra .
Now let be a finite set and let be the free monoid on . We abbreviate to . We can identify a mapping with the formal power series . Schützenberger defined a power series to be recognizable if the corresponding mapping is representative and proved a power series is recognizable if and only if it is rational (i.e., is in the smallest -subalgebra of 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 is the set of with .
Pin’s question. Is there an algorithm which given a rational power series over (expressed as a linear combination of matrix coefficients of a representation), determines whether the support of 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 are homomorphisms of free monoids (assumed finitely generated here), then the equalizer is the submonoid . The famous Post correspondence problem says that it is undecidable whether is the trivial submonoid. In Theorem 5.2 of this paper it is shown by Salomaa that it is both undecidable whether is regular and whether it is context-free. Basically, given , he constructs such that if is trivial, then is trivial and otherwise is not context-free. Note that always is context sensitive. Since is a submonoid of , we may always assume without loss of generality that .
Here is Eilenberg’s result, although he did not state it this way.
Theorem (Eilenberg). Let be homomorphisms. Then there is a rational power series over with coefficients in whose support is the complement of .
Proof. The proof relies on a faithful representation of over . My favorite is the following one: given by and . If you think of as representing the bit 0 and as representing the bit 1, then where is the binary number represented by . See Exercise 5.2.
Now let be homomorphisms. Then are -linear representations of . As the representative functions form a ring with pointwise operations, we obtain the representative function . Clearly, if and only if , if and only if . Thus the support of the rational series is the complement of , as required.
Corollary. It is undecidable whether the support of a -rational power series is:
- all words;
- 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.