Restarting Automata

The subject of this monograph are restarting automata. The definition of these automata is motivated by the linguistic technique of analysis by reduction. This technique, which can be used to analyze sentences in natural languages with a rather free word-order like Czech (or Latin or German), consists of a sequence of step-by-step simplifications of a given sentence. Each of these simplifications is realized by a single reduction operation, which consists of either the deletion of one or several