BRICS · Contents · Programme

Algebraic Theory of Automata, Temporal Logic and Expressiveness

A BRICS Mini-Course
April 29 and 30, 1997

Lectures by
Denis Thérien
School of Computer Science, McGill University, Canada

Course Contents

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 NC1
  • relating *-free languages and AC0

Programme

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

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