LFCS Seminar: Jari Stenman
Timed Pushdown Automata
What 


When 
Jan 29, 2013 from 04:00 PM to 05:00 PM 
Where  IF 2.33 
Add event to calendar 
vCal iCal 
Pushdown automata and timed automata are two widely used models for recursive systems and systems with timed behaviour, respectively. In this talk, I present the model of timed pushdown automata (TPDA), which subsumes both pushdown automata and timed automata. A TPDA is a pushdown automaton equipped with a set of realvalued clocks. Additionally, each symbol in the stack is enriched with a real number representing its age. Despite the fact that we have two dimensions of infiniteness, reachability is decidable (EXPTIMEcomplete) for this model. A large part of the talk is devoted to showing how one can simulate TPDA with (untimed) pushdown automata.