Contribution in edited book
Restricting the use of auxiliary symbols for restarting automata
Publication Details
Authors: | Jurdzinski, T.; Otto, F. |
Editor: | Farre, J., Litovsky, I. and Schmitz, S. |
Publisher: | Springer |
Place: | Berlin |
Publication year: | 2006 |
Pages range : | 176-187 |
Book title: | Tenth International Conference on Implementation and Application of Automata, Proceedings CIAA 2005 |
Title of series: | Lecture Notes in Computer Science 3845 |
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.
Projects
