🇬🇧

On the Descriptional Complexity of Simple RL-Automata

Messerschmidt, Hartmut
Mráz, František
Otto, Friedrich
Plátek, Martin

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.

Sponsor
F. Mraz and M. Platek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by the program ‘Information Society’ under project 1ET100300517. F. Mraz was also partially supported by the Grant Agency of Charles University under Grant-No. 358/2006/A-INF/MFF.
Citation
In: Mathematische Schriften Kassel 06, 04 / (2006) , S. ; 
@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}
}