M7250 Pologrupy a formální jazyky

Přírodovědecká fakulta
podzim 2011 - akreditace

Údaje z období podzim 2011 - akreditace se nezveřejňují

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.
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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 2010 - akreditace, podzim 2010, podzim 2012, podzim 2014, podzim 2017, podzim 2019.