Sökning: id:"swepub:oai:DiVA.org:uu-10735" >
Monotonic and downw...
Monotonic and downward closed games
-
- Abdulla, Parosh Aziz (författare)
- Uppsala universitet,Datorteknik
-
Bouajjani, Ahmed (författare)
-
d'Orso, Julien (författare)
-
(creator_code:org_t)
- 2007-09-04
- 2008
- Engelska.
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press (OUP). - 0955-792X .- 1465-363X. ; 18:1, s. 153-169
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer science
- Datavetenskap
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas