On the Descriptional Complexity of Simple RL-Automata
Classification / Keywords
Sponsor
Citation
In: Mathematische Schriften Kassel 06, 04 / (2006) , S. ;
Collections
Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.
@article{urn:nbn:de:hebis:34-2006110215424, author ={Messerschmidt, Hartmut and Mráz, František and Otto, Friedrich and Plátek, Martin}, title ={On the Descriptional Complexity of Simple RL-Automata}, copyright ={https://rightsstatements.org/page/InC/1.0/}, language ={en}, year ={2006} }