Skip to main content
4 of 8
deleted 202 characters in body; added 13 characters in body; edited body; added 2 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 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 shown undecidable in Thm 5.2 szeged.hu/actacybernetica/prevvols/4_1/4_1_127_139.pdf Thm 5.2. It is also shown undec for context-free.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186