# 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].

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