Stochastic Parity Games on Lossy Channel Systems [Elektronisk resurs]
-
Abdulla, Parosh Aziz (författare)
-
Clemente, Lorenzo (författare)
-
Mayr, Richard (författare)
-
Sandberg, Sven (författare)
-
Uppsala universitet Teknisk-naturvetenskapliga vetenskapsområdet (utgivare)
- 2014
- Engelska.
-
Ingår i: Logical Methods in Computer Science. - 1860-5974. ; 10:4
-
Läs hela texten
-
Läs hela texten
-
Läs hela texten
Sammanfattning
Ämnesord
Stäng
- We give an algorithm for solving stochastic parity games with almost-sure winning conditions on lossy channel systems, under the constraint that both players are restricted to finitememory strategies. First, we describe a general framework, where we consider the class of 21/2-player games with almost-sure parity winning conditions on possibly infinite game graphs, assuming that the game contains a finite attractor. An attractor is a set of states (not necessarily absorbing) that is almost surely re-visited regardless of the players' decisions. We present a scheme that characterizes the set of winning states for each player. Then, we instantiate this scheme to obtain an algorithm for stochastic game lossy channel systems.
Ämnesord
- Engineering and Technology (hsv)
- Electrical Engineering, Electronic Engineering, Information Engineering (hsv)
- Computer Systems (hsv)
- Teknik och teknologier (hsv)
- Elektroteknik och elektronik (hsv)
- Datorsystem (hsv)
Indexterm och SAB-rubrik
- Stochastic games
- Lossy channel systems
- Finite attractor
- Parity games
- Memoryless determinacy
Inställningar
Hjälp
Beståndsinformation saknas