Beitrag in einem Tagungsband
Correctness preservation and complexity of simple RL-automata



Details zur Publikation
Autor(inn)en:
Messerschmidt, H.; Mraz, F.; Otto, F.; Platek, M.
Herausgeber:
Ibarra, Oscar;Yen, Hsu-Chun
Verlag:
Springer
Verlagsort / Veröffentlichungsort:
Berlin
Publikationsjahr:
2006
Seitenbereich:
162-172
Buchtitel:
Implementation and Application of Automata, CIAA 2006 - Proceedings
Titel der Buchreihe:
Lecture Notes in Computer Science 4094
Jahrgang/Band:
4094

Zusammenfassung, Abstract


Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method can be 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 I 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 study the correctness preservation of these automata on the one hand, and the complexity of these automata on the other hand, establishing a complexity measure that is based on the description of t-sRL-automata in terms of so-called meta-instructions. We present a hierarchy result and we show that the correctness preserving nondeterministic t-sRL-automata are not stronger than the deterministic t-sRL-automata.




Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-25-07 um 09:55