
From a linear context-free grammar simulating an arbitrary instance $(\varphi_1,\varphi_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 $(\varphi_1,\varphi_2)$ possesses a solution if and only if the quotient operation $h\g$ is not injective on its domain. Hence, the undecidability of the injectivity problem follows.
Journal of Automata, Languages and Combinatorics, Volume 6, Number 1, 2001, 91-96
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
