Semigroups, Automata and Languages
Code
10833
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Alan James Cain, Vitor Hugo Bento Dias Fernandes
Total hours
71
Teaching language
Português
Objectives
Provide a basic introduction to the Theory of Semigroups, make an elementary study, mathematically rigorous, of some topics of the Theory of Computation, in particular of Finite Automata and Regular Languages, and also providing the bridges that connect these two areas of knowledge.
Prerequisites
Elementary group theory: subgroups, cosets, factor groups, and homomorphisms.
Subject matter
1. Basics
2. Green''s Relations
3. Regular semigroups, including 0-simple semigroups and the Rees-Suschkewitsch Theorem
4. Inverse Semigroups: an introduction
5. Languages. Rational languages and finite automata
6. Grammars: a brief introduction. Regular grammars
7. Transition monoid and syntactic monoid
8. Pseudovarieties of semigroups and varieties of rational languages: a brief introduction
Bibliography
1. J.M. Howie, Automata and Languages, Oxford Univ. Press, 1991.
2. J.M. Howie, Fundamentals of semigroup theory, Oxford Univ. Press, 1995.
3. J.E. Pin, Varieties of formal languages, Plenum, 1986.
4. M.V. Lawson, Finite Automata, Chapman & Hall/CRC, 2003.
5. The GAP Group, GAP - Groups, Algorithms, and Programming,
2008, http://www.gap-system.org.
Teaching method
Classes consist of oral explanation of the theory and of solving problems.
If the number of students is less than 5, classes will be tutorial. The student prepares the contents of each chapter using the specific bibliography indicated and solves related problems.
Evaluation method
Continuous evaluation: 3 sets of problems to answer (each 1/3 of the final grade).