Return to Answer

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. 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.

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. 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. 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. Thm 5.2. It is also shown undecidable for context-free.

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.