Friedrich Otto - Böcker

The subject of this book is string-rewriting systems. It is generally accepted that string-rewriting was first introduced by Axel Thue in the early part of this century. In the 1960's and early 1970's, it received renewed attention due to interest in formal language theory. In the 1980's and 1990's, it has received more interest since it can be viewed as a special case of term­ rewriting, a subject that has become important in the study of automated deduction. Today, string-rewriting is studied by researchers in theoretical computer science and also by researchers interested in the foundations of artificial intelligence. A sketch of the way that the subject has developed is contained in Chapter 0, and the reader is advised to begin with that chapter. Both authors have been active in the field and have lectured on the subject in several universities. Lecture notes have been produced and dis­ tributed. This monograph is a result of revising and rewriting those notes. It represents an attempt by the authors to present the concepts that the authors consider to be most fundamental and to gather together the most useful results in such a way that they can be understood and used in studies relating to more general rewriting, to automated deduction, and to algo­ rithmic problems of algebraic structures. This monograph is written for independent study by researchers in the­ oretical computer science or in the foundations of artificial intelligence.

Other topics include the descriptional complexity and inductive inference of certain types of restarting automata, cooperating distributed and parallel communicating systems of restarting automata, restarting automata with output, weighted restarting automata, and restarting automata for picture languages and tree languages.

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 in 1995. This type was required to restart as soon as it executes a rewrite operation, that is, the window jumps back to the left end of the tape and the finite-state control is reset to the initial state. Moreover, each rewrite operation simply deletes one or more letters from the contents of the read-write window. Subsequently, many different variants of the restarting automaton have been defined and studied. In particular, proper length-reducing rewrite operations have replaced the original delete steps, additional non-input letters, called auxiliary letters, have been added to the alphabet, and the original combined rewrite/restart operation has been split into a rewrite operation and a separate restart operation. Thus, the restarting automaton is no longer just a particular type of automaton, but it has evolved into a whole family of various types of automata that are specified through several parameters. The objective of the current monograph is to collect the many results that have been obtained on the various types of restarting automata in one place and to present them in a uniform and systematic way. In particular, the influence of the various parameters on the expressive capacity of the resulting types of restarting automata is studied in detail. Other topics include the descriptional complexity and inductive inference of certain types of restarting automata, cooperating distributed and parallel communicating systems of restarting automata, restarting automata with output, weighted restarting automata, and restarting automata for picture languages and tree languages. This monograph may serve as a book of reference for researchers working in formal language and automata theory, as a guide to the literature on restarting automata, and as a text book for an advanced undergraduate or graduate course in formal language and automata theory.

Other topics include the descriptional complexity and inductive inference of certain types of restarting automata, cooperating distributed and parallel communicating systems of restarting automata, restarting automata with output, weighted restarting automata, and restarting automata for picture languages and tree languages.

This book constitutes the refereed proceedings of the Second International Conference on Language and Automata Theory and Applications, LATA 2008, held in Tarragona, Spain, in March 2008. The 40 revised full papers presented were carefully reviewed and selected from 134 submissions. The papers deal with the various issues related to automata theory and formal languages