Lossy Machines

Prelegent(ci)

Sławomir Lasota

Afiliacja

Uniwersytet Warszawski

Termin

5 marca 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

FIFO- and counter-automata are Turing complete models. I will present a weakening of these models, allowing for spontaneous and non-controllable loss of messages from FIFO (or, respectively, decrements of counters). I will discuss how much this weakening decreases complexity of verification problems, like reachability, termination, equivalence and model-checking.

---