Final exam: Tuesday (19 Feb) 8:00, LH 801
This is a half credit course running through Jan-Feb 2019.
Prerequisite. A pass grade in ToC
Lectures will take place from 9:10-10:25 on Tuesdays, Wednesdays and Thursdays in LH 801.
Registration on moodle is compulsory, as important announcements regarding the course will be mailed via moodle to the registered participants.
References:
[1] Tutorial (slides) by Paul Gastin
[2] Lecture notes by Benedikt Bollig and Marc Zeitoun
[3] Lecture notes by Manfred Droste and Dietrich Kuske
| Date | Descr | Topics covered | Resources/materials |
|---|---|---|---|
| 3/1/2019 | Lecture 1 |
examples of weighted automata, examples of semirings.
exercise: design a weighted automaton that computes the length of the smallest a-block using (min,+) semiring. exercise: show that the n X n matrices over a semiring with matrix addition and multiplication forms a semiring. |
Lecture 1 (scribe: Agnishom Chattopadhyay) |
| 8/1/2019 | Lecture 2 | more examples of weighted automata -- computing number of a's in a word over natural semiring, and over tropical semiring. word evaluation problem. Matrix representation of a weighted automaton efficient algorithm for word evaluation problem | Lecture 2 (scribe: Agnishom Chattopadhyay) |
| 10/1/2019 | Lecture 3 | efficient solution to the word evaluation problem via matrix representation Using matrix representation to prove that an automaton computes a designated function Support language Support non-emptiness decidable (graph reachability) if the semiring is zero-sum-free. | Lecture 3 (scribe: Agnishom Chattopadhyay) |
| 16/1/2019 | Lecture 4 |
Reachable vectors. When the semiring is a sub-semiring of a field: Reachability space spanned by the reachable vectors --- Algorithm for computing a basis of the reachability space. Algorithm for support non-emptiness if the semiring is a sub-semiring of a field.Algorithm for equivalence if the semiring is a sub-semiring of a field. |
Lecture 4 (scribe: Agnishom Chattopadhyay) |
| 17/1/2019 | Lecture 5 |
Algorithm for computing a basis of the reachability space. Reduced automaton computing the same weight function. Exercise: Show that Det(Rev(Det(Rev(A)))) yields the minimal DFA of an NFA A. |
Lecture 5 (scribe: Agnishom Chattopadhyay) |
| 29/1/2019 | Lecture 6 | Reduce(Transpose(Reduce(Transpose(A)))) gives the minimal WA for the function (over a field). Equivalence decidable in poly time over fields. in PSPACE over Boolean. Undecidable over Tropical. (proof in next lecture). Threshold languages: There are threshold languages that are not r.e. | Lecture 6 (scribe: Agnishom Chattopadhyay) |
| 30/1/2019 | Lecture 7 | Weighted automata over tropical semiring (distance automata): Equivalence and dominance are undecidable (Krob) | Lecture 7 (scribe: Agnishom Chattopadhyay) |
| 31/1/2019 | Lecture 8 | Probabilistic Automata | Lecture 8 (scribe: Agnishom Chattopadhyay) |
| 6/2/2019 | Lecture 9 | Probabilistic Automata - threshold language regular if isolated cutpoint. | Lecture 9 (scribe: Agnishom Chattopadhyay) |
| 7/2/2019 | Lecture 10 | Probabilistic Automata - undecidability of threshold languages - equivalence decidable |
Lecture 10 (scribe: Agnishom Chattopadhyay) Reference: Chapter 3 of Lecture notes by Benedikt Bollig and Marc Zeitoun |
| 12/2/2019 | Lecture 11 | rational series - monomials, polynomials, sum, Cauchy product, Kleene star. When is a family of series summable? locally finite family of series. Kleene star defined if f is proper. |
Lecture 11 (scribe: Agnishom Chattopadhyay) Reference: Chapter 4 of Lecture notes by Benedikt Bollig and Marc Zeitoun |
| 13/2/2019 | Lecture 12 | A formal power series is rational if and only if it is recognizable. (Kleene-Schutzenberger theorem) |
Lecture 12 (scribe: Agnishom Chattopadhyay) Reference: Chapter 4 of Lecture notes by Benedikt Bollig and Marc Zeitoun |
| 14/2/2019 | Lecture 13 | A formal power series is recognizable if and only if it belongs to a stable finitely generated left-submodule. |
Lecture 13 (scribe: Agnishom Chattopadhyay) Reference: Chapter 4 of Lecture notes by Benedikt Bollig and Marc Zeitoun |