Algebraic automata theory


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


03.02.10 Sequential machines

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

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

09.12.09 Decompositions

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

25.11.09 Composition of State Machines

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

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.