MPFSG Profinite Semigroups and Their Applications in Computer Science

Faculty of Science
Autumn 2011
Extent and Intensity
2/0. 1 credit(s). Type of Completion: k (colloquium).
Teacher(s)
prof. Jorge Manuel Meneses Guimaräes de Almeida (lecturer)
doc. Mgr. Ondřej Klíma, Ph.D. (assistant)
Guaranteed by
doc. RNDr. Libor Polák, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: doc. Mgr. Ondřej Klíma, Ph.D.
Course Enrolment Limitations
The course is offered to students of any study field.
Syllabus (in Czech)
  • 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).
Language of instruction
English
Further comments (probably available only in Czech)
Study Materials
The course is taught only once.
The course is taught: in blocks.
Teacher's information
http://cmup.fc.up.pt/cmup/jalmeida/index.html
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2011/MPFSG