Word Problems and Confluence Problems for Restricted Semi-Thue Systems.

We investigate word problems and confluence problems for the following four classes of terminating semi-Thue systems: length-reducing systems, weight-reducing systems, length-lexicographic systems, and weight-lexicographic systems. For each of these four classes we determine the complexity of several variants of the word problem and confluence problem. Finally we show that the variable membership problem for quasi context-sensitive grammars is EXPSPACE-complete. [ABSTRACT FROM AUTHOR]