Jean-Éric Pin

 Variétés de langages formels

 Masson, Paris, 1984.

 

 Varieties of formal languages

 North Oxford, London and Plenum, New-York, 1986.

Presentation

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.

Contents

Preface vii

Foreword ix

Introduction. Relations 1

Chapter 1. Semigroups, languages and automata 5

1 Semigroups 5

1.1 Semigroups, monoids, morphisms 5
1.2 Idempotents, zero, ideal 6
1.3 Congruences 7
1.4 Semigroups of transformations 9
1.5 Free semigroups 10

2. Languages 12

2.1 Words 12
2.2 Automata 12
2.3 Rational and recognizable languages 13
2.4 Syntactic monoids 17
2.5 Codes 18
2.6 The case of free semigroups 20

3. Explicit calculations 20

3.1 Syntactic semigroups of L = A^*abaA^* over the alphabet A = {a, b} 21
3.2 The syntactic monoid of L = {a², ab, ba}^* over the alphabet A = {a, b} 23

Problems 24

Chapter 2. Varieties 27

1 Varieties of semigroups and monoids 27

1.1 Definitions and examples 27
1.2 Equations of a variety 28

2 The variety theorem 31

3 Examples of varieties 35

Problems 42

Chapter 3. Structure of finite semigroups 45

1 Green's relations 45

2 Practical computations 52

3 The Rees semigroup and the structure of regular D-classes 61

4 Varieties defined by Green's relations 65

5 Relational morphisms and V-morphisms 67

Problems 75

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

1 Piecewise-testable languages ; Simon's theorem 79

2 Star-free languages; Schützenberger's theorem 79

3 R-trivial and L-trivial languages 93

Problems 96

Chapter 5. Complementary results 99

1 Operations 99

1.1 Operations on languages 99
1.2 Operations on monoids 103
1.3 Operations on varieties 107

2 Concatenation hierarchies 113

2.1 Locally testable languages 113
2.2 General results on concatenation hierarchies 114
2.3 Straubing's hierarchy 114
2.4 Brzozowski's hierarchy 116
2.5 Connection between teh hierarchies of Straubing and Brzozowski 117
2.6 The group-languages hierarchy 117
2.7 Hierarchies and symbolic logic 118

3 Relations with the theory of codes 120

3.1 Restriction of the operations star and plus 120
3.2 Varieties described by codes 122
3.3 Return to the operation V * W 122

4 Other results and problems 122

4.1 Congruences 122
4.2 The lattice of varieties 122

Bibliographic notes 125

Index 135