PřF:M7250 Semigroups and formal lang. - Course Information
M7250 Semigroups and formal languages
Faculty of ScienceAutumn 2012
- 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. RNDr. Libor Polák, CSc.
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 12:00–13: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)
- Algebra, Number Theory and Mathematical Logic (Eng.) (programme PřF, D-MA4)
- Algebra, Number Theory and Mathematical Logic (programme PřF, D-MA4)
- Course objectives
- The course presents two closely related areas of theoretical computer science and mathematics: theory of regular languages and finite semigroups. After passing the course, students should: 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
- 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.
- Enrolment Statistics (Autumn 2012, recent)
- Permalink: https://is.muni.cz/course/sci/autumn2012/M7250