Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 10, nr 4, 21Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2014. Vol. 10, nr 4, 21
Nyckelord [en]
Stochastic games, Lossy channel systems, Finite attractor, Parity games, Memoryless determinacy
Nationell ämneskategori
Datorsystem
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: diva2:802274
Tillgänglig från: 2015-04-12 Skapad: 2015-04-06 Senast uppdaterad: 2017-12-04Bibliografiskt granskad

Open Access i DiVA

fulltext(223 kB)108 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 223 kBChecksumma SHA-512
b5853e29964e85e252c31df528da33c2b243bf7f35759a8ab4bb355d64e4af8dcacf0c767782de3ecc1e5c7be6b012a6da785af9d361a55a0dbe4b64c85641f0
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Abdulla, Parosh Aziz
Av organisationen
Datorteknik
I samma tidskrift
Logical Methods in Computer Science
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 108 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 482 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf