Prof. Dr. Friedrich Otto is affiliated with the University of Kassel. He is a retired associate professor of the Department of Electrical Engineering and Computer Science.
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 words from that sentence or the replacement of a (possibly discontinuous) substring of that sentence by a shorter substring. It is required that each application of such a reduction operation must preserve the syntactical correctness of the sentence. Accordingly, a restarting automaton consists of a finite-state control, a flexible tape that initially contains the input, and a read-write window of a fixed finite size that works on that tape. The first type of restarting automaton was presented at the international conference FCT...