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.


Authors/Editors

Last updated on 2019-25-07 at 13:18