Show simple item record
dc.description.sponsorshipF. 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.extent221343 bytes
dc.subjectanalysis by reductioneng
dc.subjectrestarting automataeng
dc.subjectcorrectness preserving propertyeng
dc.subjectdescriptional complexityeng
dc.subjectnonrecursive trade-offseng
dc.titleOn the Descriptional Complexity of Simple RL-Automataeng
dcterms.abstractAnalysis 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.accessRightsopen access
dcterms.creatorMesserschmidt, Hartmut
dcterms.creatorMráz, František
dcterms.creatorOtto, Friedrich
dcterms.creatorPlátek, Martin
dcterms.isPartOfMathematische Schriften Kasselger
dcterms.isPartOf06, 04ger

Files in this item


This item appears in the following Collection(s)

Show simple item record