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.

68Q45 Formal languages and automata