Aufsatz
On the Expressive Power of Stateless Ordered Restart-Delete Automata
Zusammenfassung
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.
Zitierform
In: Theory of Computing Systems Volume 65 / Issue 7 (2021-03-13) , S. 1033-1068 ; eissn:1433-0490Förderhinweis
Gefördert im Rahmen des Projekts DEALZitieren
@article{doi:10.17170/kobra-202109084733,
author={Otto, Friedrich},
title={On the Expressive Power of Stateless Ordered Restart-Delete Automata},
journal={Theory of Computing Systems},
year={2021}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2021$n2021 1500 1/eng 2050 ##0##http://hdl.handle.net/123456789/13254 3000 Otto, Friedrich 4000 On the Expressive Power of Stateless Ordered Restart-Delete Automata / Otto, Friedrich 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/13254=x R 4204 \$dAufsatz 4170 5550 {{Automation}} 5550 {{Restart-Automat}} 5550 {{Kontextfreie Sprache}} 7136 ##0##http://hdl.handle.net/123456789/13254
2021-09-22T13:58:42Z 2021-09-22T13:58:42Z 2021-03-13 doi:10.17170/kobra-202109084733 http://hdl.handle.net/123456789/13254 Gefördert im Rahmen des Projekts DEAL eng Namensnennung 4.0 International http://creativecommons.org/licenses/by/4.0/ restarting automation ordered rewriting context-free language desciptional complexity limited context restarting automation 600 On the Expressive Power of Stateless Ordered Restart-Delete Automata Aufsatz 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. open access Otto, Friedrich doi:10.1007/s00224-020-10028-3 Automation Restart-Automat Kontextfreie Sprache publishedVersion eissn:1433-0490 Issue 7 Theory of Computing Systems 1033-1068 Volume 65 false
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: