The undecidability of self-embedding for finite semi-Thue and Thue systems (Q1092041)

A semi-Thue system S (Thue system T) is self-embedding if there exist words x, y and z such that xz\(\neq e\) and y \(\Rightarrow^*_ S xyz\) (y \(\leftrightarrow^*_ T xyz)\). It is shown that it is unecidable in general whether or not a given finite semi-Thue system S (Thue system T) is self-embedding. This result is proved by an effective reduction from the DLBA-emptiness problem to the self-embedding problem for Thue systems. This reduction is a variant of the one used by Narendran and McNaughton to prove the undecidability of preperfectness of finite Thue systems [\textit{P. Narendran} and \textit{R. McNaughton}, The undecidability of preperfectness of Thue systems, Theor. Comput. Sci. 31, 165-174 (1984; Zbl 0545.03022)].