Übung zur Algebraischen Automatentheorie im Sommersemester 2012

Termine

Vorlesung

Übung

Übungsblätter

In der Regel gibt es für jedes Übungsblatt eine Woche Arbeitszeit. Die Antworten zur Aufgaben sollen begründet werden. Sie sollen in der Lage sein, Ihre Lösungen zu erklären.

Abgabe der H-Aufgaben: am Anfang der Vorlesung eine Woche vor der Übung oder an meine E-Mail-Adresse bis zu diesem Zeitpunkt.

Bitte vorbereiten Sie auch die S-Aufgaben für die Übung!

  1. Monoide und Halbgruppen (PDF), Abgabe bis 7. Mai.
  2. Semidirektes Produkt und Blockprodukt (PDF), Abgabe bis 21. Mai.
  3. Transformationsmonoide, Kranzprodukt (PDF), Abgabe bis 4. Juni.
  4. Einfache Zerlegungen (PDF), Abgabe bis 18. Juni.
  5. Verschiedene Zerlegungen (PDF), Abgabe bis 2. Juli.

Literatur

  1. Howard Straubing, Finite automata, formal logic, and circuit complexity, Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1994. ISBN: 0-8176-3719-2

    Die Hauptquelle der Vorlesung.

  2. Zoltán Ésik, A proof of the Krohn–Rhodes Decomposition Theorem, Theor. Comput. Sci. 234 (2000) 1–2, 287–300

    Ein alternativer Beweis des Satzes von Krohn–Rhodes.

  3. Ein kurzer Beweis des Satzes von Krohn–Rhodes und die Quelle für die Aufgaben H 1-2, H 3-3, H 4-1 und H 5-2.

Prüfung

Zur mündlichen Prüfung zugelassen sind alle, die 50% der H-Aufgaben richtig lösen. Besseres Ergebnis sowie aktive Teilnahme werden positiv bewertet.


Gábor Braun
Johannisgasse 26, Zi 4-39
Tel: (0)341-97-32202
gabor DOT braun AT informatik DOT uni-leipzig DOT de