uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Stochastic Parity Games on Lossy Channel Systems
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
2014 (engelsk)Inngår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 10, nr 4, artikkel-id 21Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

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.

sted, utgiver, år, opplag, sider
2014. Vol. 10, nr 4, artikkel-id 21
Emneord [en]
Stochastic games, Lossy channel systems, Finite attractor, Parity games, Memoryless determinacy
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-248657DOI: 10.2168/LMCS-10(4:21)2014ISI: 000350399900001Arkivnummer: 10.2168/LMCS-10OAI: oai:DiVA.org:uu-248657DiVA, id: diva2:802274
Tilgjengelig fra: 2015-04-12 Laget: 2015-04-06 Sist oppdatert: 2017-12-04bibliografisk kontrollert

Open Access i DiVA

fulltext(223 kB)144 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 223 kBChecksum SHA-512
b5853e29964e85e252c31df528da33c2b243bf7f35759a8ab4bb355d64e4af8dcacf0c767782de3ecc1e5c7be6b012a6da785af9d361a55a0dbe4b64c85641f0
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekst

Personposter BETA

Abdulla, Parosh Aziz

Søk i DiVA

Av forfatter/redaktør
Abdulla, Parosh Aziz
Av organisasjonen
I samme tidsskrift
Logical Methods in Computer Science

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 144 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 1259 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf