#
PřF:M7250 Semigroups and formal lang. - Course Information

## M7250 Semigroups and formal languages

**Faculty of Science**

Autumn 2019

**Extent and Intensity**- 2/0. 2 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).
**Teacher(s)**- doc. Mgr. Michal Kunc, Ph.D. (lecturer)
**Guaranteed by**- doc. Mgr. Michal Kunc, Ph.D.

Department of Mathematics and Statistics - Departments - Faculty of Science

Contact Person: doc. Mgr. Michal Kunc, Ph.D.

Supplier department: Department of Mathematics and Statistics - Departments - Faculty of Science **Timetable**- Mon 10:00–11:50 M3,01023
**Prerequisites**- Algebra I.

Recommended knowledge: Formal languages and automata I, basics of universal algebra (Algebra II) and metric spaces (Mathematical analysis II). **Course Enrolment Limitations**- The course is also offered to the students of the fields other than those the course is directly associated with.
**fields of study / plans the course is directly associated with**- Algebra and Discrete Mathematics (programme PřF, N-MA)

**Course objectives**- The course presents two closely related areas of theoretical computer science and mathematics: theory of regular languages and finite semigroups.
**Learning outcomes**- After passing the course, students will: be familiar with modern methods of the theory of regular languages; understand the connection between classes of regular languages and finite semigroups; be able to use pseudovarieties of semigroups to describe properties of regular languages; master basic notions and techniques of the structure theory of finite semigroups.
**Syllabus**- 1. Recognizable and rational sets: definitions, relations between them, closure properties.
- 2. Structure of finite semigroups: Green's relations, 0-simple semigroups, factorization forests.
- 3. Eilenberg correspondence: pseudovarieties, pseudoidentities, examples.
- 4. Well quasiorders in formal language theory.

**Literature**- PIN, J.-E.
*Varieties of formal languages*. New York: Plenum Publishing Corporation, 1986. 138 pp. Foundations of Computer Science. ISBN 0-306-42294-8. info - SAKAROVITCH, Jacques.
*Elements of Automata Theory*. Cambridge: Cambridge University Press, 2009. 782 pp. ISBN 978-0-521-84425-3. info *Handbook of formal languages. Vol. 1 Word, language, grammar*. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer, 1997. xvii, 873. ISBN 3-540-60420-0. info- HOWIE, John M.
*Fundamentals of semigroup theory*. Oxford: The Clarendon Press, 1995. x, 351. ISBN 0198511949. info - GRILLET, Pierre Antoine.
*Semigroups : an introduction to the structure theory*. New York: Marcel Dekker, 1995. ix, 398. ISBN 0824796624. info - ALMEIDA, Jorge.
*Finite semigroups and universal algebra*. Singapore: World Scientific, 1994. 511 pp. ISBN 81-02-1895-8. info - DE LUCA, Aldo and Stefano VARRICCHIO.
*Finiteness and regularity in semigroups and formal languages*. Berlin: Springer, 1999. 240 pp. EATCS Monographs on Theoretical Computer Science. ISBN 3-540-63771-0. info

- PIN, J.-E.
**Teaching methods**- Lectures: theoretical explanation, homework exercises.
**Assessment methods**- Oral examination.
**Language of instruction**- Czech
**Further Comments**- Study Materials

The course is taught once in two years. **Teacher's information**- https://www.math.muni.cz/~kunc/vyuka/vyuka.html

- Enrolment Statistics (recent)

- Permalink: https://is.muni.cz/course/sci/autumn2019/M7250