Journal article

Publication year: 2013

Pages: 831-846

Journal: International Journal of Foundations of Computer Science

Volume number: 24

Issue number: 6

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054113400212

Publisher: World Scientific Publishing

Abstract: 
The restarting automaton was inspired by the technique of 'analysis by reduction' from linguistics. A restarting automaton processes a given input word through a sequence of cycles. In each cycle the current word on the tape is scanned from left to right and a single local simplification (a rewrite) is executed. One of the essential parameters of a restarting automaton is the size of its read/write window. Here we study the impact of the window size on the descriptional complexity of several types of deterministic and nondeterministic restarting automata. For all k >= 4, we show that the savings in the economy of descriptions of restarting automata that can only delete symbols but not rewrite them (that is, the so-called R- and RR-automata) cannot be bounded by any recursive function, when changing from window size k to window size k vertical bar 1. This holds for deterministic as well as for nondeterministic automata, and for k >= 5, it even holds for the stateless variants of these automata. However, the trade-off between window sizes two and one is recursive for deterministic devices. In addition, a polynomial upper bound is given for the trade-off between RRWW-automata with window sizes k + 1 and k for all k >= 2.

Harvard Citation style: Kutrib, M. and Otto, F. (2013) ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, International Journal of Foundations of Computer Science, 24(6), pp. 831-846. https://doi.org/10.1142/S0129054113400212

APA Citation style: Kutrib, M., & Otto, F. (2013). ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA. International Journal of Foundations of Computer Science. 24(6), 831-846. https://doi.org/10.1142/S0129054113400212