Chennai Mathematical Institute


3.30 pm, Seminar Hall
Reductions between one-clock time automata & lossy channel systems

P. Schnoebelen
CNRS, ENS Cachan and Infosys Professor, Chennai Mathematical Institute.


Ouaknine & Worrell [1] and Lasota & Walukiewicz [2] have used reductions between one-clock timed automata (1TA) and lossy channel systems (LCS) used to prove that the universality problem for 1TAs is decidable but as hard as reachability for LCS. The same applies to Alternating 1TAs. The goal of this informal seminar is to look in detail at these reductions and their correctness proofs, saving the audience from actually reading the papers.

[1] J. Ouaknine and J. Worrell. On the language inclusion problem for timed automata: Closing a decidability gap. In Proc. LICS 2004, pages 54--63.

[2] S. Lasota and I. Walukiewicz. Alternating timed automata. ACM Trans. Computational Logic, 9(2), 2008.