Power of S-kR-RRWW-automata

Issue title: Non-Classical Models of Automata and Applications V

Article type: Research Article

Authors: Hoffmann, Petr

Affiliations: Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám. 25, 118 00, Praha 1, Czech Republic. [email protected]

Note: [] This work was supported by the Grant Agency of the Czech Republic under the projects P103/10/0783 and P202/10/1333. Address for correspondence: Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

Abstract: Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata.

DOI: 10.3233/FI-2015-1145

Journal: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 85-112, 2015