# zbMATH — the first resource for mathematics

Some results on RWW-and RRWW-automata and their relation to the class of growing context-sensitive languages. (English) Zbl 1083.68057
Summary: It is shown that already the RWW-automata of P. Jančar, F. Mráz, M. Plátek and J. Vogel [Lect. Notes Comput. Sci. 1530, 343–354 (1998)] accept the Gladkij language $$L_{\text{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 $${\mathcal L}$$(RWW) of languages accepted by the RWW-automata. In addition, it is shown that $${\mathcal L}$$(RWW) contains an NP-complete language. Also a simple reduction from the class $${\mathcal L}$$(RRWW) of languages accepted by the RRWW-automata to the class $${\mathcal 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.

##### MSC:
 68Q45 Formal languages and automata