Finite semigroups and recognizable languages : an introduction

J-E. PIN

IBP-Litp 1994/15: Rapport de Recherche Litp / Litp research reports
32 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Finite semigroups and recognizable languages : an introduction

Résumé : Il s'agit d'un article de synthèse sur les automates finis et les langages reconnaissables. Il est destiné principalement aux mathématiciens qui connaissent un peu la théorie des semigroupes mais qui n'ont aucune connaissance en théorie des automates et des langages. Les sujets traités dans cet article couvrent le théorème de Kleene, l'équivalence entre automates finis et semigroupes, les différentes hiérarchies de langages (hiérarchies de concaténation, hauteur d'étoile, etc.), la caractérisation syntactique des langages sans-étoile, les langages testables par morceaux et localement testables, le théorème des variétés d'Eilenberg et un aperçu des résultats récents.

Abstract : This paper is a survey on finite automata and recognizable languages. It is written for the mathematician who has a background in semigroup theory but knows next to nothing on automata and languages. The topics covered in this paper include Kleene's theorem, the equivalence between finite automata and finite semigroups, the various hierarchies of languages (dot-depth, star-height, etc.), the syntactic characterization of the star-free , the piecewise testable and the locally testable languages, Eilenberg's variety theorem and a quick review of some more recent developments.

Publications internes Litp 1994 / Litp research reports 1994