Preprint
On the Descriptional Complexity of Simple RL-Automata
Zusammenfassung
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.
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.
Förderhinweis
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.Zitieren
@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},
year={2006}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2006$n2006 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2006110215424 3000 Messerschmidt, Hartmut 3010 Mráz, František 3010 Otto, Friedrich 3010 Plátek, Martin 4000 On the Descriptional Complexity of Simple RL-Automata / Messerschmidt, Hartmut 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2006110215424=x R 4204 \$dPreprint 4170 Mathematische Schriften Kassel ;; 06, 04 7136 ##0##urn:nbn:de:hebis:34-2006110215424
2006-11-02T08:49:45Z 2006-11-02T08:49:45Z 2006 urn:nbn:de:hebis:34-2006110215424 http://hdl.handle.net/123456789/2006110215424 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. 221343 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ analysis by reduction restarting automata correctness preserving property descriptional complexity hierarchies nonrecursive trade-offs 004 On the Descriptional Complexity of Simple RL-Automata Preprint 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. open access Messerschmidt, Hartmut Mráz, František Otto, Friedrich Plátek, Martin Mathematische Schriften Kassel ;; 06, 04 Mathematische Schriften Kassel 06, 04
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: