Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is undecidable to know whether the support of a given$^*$ rational series is cofinite (respectively equal to $A^*$). However, it is decidable whether the support is finite (respectively empty). See the exercises of Chapter III in [1].

Question: is it decidable whether the support of a given rational series is a rational (= regular) language?

[1] J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0

(*) The rational series can be given by a weighted automaton or by a finite linear representation.


1 Answer 1


Update. It is undecidable. Here is the proof.

If $f,g\colon A^*\to \{a,b\}^*$ are two morphisms, then one can construct a rational Z-series over A whose support is the complement of the equalizer of f,g. This is how Post correspondence is reduced to universality of $\mathbb{Z}$-series and is based on a faithful 2x2 rep of the free monoid over $\mathbb{N}$. See the proof of Thm 27 of http://www.infres.enst.fr/~jsaka/ENSG/MPRI/Files/References/JS-HWA.pdf

So it suffices to prove it is undecidable whether the equalizer of two free monoid morphisms is rational.

This is shown undecidable in Thm 5.2 here. It is also shown undecidable for 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 Thm 5.2.

Update This is Exercise 1 of II.12 of the book of Salomaa et al and presumably was to use Hilbert's 10th problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.