We consider lossy counter machines, i.e. counter machines with counters whose contents can spontaneously decrease at any time. They are not Turing-powerful, since reachability is decidable for them, but they still have interesting undecidable properties: For a lossy counter machine it is undecidable if there exists an initial configuration s.t. there is an infinite run. Lossy counter machines can be used as a general tool to show the undecidability of many problems for lossy and non-lossy systems, e.g. verification of lossy FIFO-channel systems, model checking lossy Petri nets, problems for reset and transfer Petri nets, and parametric problems like fairness of broadcast communication protocols.
«
We consider lossy counter machines, i.e. counter machines with counters whose contents can spontaneously decrease at any time. They are not Turing-powerful, since reachability is decidable for them, but they still have interesting undecidable properties: For a lossy counter machine it is undecidable if there exists an initial configuration s.t. there is an infinite run. Lossy counter machines can be used as a general tool to show the undecidability of many problems for lossy and non-lossy system...
»