Skip to main content
2 of 8
added 55 characters in body
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

My guess is that this is undecidable. Here is an approach.

If $f,g\colon A^*\to \{a,b\}^*$ are two morphisms, the 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 Z-series and is based on a faithful 2x2 rep of the free monoid over 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 a jazzed up Post correspondence problem so should be equivalent to whether the halting language of a Turing machine is regular. But this is undecidable day by Rice's theorem. Am I correct? I forget the details of the proof PCP is undecidable but it should preserve regularity vs non regularity of the halting language.

Actually I think the equalizer is always rational.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186