Beitrag in einem Sammelband
Restricting the use of auxiliary symbols for restarting automata
Details zur Publikation
Autor(inn)en: | Jurdzinski, T.; Otto, F. |
Herausgeber: | Farre, J., Litovsky, I. and Schmitz, S. |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2006 |
Seitenbereich: | 176-187 |
Buchtitel: | Tenth International Conference on Implementation and Application of Automata, Proceedings CIAA 2005 |
Titel der Buchreihe: | Lecture Notes in Computer Science 3845 |
Zusammenfassung, Abstract
The most general models of restarting automata make use of auxiliary symbols in their rewrite operations. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.
The most general models of restarting automata make use of auxiliary symbols in their rewrite operations. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.
Projekte
