10833 Semigroups, Automata, and Languages

Contents

  1. Summary
  2. Lecture notes
  3. Textbooks
  4. Links

1. Summary

The aim of this course is to provide a basic introduction to the theory of semigroups, to make an elementary, mathematically rigorous, study of some topics of the theory of computation, in particular of finite automata and regular languages, and also to examine the bridges that connect these two areas of knowledge.

2. Lecture notes

The course will use selected material from the lecture notes ‘Nine Chapters on the Semigroup Art’, together with a supplement dicussing automata and regular languages in greater depth.

Nine Chapters on the Semigroup Art
[ version 0.66.2 (2017-11-07)  ]
For this course, the relevant parts are the following:
Chapter 1: Elementary semigroup theory
Chapter 3: Structure of semigroups
Not including the sections ‘Properties of free semigroups’ or ‘Semigroup presentations’.
Not including any exercises.
Chapter 3: Structure of semigroups
Not including the section ‘Schützenberger groups’.
Not including Exercises 3.9 and 3.11.
Chapter 4: Regular semigroups
Chapter 5: Inverse semigroups
Not including the material on the word problem in the free inverse monoid (p. 97ff).
[A supplement on semigroups, automata, and languages]

3. Textbooks

All the material required for the course is included in the lecture notes and supplement. Students may wish to consult the following textbooks for further reading:

J.M. Howie, Automata and Languages
Oxford Science Publications. New York: Clarendon Press, Oxford University Press (1991). ISBN: 0-19-853424-8.
J.M. Howie, Fundamentals of Semigroup Theory
no. 12 in London Mathematical Society Monographs (New Series). New York: Clarendon Press, Oxford University Press (1995). ISBN: 0-19-851194-9.
J.-E. Pin, Varieties of formal languages
Foundations of Computer Science. New York: Plenum Publishing (1986). ISBN: 0-306-42294-8.
M.V. Lawson, Finite Automata
Boca Raton, FL: Chapman & Hall/CRC (2004). ISBN: 1-58488-255-7.