Petri Games are Monotonic but Dicult to Decide
Jean-François Raskin, Mathias Samuelides, Laurent Van Begin · 2003
In this paper, we study two-player games played on innite but monotonic game structures. We concentrate on coverability games, a natural subclass of reachability games in the context of monotonic game structures. On the negative side, we show that surprisingly, and contrary to the one-player case, coverability is undecidable on two-player mono- tonic game structures. On the positive side, we identify an interesting subclass of two-player monotonic game structures, for which coverability is decidable and for which we can eectiv ely construct winning strate- gies. Furthermore, we show how to dene two-player game structures that belong to that subclass with Petri nets. The results of this paper are compared to recent results obtained independently by Abdulla, Boua- jjani and d'Orso on similar game structures where they identify another subclass of monotonic game structures with decidable results.