Lossy Machines

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.