The homomorphism problem for the free monoid (Q1861212): Difference between revisions

The following extension problem for mappings is shown to be algorithmically decidable: given a finite subset \(F\) of words over an alphabet \(X\) and a mapping \(\varphi\colon F\to X^*\), determine whether or not \(\varphi\) can be extended to a monoid homomorphism \(F^*\to X^*\). This result gives another solution to the isomorphism problem for finitely generated submonoids of free monoids, a result due to \textit{C. Choffrut, T. Harju}, and \textit{J. Karhumäki} [Theor. Comput. Sci. 183, No. 1, 83-92 (1997; Zbl 0901.68096)].