A property of left-linear rewrite systems preserving recognizability

摘要

Let R be a left-linear rewrite system over sign(R), and let Sigma = (g,#) boolean OR sign(R), where g is an element of Sigma(1) - sign(R) and # is an element of Sigma(0) - sign(R). We show that R effectively preserves Sigma-recognizability if and only if R effectively preserves recognizability. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 11]