Selected Chapters in Theoretical Informatics

Guarantee:  Doc. RNDr. Alice Kelemenová, CSc.

Goal:
The goal of the course is to make students familiar with the classical subfields of theoretical informatics, mainly formal languages and automata theory, computability theory, complexity theory, as well as to present them the most recent trends in these areas. Finishing the course will enable the basic orientation in the area and the possibility of gaining from the acquired knowledge in they research.

Syllabus

Formal language. Motivation, operations.
Formal machines.
Turing machine. Its modifications (number of tapes, number of heads and direction of their movement). Nondeterminism. Push-down automaton. Final automaton.
Formal grammars. Sequential grammars, parallel grammars, controlled derivation in grammars.
Computational power of automata and grammars.
Complexity of languages. Computational and descriptive complexity.
Co-operative and distributed systems.
Biologically motivated machines and grammars. Cellular automaton, L systems, P systems, eco-grammatic systems.

Literature:
1. D.P. Bovet, P. Crescenzi: Introduction to the theory of complexity. Prentice Hall, 1994
2. E. Csuhaj-Varjú, J. Dassow, J. Kelemen, G. Păun: Grammar systems: A grammatical approach to distribution and cooperation. Gordon and Breach, Yverdon, 1994
3. J. Dassow, G. Paun: Regulated rewriting in formal language theory. Springer Verlag, 1989
4. J. Gruska: Foundation of computing. Thomson 1997
5. G. Rozenberg, A. Salomaa: The mathematical theory of L systems. Academic Press, 1980
6. G. Rozenberg, A. Salomaa (eds.): Handbook of formal languages, Springer Verlag, Berlin, 1997
7. D.A. Simovici, R.L. Tenney: Theory of formal languages with applications. World Scientific, 1999