Skip to main content
6 of 8
deleted 8 characters in body
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

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.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186