Injectivity of the quotient h/g of two morphisms and ambiguity of linear grammars

摘要

From a linear context-free grammar simulating an arbitrary instance (φ1,φ2) of the Post correspondence problem PCP we easily construct two nonerasing morphisms h and g with h length-duplicating such that the instance (h,g) of PCP has no solution but (φ1,φ2) possesses a solution if and only if the quotient operation hg is not injective on its domain. Hence, the undecidability of the injectivity problem follows.