Varieties of formal languages

Jean-Éric Pin


This book presents a synthesis of the latest developments in the mathematical theory of data processing. It discusses the fundamental results of the theory of finite automata and of rational languages and examines the recent concept of variety of languages which formalises the connections between finite automata, recognizable languages and finite semigroups.

The first four chapters of the book are devoted to the fundamental results of the theory of automata and are illustrated by numerous examples. The final chapter contains the most recent results of the theory (but without the proof). The reader does not require any previous knowledge of formal languages or automat, although a certain familiarity with algebra is called for.


Preface vii

Foreword ix

Introduction. Relations 1

Chapter 1. Semigroups, languages and automata 5

Chapter 2. Varieties 27

Chapter 3. Structure of finite semigroups 45

Chapter 4. Piecewise-testable languages and star-free languages 79

Chapter 5. Complementary results 99

Bibliographic notes 125

Index 135

prev up

Prev: Livres Up: Home Page

Jean-Eric PIN, 5 Octobre 1996