Applied Automata Theory

» Diese Veranstaltung wird auf englisch gehalten.

Lecture in summer term 2004

V4 Thu 14:00h-15:30h AH I
Tue 16:00 - 17:30 AH I
20.04.2004 Thomas
Ü2 Wed 10:00 - 11:30 AH II Rohde


In this advanced course of theoretical computer science, fundamental models of automata as used in the practice of computer science are introduced and analyzed.

We present basic results on the following questions: How to minimize an automaton? How to transform one form of automaton into another? How to switch from logical spezifications to state-based specifications? Which problems (e.g., reachability of given states, existence of successful runs, equivalence of automata) are decidable or even efficiently decidable?

Among the models to be discussed are pushdown systems, communicating finite-state machines, Petri nets, Message Sequence Charts, Hierarchical finite-state machines.

Previous Knowledge:

Basic knowledge of automata theory as presented in basic courses is required for participation.

Curriculum Relevance:

By passing the final written examination we issue an "Übungsschein" or credit points, respectively.


To obtain an Übungsschein or the credit points for this course students have to meet the following requirements:
  1. Obtain 50% of the points from the exercises.
  2. Pass the final exam.
The final exam consists of a written exam. Students who gain enough points from the exercises, and fail the written exam or do not take part in the written exam are eligible for a (written or oral) reexamination. Students who didn't hand in exercises can participate in the written exam. They will however not be eligible for an Übungsschein or credit points, even if they pass the exam.

Credit Points: