Rationalité & reconnaissabilité :
une introduction

Résumé

Jacques Sakarovitch
LITP / IBP, C. N. R. S., Paris

Dans la lignée des exposés expositoires de la réunion précédente, on présentera les notions de séries rationnelles et de séries reconnaissables, leurs liens via le théorème dit ``de Kleene - Schützenberger'', les distinctions qu'il convient de faire quand on travaille sur d'autres structures que le monoïde libre, et le pont qu'elles permettent d'établir entre la théorie des automates et celle des SED par le choix judicieux du semi-anneau des coefficients.

Références :

1.

S. Eilenberg, Automata, Languages and Machines, Academic Press, vol. A, 1974.

2.

J. Berstel & Ch. Reutenauer, Les séries rationnelles et leurs langages, Masson, 1983; édition en anglais et augmentée : Rational Series and their Languages, Springer 1988.

3.

D. Perrin, Finite Automata, in Handbook of Theoretical Computer Science, (J. van Leeuwen ed.), vol. B, Elsevier, 1990, pp. 1-53.