On the Descriptional Complexity of Simple RL-Automata
| dc.date.accessioned | 2006-11-02T08:49:45Z | |
| dc.date.available | 2006-11-02T08:49:45Z | |
| dc.date.issued | 2006 | |
| dc.description.sponsorship | 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. | eng |
| dc.format.extent | 221343 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2006110215424 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2006110215424 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | analysis by reduction | eng |
| dc.subject | restarting automata | eng |
| dc.subject | correctness preserving property | eng |
| dc.subject | descriptional complexity | eng |
| dc.subject | hierarchies | eng |
| dc.subject | nonrecursive trade-offs | eng |
| dc.subject.ddc | 004 | |
| dc.title | On the Descriptional Complexity of Simple RL-Automata | eng |
| dc.type | Preprint | |
| dcterms.abstract | 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. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Messerschmidt, Hartmut | |
| dcterms.creator | Mráz, František | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.creator | Plátek, Martin | |
| dcterms.isPartOf | Mathematische Schriften Kassel ;; 06, 04 | ger |
| dcterms.source.journal | Mathematische Schriften Kassel | ger |
| dcterms.source.volume | 06, 04 |