3.30 p.m., 3.30 p.m., 2.00 p.m.
Automata and Logics for Data Languages
17-01-12, 19-01-12, 20-01-12
Amaldev Manuel will give a series of 3 lectures on Automata and Logics for Data Languages. The schedule of lectures and the topics to be covered are as follows:
Lecture 1: Tuesday, 17th Jan 2012, 3.30 p.m., Seminar Hall.
Basics: Linear orders, Preorders, Equivalence relations. Extending Buchi-Elgot-Trakhtenbrot theorem to total preorders. Multicounter automata. Shuffle and Permutation of a regular language. Basic undecidability results.
Lecture 2: Thursday, 19th Jan 2012, 3.30 p.m., Seminar Hall.
Examples of data languages. Data Automata. Scott normal form. Proof sketch for logically characterizing Data automata. Decidability of emptiness of data automata.
Lecture 3: Friday, 20th Jan 2012, 2.00 p.m., Seminar Hall.
Ordered Data words: Examples of ordered data languages. Ordered Data Automata (ODA). Logical characterization of ODA. Decidability of ODA.