Confluence of Length Preserving String Rewriting Systems is Undecidable(Theory of Computer Science and Its Applications)
Yi Wang, Masahiko Sakai, Naoki Nishida, Toshiki Sakabe, Keiichirou Kusakari · Institutional Repositories DataBase (IRDB) · 2007
This paper shows the undecidability of confluence for length $pr\infty er\backslash \prime ing$ string rewriting systems.It is proven by reducing the Post's correspondence problem (PCP).which is known to be undecidable, to $\infty nfluence$ problem for length preserving string rewriting systems.More precisely, we designed a reduction algorithm having the property that the existence of a solution for a given instance of PCP coincides with the non-confluence of the string rewriting system obtained kom the reduction algorithm.