|Automata and Formal Languages 2013/14|
|News | Dates | Grading | Content | Exercises | Exam | Material|
10.03.2014The 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.2014The inspection of the written exam (Klausureinsicht) will be on March 3rd at 2pm in room 03.11.051.
5.02.2014Contents of today's lecture: Carton-Michel automata (part 2)
3.02.2014Contents of today's lecture: Carton-Michel automata aka strongly unambiguous automata (part 1)
31.01.2014Exercise sheet 11 is online. We also provided solutions to selected exercises.
28.01.2014The lecture notes now include Angluin's learning algorithm.
27.01.2014Contents 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.2014Exercise sheet 10 is online.
23.01.2014Contents of today's lecture: Safra's construction (part 2), order vectors with hits
23.01.2014There 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.2014Contents of today's lecture: Transformations between the various acceptance conditions, Safra's construction (part 1)
20.01.2014Contents of today's lecture: Klarlund's construction (part 2), other acceptance conditions for automata over infinite words
17.01.2014Exercise sheet 9 is online.
15.01.2014The lecture notes now include Hopcroft's minimization algorithm. I also put some German notes regarding omega-regular languages online.
15.01.2014Contents of today's lecture: Complementing Büchi automata using Klarlund's construction (part 1)
13.01.2014Contents of today's lecture: Complexity of Hopcroft's minimization algorithm, Michel's lower bound for complementing Büchi automata
12.01.2014Exercise sheet 8 is online.
8.01.2014Contents of today's lecture: Hopcroft's minimization algorithm, its correctness, implementation details
2.01.2014Exercise sheet 7 is online.
23.12.2013A small update of the lecture notes is online.
23.12.2013Today is no lecture. We will make up for it in 2014.
19.12.2013Contents of today's lecture: an application of Angluin's L*-algorithm to learning some Boolean functions, MSO logic over infinite words
18.12.2013Contents 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.2013The Hopcroft-Karp equivalence test for deterministic automata is now included in the lecture notes.
11.12.2013Some algorithms are now included in the lecture notes.
11.12.2013Contents 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.2013Exercise sheet 6 is online.
9.12.2013Contents 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.2013Contents 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.2013Exercise sheet 5 is online.
21.11.2013Exercise 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.2013The chapter on Kleene's Theorem is online.
12.11.2013The remainder of the chapter on rational sets is online.
11.11.2013The first half of the chapter on rational sets is online (see lecture notes).
05.11.2013Moore's algorithm is now included in the lecture notes.
04.11.2013The first part of the lecture notes is online.
30.10.2013The third exercise sheet is online.
28.10.2013The second exercise sheet is online.
23.10.2013The first exercise sheet is online.
22.10.2013I prepared a quick repetition of basic notation.
08.10.2013The 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.