M7250 Pologrupy a formální jazyky

Přírodovědecká fakulta
podzim 2014
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. RNDr. Libor Polák, CSc.
Ú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
Pá 8:00–9:50 B204
Předpoklady
Algebra I.
Doporučená znalost: Formální jazyky a automaty I, základy univerzální algebry (Algebra II) a teorie metrických prostorů (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. Po absolvování kurzu by studenti měli: být 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; být 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.
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 2017, podzim 2019, podzim 2021, podzim 2024.