🇬🇧

On the Expressive Power of Stateless Ordered Restart-Delete Automata

Otto, Friedrich

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.

Sponsor
Gefördert im Rahmen des Projekts DEAL
Citation
In: Theory of Computing Systems Volume 65 / Issue 7 (2021-03-13) , S. 1033-1068; eissn:1433-0490
Collections
@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}
}