This volume contains the proceedings of the 15th Spring School of the LITP (Laboratoire d'Informatique Theorique et de Programmation, Universite Paris VI-VII, CNRS) held from May 25 to 29, 1987 in Saint-Pierre d'Oleron. The meeting was organized by M. Borillo, M. Gross, M. Nivat and D. Perrin. The purpose of this yearly meeting is to present the state of the art in a specific topic which has gained considerable maturity. The proceedings of the last three Spring Schools have already been published in this series and deal with "Automata on Infinite Words" (LNCS 192), "Combinators and Functional Programming Languages " (LNCS 242) and "Automata Networks" (LNCS 316). The contributions gathered for the 1987 conference present a unique combination of automata theory on the one hand and natural language processing on the other hand. Both fields have strong historical links as exemplified by the works of Chomsky and Harris in Linguistics, the work of Backus and others in Computer Science and the work of Schutzenberger in Algebra. The methods described and discussed in the field of string processing and automata cover the traditional algorithms for string matching, data compression, sequence comparison and lexical analysis. The papers that deal more directly with natural language processing treat automated text generation, lexical analysis and formal representation.
Data compression with substitution.- Some pronominalization issues in generation of texts in romance languages.- The use of finite automata in the lexical representation of natural language.- Estimation of the entropy by the lempel-ziv method.- Applications of phonetic description.- Sequence comparison: Some theory and some practice.- The lexical analysis of French.