zbMATH — the first resource for mathematics

\(\Delta \)-clearing restarting automata and CFL. (English) Zbl 1221.68121
Mauri, Giancarlo (ed.) et al., Developments in language theory. 15th international conference, DLT 2011, Milan, Italy, July 19–22, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22320-4/pbk). Lecture Notes in Computer Science 6795, 153-164 (2011).
Summary: \(\Delta \)-clearing restarting automata represent a new restricted model of restarting automata which, based on a limited context, can either delete a substring of the current content of its tape or replace a substring by a special auxiliary symbol \(\Delta \), which cannot be overwritten anymore, but it can be deleted later. The main result of this paper consists in proving that besides their limited operations, \(\Delta \)-clearing restarting automata recognize all context-free languages.
For the entire collection see [Zbl 1218.68023].

68Q45 Formal languages and automata
Full Text: DOI