uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Monotonic and downward closed games
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2008 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 18, no 1, 153-169 p.Article in journal (Refereed) Published
Abstract [en]

In an earlier work [Abdulla et al. (2000, Information and Computation, 160, 109127)] we presented a general framework for verification of infinite-state transition systems, where the transition relation is monotonic with respect to a well quasi-ordering on the set of states. In this article, we investigate extending the framework from the context of transition systems to that of games with infinite state spaces. We show that monotonic games with safety winning conditions are in general undecidable. In particular, we show this negative results for games which are defined over Petri nets. We identify a subclass of monotonic games, called downward closed games. We provide algorithms for analysing downward closed games subject to safety winning conditions. We apply the algorithm to games played on lossy channel systems. Finally, we show that weak parity games are undecidable for the above classes of games.

Place, publisher, year, edition, pages
2008. Vol. 18, no 1, 153-169 p.
National Category
Computer Science
URN: urn:nbn:se:uu:diva-10735DOI: 10.1093/logcom/exm062ISI: 000252718100008OAI: oai:DiVA.org:uu-10735DiVA: diva2:38503
Available from: 2007-05-21 Created: 2007-05-21 Last updated: 2011-03-24Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Abdulla, Parosh Aziz
By organisation
Computer Systems
In the same journal
Journal of logic and computation (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 216 hits
ReferencesLink to record
Permanent link

Direct link