MPFSG Profinite Semigroups and Their Applications in Computer Science

Přírodovědecká fakulta
podzim 2011
Rozsah
2/0. 1 kr. Ukončení: k.
Vyučující
prof. Jorge Manuel Meneses Guimaräes de Almeida (přednášející)
doc. Mgr. Ondřej Klíma, Ph.D. (pomocník)
Garance
doc. RNDr. Libor Polák, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. Mgr. Ondřej Klíma, Ph.D.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Osnova
  • Abstract: Finite semigroups appear naturally in Computer Science, namely as syntactic semigroups of regular languages, transition semigroups of finite automata, or as finite recognizing devices on their own. Eilenberg's correspondence theorem gives a general framework for the classification of regular languages through algebraic properties of their syntactic semigroups. Here is the resulting typical problem on the algebraic side: a recursively enumerable set R of finite semigroups is given and one wishes to decide whether a given finite semigroup is a homomorphic image of a subsemigroup of a finite product of members of R. Since such a problem is often undecidable, special techniques have been devised to handle special cases. Relatively free profinite semigroups turn out to be quite useful in this context. They play the role of free algebras in Universal Algebra, capturing in their algebraic-topological/metric structure combinatorial properties of the corresponding classes of languages. The aim of this short course is to introduce reltively free profinite semigroups and to explore two topics in which there have been significant recent developments, namely the separation of a given word from a given regular language by a regular language of a special type (for instance, a group language), and connections with symbolic dynamics.
  • Tentative syllabus and preliminary references:
  • 1. Relatively free profinite semigroups. (1 lecture)
  • Reference: [1] J. Almeida, Profinite semigroups and applications, in "Structural Theory of Automata, Semigroups, and Universal Algebra", V. B. Kudryavtsev and I. G. Rosenberg (eds.), Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra (Montréal, Québec, Canada, 7-18 July 2003), Springer, New York, 2005, pp. 1-45.
  • 2. Separating words and regular languages. (2 lectures)
  • Reference: [2] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata, Int. J. Algebra and Comput. 11 (2001) 405-455.
  • 3. Relatifely free profinite semigroups and Symbolic Dynamics. (2 lectures)
  • Reference: [1] (see above).
Vyučovací jazyk
Angličtina
Informace učitele
http://cmup.fc.up.pt/cmup/jalmeida/index.html
Finalni verze clanku [1] a [2] nejsou dostupne zdarma. Nicmene predbezne verze jsou ke stazeni ze stranek autoru. Clanek [1] lze nalezt jako polozku 40 na uvedenych strankach profesora J. Almeidy. Clanek [2] je napriklad zverejnen jako polozka 43 na strance profesora P.Weila http://www.labri.fr/perso/weil/publications/
Další komentáře
Studijní materiály
Předmět je vyučován jednorázově.
Výuka probíhá blokově.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/podzim2011/MPFSG