Formal Properties of Finite
Automata and Applications
Jean-Éric Pin (Ed.)
LITP Spring School on Theoretical Computer Science
Ramatuelle, France, May 1988
Proceedings
Lecture Notes in Computer Science 386, Springer, 1989.
This volume contains the proceedings of the sixteenth Spring School of
Theoretical Computer Science (Ecole de Printemps d'Informatique
Théorique) organized jointly by the LITP (Paris), the ENSEEITH, the
LSI (Toulouse) and the "Association d'Informatique Théorique", with
the support of the Centre National de la Recherche Scientifique (CNRS) and
of the Programme de Recherches Coordonnées (PRC)
Mathématiques et Informatique.
The subject of the sixteenth School is the theory of finite automata and
its applications. However two important parts of this theory are not
treated in this volume, because they were already the subject of two
earlier Spring Schools : "Automata on infinite words" (Spring School 1984)
and "Automata Networks" (Spring School 1986).
The proceedings have been divided into three sections. The first section is
devoted to the mathematical foundations of the theory of automata. The
first paper of this section, by J. Berstel, is a survey of the theory of
finite automata which contains many interesting examples. The paper by H.
Straubing is an introduction to the wreath product and the
décomposition techniques for finite automata. M.P.
Schützenberger's paper deserves special mention. Professor
Schützenberger was not able to attend the Spring School, but he was
kind enough to prepare this article on rational fonctions, which was read
by D. Perrin at the Spring School. The next two articles, by myself and
J.C. Birget, concem some useful tools of the theory: relational morphisms
and transductions in my article, and two-way finite automata in Birget's
article. The paper by I. Simon is a survey on factorisation forests, a
concept that covers most of the "Ramseyan type" properties used in the
theory of automata.
The second section deals with famous problems of the theory of automata.
The first paper, by K. Hashiguchi, gives the main ideas of his recent
algorithm for determining the star-height of a given rational language. The
second paper, by J. Meakin, presents some recent advances on word problems.
The paper by W. Thomas shows the connections between automata and
quantifier hiérarchies in logic. P. Weil gives a survey on the
difficult problems connected with the concaténation product,
including some very recent results. The last two papers of this section are
directly related to semigroup theory. A. de Luca and S. Varricchio give
some new finiteness conditions for semigroups, and J. Almeida presents a
new approach on equations defining varieties of finite semigroups.
Some applications of finite automata are presented in the last section.
Algorithms on strings using automata are analyzed by M. Crochemore. G.
Rauzy and A. Restivo show the applications of fînite automata to
number theory and to the theory of codes, respectively. H. Straubing and D.
Thérien present their recent work on computational complexity based
on finite automata. The last two papers, by I. Guessarian and D. Vergamini,
are devoted to the application of automata to the modeling of distributed
systems.
Contents
Part I : Mathematical foundations of the theory of
automata
Finite automata and rational languages. An introduction (J.
Berstel)
The wreath product and its applications (H. Straubing)
Décomposition polynomiale des fonctions rationnelles (M.P.
Schützenberger)
Relational morphisms, transductions and opérations on
languages (J.-E. Pin)
Basic techniques for two-way finite automata (J.C.
Birget)
Properties of factorisation forests (I. Simon)
Part II : Problems related to the theory of automata
Relative star height, star height and finite automata with
distance fonctions (K.Hashiguchi)
Automata and the word problem (J. Meakin)
Automata and quantifier hierarchies (W. Thomas)
Concatenation product: a survey (P. Weil)
A finiteness condition for semigroups (A.de Luca, S.
Varricchio)
Equations for pseudovarieties (J. Almeida)
Part III : Applications of the theory of automata
Algorithms and automata (M.Crochemore)
Numbers and automata (G. Rauzy)
Codes and Automata (A. Restivo)
Finite automata and computational complexity (H. Straubing and D.
Thérien)
A characterization of fair computations of finite state SCCS
processes (I. Guessarian)
Verification of distributed systems: an experiment (D.
Vergamini)
