Formal Properties of Finite Automata and Applications: LITP Spring School on Theoretical Computer Science, Ramatuelle, France, May 23-27, 1988. Proceedings (Lecture Notes in Computer Science)

"The volume contains the proceedings of the 16th Spring School on Theoretical Computer Science held in Ramatuelle, France, in May 1988. It is a unique combination of research level articles on various aspects of the theory of finite automata and its applications. Advances made in the last five years on the mathematical foundations form the first part of the book. The second part is devoted to the important problems of the theory including star-height, concatenation hierarchies, and connections with logic and word problems. The last part presents a large variety of possible applications: number theory, distributed systems, algorithms on strings, theory of codes, complexity of boolean circuits and others."--Publisher's website Finite automata and rational languages an introduction....Pages 1-14 The wreath product and its applications....Pages 15-24 Polynomial decomposition of rational functions....Pages 25-33 Relational morphisms, transductions and operations on languages....Pages 34-55 Basic techniques for two-way finite automata....Pages 56-64 Properties of factorization forests....Pages 65-72 Relative star height, star height and finite automata with distance functions....Pages 73-88 Automata and the word problem....Pages 89-103 Automata and quantifier hierarchies....Pages 104-119 Concatenation product: a survey....Pages 120-137 A finiteness condition for semigroups....Pages 138-147 Equations for pseudovarieties....Pages 148-164 Algorithms and automata....Pages 165-175 Numbers and automata....Pages 176-185 Codes and automata....Pages 186-198 Finite automata and computational complexity....Pages 199-233 A characterization of fair computations of finite state SCCS processes....Pages 234-248 Verification of distributed systems: An experiment....Pages 249-259 This introductory text gives a short exposition of the basic results concerning finite automata and rational languages.