Restarting automata, which were originally introduced to handle certain problems in the linguistic analysis of natural languages, are considered in this paper for their formal properties. The basic model, the RLWW-automaton, is a nondeterministic two-way acceptor that slides a window across a string of letters from an input alphabet, occasionally replacing the contents of the window with a shorter string and restarting from the initial state using the modified string. Auxiliary symbols that are not in the input alphabet can be used during the replacement process. A number of recent papers, many of which are cited, attempt to place the languages accepted by the model and its many variants into the Chomsky hierarchy.

The authors of the paper parameterize RLWW language classes according to two criteria: the number of auxiliary symbols in the alphabet, and the maximum number of auxiliary symbols that might appear in any configuration reachable from a valid starting configuration. These are further broken down into several more categories (for instance, by counting only the auxiliary symbols that occur in configurations of accepting computations).

The most difficult result is a lengthy (more than six journal pages) proof that certain context-free languages can be accepted by deterministic RLWW-automata only if the maximum number of auxiliary symbols that occur in any configuration is &OHgr;(n/log⁵n), where n is the input length. This result, which holds for an auxiliary alphabet of any size, uses Kolmogorov complexity analysis and the two-linear language PAL², where PAL is the language of even-length palindromes over {0,1}.

If the behavior of the RLWW is restricted so that left moves are not permitted (apart from restarts), no more than n occurrences of a single auxiliary symbol for inputs of length n are needed, or log n if only configurations are accepted. More precisely, this result demonstrates that an accepting computation always exists that uses no more than n occurrences in any configuration.

Apart from a number of other, simpler propositions, the remainder of the paper discusses linear languages and their concatenations. Not surprisingly, the class of linear languages requires RLWW-automata with one (at most) auxiliary symbol occurring once (at most). The class of two-linear languages, formed by concatenating two linear languages, yields the same upper bounds. Furthermore, k-linear languages, k > 2, require no more than one auxiliary symbol, and never more than two occurrences in any configuration.

The paper concludes with a number of open problems. For instance, it is not known whether there is an infinite hierarchy of languages, based on either the number of auxiliary symbols or their number of occurrences.