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



Schedule

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