Chennai Mathematical Institute


3.30 p.m., 3.30 p.m., 2.00 p.m.
Automata and Logics for Data Languages

Amaldev Manuel

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.