Some Results on RWW- and RRWW-Automata and Their Relation to the Class of GrowingContext-Sensitive Languages

Abstract

It is shown that already the RWW-automata of Jan{\v{c}}ar et al. (1998) accept the Gladkij language $L_{Gl}=\{w\#w^R\#w \mid w\in\{a, b\}^*$, which implies that the class GCSL of growing context-sensitive languages is a proper subclass of the class $L(RWW)$ of languages accepted by the RWW-automata. In addition, it is shown that $L(RWW)$ contains an NP-complete language. Also a simple reduction from the class $L(RRWW)$ of languages accepted by the RRWW-automata to the class $L(RWW)$ is presented, which indicates that these two classes will be hard to separate if they are not identical. Finally, characterizations of the class GCSL in terms of restricted versions of the RWW- and the RRWW-automata are given.