Formal properties of finite automata and applications. LITP Spring school on theoretical computer science, Ramatuelle, France, May 23-27, 1988. Proceedings (Q1801316)

[The articles of this volume will not be indexed individually.] The book contains the proceedings of the Spring School on Theoretical Computer Science, Ramatuelle, France, May 23-27, 1988. It is devoted on Finite Automata Applications. Eighteen papers are published into three sections: I. Mathematical foundations of the theory of automata. II. Problems, related to the theory of automata. III. Applications of theory of automata. In the first section, including six papers, many useful aspects of the theory of automata are discussed, mainly from algebraic point of view: the wreath product principle, the relational morphisms and transductions, polysequential functions, two-way automata. The first paper by \textit{J. Berstel}, as a survey, contains the basic results on finite automata and relational languages. The next paper by \textit{H. Straubing} is an introduction to the wreath product of transformation semigroups and the decomposition techniques for finite automata. Polysequential functions, their relationship with relational functions, a special recognizing machine for them, are thoroughly investigated by \textit{M. P. Schützenberger}. The representable transductions and the relational morphisms are described by \textit{J. E. Pin} as useful algebraic tools to study operations on recognizable languages: the most natural operations on languages (resp. semigroups) are discussed in terms of semigroups (resp. languages), as well as the related problems. \textit{J. C. Birget} indicates that two-way automata have the potential of giving rise to a nice mathematical theory. The properties of factorization forests (\textit{I. Simon}) are the last subject in the section. Six chapters are presented in Section II. They are concerned with problems related to automata theory. The first paper by \textit{K. Hashiguchi} investigates the notion of relative star height to any pair of a regular language and a finite class of regular languages, and shows the existence of a (recursive) algorithm for determining relative star height. \textit{J. Meakin} considers the use of automata theory for the word problem for monoid presentations. \textit{W. Thomas} discusses the connection between \(\omega\)-languages and hierarchies of recursion theory and descriptive set theory. The survey paper by \textit{P. Weil} reviews the main results on the concatenation product as a fundamental operation of the theory of formal languages. \textit{A. de Luca} and \textit{St. Varricchio} propose a new finiteness condition for semigroups. The paper by \textit{J. Almeida} is concerned with equations defining varieties of finite semigroups. The last six chapters, organized as Section III, are about different applications of the automata theory: algorithms for string-matching (\textit{M. Crochemore}), some problems in number theory reformulated by \textit{G. Rauzy} in terms of automata, codes and automata (\textit{A. Restivo}). The connections between algebraic theory of finite automata and computational complexity (circuit complexity and membership problem) are investigated by \textit{H. Straubing} and \textit{D. Thérien}. Applications of finite automata to characterize a class of fair languages are considered by \textit{I. Guessarian}. \textit{D. Vergamini} describes two software tools for verification of distributed systems.