Final Exam: on Thursday 27/02/2020 at 15:00 in LH 6
This is a half credit course running through Jan-Feb 2020.
Prerequisite. A pass grade in ToC
Instructor. C. Aiswarya
Teaching Assistant. Ashwani Anand
Grading. Exam during the midsem week, and possible a quiz before.
Lectures will take place from 10:30 to 11:45 on Thursdays and Fridays in LH 6.
Please send an email to C. Aiswarya if you plan to attend this course. Important announcements will be sent via email.
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 |
---|---|---|---|
9/1/2020 | 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. |
|
10/1/2020 | Lecture 2 | more examples of weighted automata -- computing number of a's in a word over tropical semiring. formal description of a Weighted automaton Matrix representation of a weighted automaton | |
10/1/2020 | Problem Set 1 | Submit to Ashwani Anand before Monday 13/1 for feedback | Problem Set 1 |
16/1/2020 | 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 language can be non-regular. Support non-emptiness decidable (graph reachability) if the semiring verifies 1) (s1+s2 = 0 => s1=0 and s2=0) and 2) (s1s2=0 => s1=0 or s2=0). | |
17/1/2020 | 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. |
|
17/1/2020 | Problem Set 2 | Submit to Ashwani Anand before Monday 20/1 for feedback | Problem Set 2 |
23/1/2020 | Lecture 5 |
Reduced automaton. Minimizing an automaton. |
|
24/1/2020 | Lecture 6 |
Dominance problem is undecidable for tropical automata (Z, min, +) |
|
24/1/2020 | Problem Set 3 | Submit to Ashwani Anand before Monday 27/1 for feedback | Problem Set 3 |
30/1/2020 | Lecture 7 |
Dominance problem is undecidable for tropical automata (Z, min, +) Equivalence problem is undecidable for tropical automata (Z, min, +) Equivalence problem is undecidable for tropical automata (N, min, +) Dominance problem is undecidable for tropical automata (N, min, +) Threshold languages: There are threshold languages that are not r.e. |
|
6/2/2020 | Lecture 8 | Guest Lecture by Amaldev Manuel on the limitedness problem and boundedness problem of distance automata. | |
7/2/2020 | Lecture 9 | Probabilistic Auotomata .. stochastic matrices closed under product.. support effectively regular. Value 1 effectively regular. threshold langauges need not be r.e... threshold langauge regular if the threshols is an isolated cutpoint. proof in next class |
Lecture notes by Benedikt Bollig and Marc Zeitoun, Chapter 3 |
7/2/2020 | Problem Set 4 | Submit to Ashwani Anand before Monday 10/2 for feedback | Problem Set 4 |
13/2/2020 | Lecture 10 | Probabilistic Auotomata. threshold langauge regular if the threshols is an isolated cutpoint. proof |
Lecture notes by Benedikt Bollig and Marc Zeitoun, Chapter 3 |
13/2/2020 | Lecture 10 | Probabilistic Auotomata. value half problem is undecidable. proof |
Lecture notes by Benedikt Bollig and Marc Zeitoun, Chapter 3 |
17/2/2020 | Problem Set 5 | Submit to Ashwani Anand for feedback | Problem Set 5 |
19/2/2020 | Lecture 11 | monomilas, polynomials, series, Rational series, Recognizable series. Kleene-Schutzenberger theorem : Rational = Recognizable |
Lecture notes by Benedikt Bollig and Marc Zeitoun, Chapter 4 |
20/2/2020 | Lecture 12 | Myhill-Nerode analogue for Weighted automata: A series is recognizable iff it belongs to a stable, finitely generated left submodule. |
Lecture notes by Benedikt Bollig and Marc Zeitoun, Chapter 4 |