M7250 Pologrupy a formální jazyky

Přírodovědecká fakulta
podzim 2021
Rozsah
2/0. 2 kr. (příf plus uk k 1 zk 2 plus 1 > 4). Ukončení: zk.
Vyučující
doc. Mgr. Michal Kunc, Ph.D. (přednášející)
Garance
doc. Mgr. Michal Kunc, Ph.D.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. Mgr. Michal Kunc, Ph.D.
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
St 16:00–17:50 MS1,01016
Předpoklady
M2150 Algebra I nebo MV008 Algebra I.
Doporučená znalost: IB005 Formální jazyky a automaty, základy univerzální algebry (M7350 Algebra III nebo MA009 Algebra II) a teorie metrických prostorů (M2100 Matematická analýza II).
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Přednáška seznamuje se dvěma úzce svázanými oblastmi teoretické informatiky a matematiky, s teorií regulárních jazyků a konečných pologrup.
Výstupy z učení
Po absolvování kurzu studenti budou: seznámeni s moderními metodami teorie regulárních jazyků; rozumět vztahu mezi třídami regulárních jazyků a konečných pologrup; schopni použít pseudovariety pologrup k popisu vlastností regulárních jazyků; ovládat základní pojmy a techniky strukturní teorie konečných pologrup.
Osnova
  • 1. Rozpoznatelné a racionální množiny: definice, vztahy mezi nimi, uzávěrové vlastnosti.
  • 2. Struktura konečných pologrup: Greenovy relace, 0-jednoduché pologrupy, faktorizační lesy.
  • 3. Eilenbergova korespondence: pseudovariety, pseudoidentity, příklady.
  • 4. Dobrá předuspořádání v teorii formálních jazyků.
Literatura
  • PIN, J.-E. Varieties of formal languages. New York: Plenum Publishing Corporation, 1986, 138 s. Foundations of Computer Science. ISBN 0-306-42294-8. info
  • SAKAROVITCH, Jacques. Elements of Automata Theory. Cambridge: Cambridge University Press, 2009, 782 s. 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 s. ISBN 81-02-1895-8. info
  • DE LUCA, Aldo a Stefano VARRICCHIO. Finiteness and regularity in semigroups and formal languages. Berlin: Springer, 1999, 240 s. EATCS Monographs on Theoretical Computer Science. ISBN 3-540-63771-0. info
Výukové metody
Přednáška: teoretická výuka, domácí cvičení.
Metody hodnocení
Ústní zkouška.
Informace učitele
https://www.math.muni.cz/~kunc/vyuka/vyuka.html
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2010 - akreditace, podzim 2010, podzim 2011 - akreditace, podzim 2012, podzim 2014, podzim 2017, podzim 2019, podzim 2024.