time becomes data on the other side of the mirror

Speaker(s)

Piotrek Hofman

Affiliation

Uniwersytet Warszawski

Date

June 2, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Timed automata and register automata are well-known  models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers
that may store data values for later comparison. Although these two models behave in appearance  differently, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata
with one clock or register, both with non-primitive recursive complexity. This is not by chance.

There is indeed a tight relationship between the two models. I will show that a run of a timed automaton can be simulated by a register automaton, and conversely that a run of a register automaton can be simulated by a timed automaton. These results allow to transfer  complexity and decidability results back and forth between these two kinds of models.

This is joint work with Diego Figueira and Sławek Lasota.

 

 

---