Reducing the gradedness problem of string rewriting systems to a termination problem
Itamar Stein · RAIRO - Theoretical Informatics and Applications · 2015
A finite string rewriting system (SRS) is called graded if every word over its alphabet is equivalent to only a finite number of other words. We consider the problem of deciding whether a given finite SRS is graded. We show that, in general, this problem is not decidable. Moreover we show that for many SRSs (including all one-rule SRSs), one can convert the SRS to another SRS such that the original one is graded if and only if the converted one is terminating. Since there are computer programs that can decide for many cases whether a given SRS is terminating or not, this can give us a method to prove automatically if a given SRS is graded or not.