Universal Algebra, Semigroup Theorym and Automata are fields of mathematics that have seen rapid development in the last 30 years, in part due to their use in the theoretical description of computational systems. This UC aims to develop competencies in the areas of Universal Algebra, Semigroup Theory and Automata. In the case of Automata, the emphasis will be on their use as mathematical tool for the theoretical treatment of computation.
Upon completion of this curricular unit, the student must be able to:
- describe the objects and elementary results of semigroup theory and universal algebra;
- solve problems involving the calculation and manipulations of Green’s relations for a given semigroup, and the corresponding inverse problem (ie. find semigroups with prescribed relations);
- state and prove Rees' theorem;
- state and prove Birkhoff's theorem on varieties, and relate Birkhoff's theory to the most common problems in equational logic;
- describe automata and their relationship to semigroups and the theory of computation.
Universal Algebra. Birkhoff’s Theorem for varieties of algebras.
Semigroup Theory: Green’s relations, basic results about regular, completely-0-simple, and inverse semigroups.
Automata Theory. Connections between Automata, Semigroups, Computability and Complexity.
1. Stanley Burris, H.P.Sankappanavar, A First Course in Universal Algebra, free online addition, 2022.
2. John M. Howie, Fundamentals of Semigroup Theory, London Mathematical Society Monographs, New Series vol. 12, Oxford University Press, Oxford, 1996.
3. W. J. Gilbert, W. K. Nicholson, Modern Algebra with Applications, Second Edition, John Wiley & Sons, Inc., 2004.
4. M. Sipser, Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, 2006.
Evaluation is made on individual basis and it involves the coexistence of two modes: continuous assessment (60%) and
final evaluation (40%). Further information is detailed in the Learning Agreement of the course unit.