I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Automata and Formal Languages 2013/14

  News | Dates | Grading | Content | Exercises | Exam | Material

10.03.2014

The list for the repetition exam can be found at the room 03.11.044. The repetition exams are oral. Possible dates are March 24th and 25th.

25.02.2014

The inspection of the written exam (Klausureinsicht) will be on March 3rd at 2pm in room 03.11.051.

5.02.2014

Contents of today's lecture: Carton-Michel automata (part 2)

3.02.2014

Contents of today's lecture: Carton-Michel automata aka strongly unambiguous automata (part 1)

31.01.2014

Exercise sheet 11 is online. We also provided solutions to selected exercises.

28.01.2014

The lecture notes now include Angluin's learning algorithm.

27.01.2014

Contents of today's lecture: From deterministic Muller automata to deterministic Rabin and deterministic parity automata, Landweber's characterization of deterministic omega-regular languages

25.01.2014

Exercise sheet 10 is online.

23.01.2014

Contents of today's lecture: Safra's construction (part 2), order vectors with hits

23.01.2014

There will be a lecture from 14:30 to 16:00 in room 03.10.011 (this is the compensation for the skipped lecture on 23.12.2013).

22.01.2014

Contents of today's lecture: Transformations between the various acceptance conditions, Safra's construction (part 1)

20.01.2014

Contents of today's lecture: Klarlund's construction (part 2), other acceptance conditions for automata over infinite words

17.01.2014

Exercise sheet 9 is online.

15.01.2014

The lecture notes now include Hopcroft's minimization algorithm. I also put some German notes regarding omega-regular languages online.

15.01.2014

Contents of today's lecture: Complementing Büchi automata using Klarlund's construction (part 1)

13.01.2014

Contents of today's lecture: Complexity of Hopcroft's minimization algorithm, Michel's lower bound for complementing Büchi automata

12.01.2014

Exercise sheet 8 is online.

8.01.2014

Contents of today's lecture: Hopcroft's minimization algorithm, its correctness, implementation details

2.01.2014

Exercise sheet 7 is online.

23.12.2013

A small update of the lecture notes is online.

23.12.2013

Today is no lecture. We will make up for it in 2014.

19.12.2013

Contents of today's lecture: an application of Angluin's L*-algorithm to learning some Boolean functions, MSO logic over infinite words

18.12.2013

Contents of today's lecture: linked pairs, a characterization of omega-recognizable languages in terms of infinite substitutions, from homomorphims to Büchi automata, decision problems for Büchi automata

18.12.2013

The Hopcroft-Karp equivalence test for deterministic automata is now included in the lecture notes.

11.12.2013

Some algorithms are now included in the lecture notes.

11.12.2013

Contents of today's lecture: the syntactic semigroup is the minimal recognizer, omega-regular = recognizable by finite semigroup, omega-regular languages are closed under complement

9.12.2013

Exercise sheet 6 is online.

9.12.2013

Contents of today's lecture: omega-rational expressions define the omega-regular languages, ultimately periodic words, Ramsey's Theorem for infinite edge-labeled graphs, recognition by homomorphisms, factorization-lemma (using Ramsey's Theorem), Arnold's syntactic congruence, syntactic homomorphism

4.12.2013

Contents of today's lecture: omega-regular languages, Büchi automata, deterministic Büchi automata are weaker than nondeterministic Büchi automata and they are not closed under complement, closure of (deterministic) omega-regular languages under union and intersection, omega-rational expressions

2.12.2013

Exercise sheet 5 is online.

21.11.2013

Exercise sheet 4 is online. The next tutorial will be on Wednesday, November 27th, at 12:00 in HS3 instead of the lecture. The Wednesday lecture will take place on Thursday, November 28th, at 12:15 in 02.13.010 as usually the exercises do.

14.11.2013

The chapter on Kleene's Theorem is online.

12.11.2013

The remainder of the chapter on rational sets is online.

11.11.2013

The first half of the chapter on rational sets is online (see lecture notes).

05.11.2013

Moore's algorithm is now included in the lecture notes.

04.11.2013

The first part of the lecture notes is online.

30.10.2013

The third exercise sheet is online.

28.10.2013

The second exercise sheet is online.

23.10.2013

The first exercise sheet is online.

22.10.2013

I prepared a quick repetition of basic notation.

08.10.2013

The lectures on 14.10 or 16.10 are cancelled. The first lecture will be on Monday, October 21.
October 14 is a welcome day for first-term students. All lectures are cancelled.
The cancellation of the October 16 lecture is due to an administrative problem that prevents the instructor (Dr. Manfred Kufleitner, University of Stuttgart),to start his appointment as invited professor at TUM before the beginning of the term. We apologize for the inconveniences.

01.07.2013

Creation of the website.