Regular and Context-Free Languages: Advanced Results
» Diese Veranstaltung wird auf englisch gehalten.
Lecture in Winter Term 2011/12
| Type | Time/Place | Start | Lecturer |
|---|---|---|---|
| V2 | Mon 14:00–15:30, AH II | 17 October 2011 | Thomas |
| Ü1 | Do 11:45–13:15, 4116 | 20 October 2011 | Thomas Felscher Gelderie |
Preliminary Information:
Contents
This course is addressed to MSc students and diploma students. It offers a deeper understanding of the two essential
language classes that are fundamental in many areas of computer science: the regular and the context-free languages.
Although some of the presented results are quite old, they have not lost their significance. Also some of the oldest
open problems of theoretical computer science belong to this area.
Applications will be mentioned, but the emphasis is on theory, with two main topics:
alternative descriptions of languages in different frameworks, and classification of languages in terms various
views of "complexity".
The course will be given in German if all participants prefer this.
Contents:
- Part I: Regular Languages
- Star-height and the star-height poblem
- Star-free languages, first-order logic and Schützenberger's Theorem
- Regular languages and circuit complexity
-
Part II: Context-Free Languages
- Chomsky-Schützenberger Theorem
- Generators of context-free, linear, and one counter-languages
- Deterministic context-free languages
Credit Points
4 ECTS