BRICS · Contents · Programme

**A BRICS Mini-Course**

**April 29 and 30, 1997**

**Lectures by
Denis Thérien
**

**
**

**I Algebraic theory of automata**-
- transformation semigroup of a DFA
- syntactic semigroup of a language
- varieties of finite semigroups
- Eilenberg theorem
- equational description of varieties

**II Decomposition of finite semigroups**-
- wreath and block product
- Krohn-Rhodes decomposition theorem
- Schutzenberger theorem: L is *-free iff S(L) is aperiodic

**III Logical description of *-free languages**-
- first-order logic
- temporal logic

**IV Regular languages and boolean circuits**-
- which regular languages are complete for NC
^{1} - relating *-free languages and AC
^{0}

- which regular languages are complete for NC

### Tuesday April 29, 1997, 13:15-15:00 in Colloquium B4

### Wednesday April 30, 1997, 13:15-15:00 in Colloquium B4