Algebraic automata theory

Book

Course is based on book "Algebraic automata theory" by W.M. Holcombe. [Google book][djvu][pdf]

Seminars

03.02.10 Sequential machines

Mealy machines, Minimizing Mealy machine, Coverings, Sequential function, Decomposition of sequential function

• [Slides]

13.01.10 Recognizers

Automata, Minimal recognizer, Recognizible set, Syntactic monoid, Rational decomposition of recognizible sets, Prefix decomposition of recongnizible set, The pumping lemma and size of recognisizle set

• [Slides]

09.12.09 Decompositions

Decompositions, Orthogonal partition, General admissible partition, Permutation-reset machines, Group machines

• [Slides]
• Common types of transformation semigroups [Notation]

25.11.09 Composition of State Machines

Mealy machines, Products of Mealy machines, Products of semiautomata, Products of transformation semigroups, Products of incomplete machines

• [Slides]
• Additional reading: Automata-Based Programming [in russian, but some information in english], Unimod [sourceforge.net]

11.11.09 Machines and semigroups

State machines, The semigroup of a state machine, Homomorphisms and quotients, Coverings

• [Slides]
• Additional reading: Some examples are taken from book Gilbert W.J., Nicholson W.K. "Modern algebra with applications" (Chapter 7 "Monoids and machines") [pdf]

20.10.09 Semigroups

Relations, Semigroups and homomorphisms, Products, Groups, Permutation groups.

• [Slides]