Classification / Keywords
Sponsor
Citation
In: Theory of Computing Systems Volume 65 / Issue 7 (2021-03-13) , S. 1033-1068; eissn:1433-0490
Collections
Stateless ordered restart-delete automata (stl-ORD-automata) are studied. These are obtained from the stateless ordered restarting automata (stl-ORWW-automata) by introducing an additional restart-delete operation, which, based on the surrounding context, deletes a single letter. While the stl-ORWW-automata accept the regular languages, we show that the swift stl-ORD-automata yield a characterization for the class of context-free languages. Here a stl-ORD-automaton is called swift if it can move its window to any position after performing a restart. We also study the descriptional complexity of swift stl-ORD-automata and relate them to limited context restarting automata.
@article{doi:10.17170/kobra-202109084733, author ={Otto, Friedrich}, title ={On the Expressive Power of Stateless Ordered Restart-Delete Automata}, keywords ={600 and Automation and Restart-Automat and Kontextfreie Sprache}, copyright ={http://creativecommons.org/licenses/by/4.0/}, language ={en}, journal ={Theory of Computing Systems}, year ={2021-03-13} }