This HTML5 document contains 48 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n18http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n15http://purl.org/net/nknouf/ns/bibtex#
n13http://localhost/temp/predkladatel/
n17http://linked.opendata.cz/resource/domain/vavai/projekt/
n11http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n9http://linked.opendata.cz/ontology/domain/vavai/
n22https://schema.org/
n8http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F10%3A00044742%21RIV11-GA0-14330___/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n20http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n21http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F10%3A00044742%21RIV11-GA0-14330___
rdf:type
n9:Vysledek skos:Concept
dcterms:description
We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on transition graphs of classic one-counter automata. We study primarily the termination objective, where one player has to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives. We show that the qualitative termination problem for OC-SSGs is both in NP and coNP, and in P-time for 1-player OC-SSGs. Moreover, we show that quantitative limit problems for OC-SSGs are both in NP and coNP, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs. We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on transition graphs of classic one-counter automata. We study primarily the termination objective, where one player has to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives. We show that the qualitative termination problem for OC-SSGs is both in NP and coNP, and in P-time for 1-player OC-SSGs. Moreover, we show that quantitative limit problems for OC-SSGs are both in NP and coNP, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.
dcterms:title
One-Counter Stochastic Games One-Counter Stochastic Games
skos:prefLabel
One-Counter Stochastic Games One-Counter Stochastic Games
skos:notation
RIV/00216224:14330/10:00044742!RIV11-GA0-14330___
n4:aktivita
n7:P n7:Z
n4:aktivity
P(1M0545), P(GAP202/10/1469), Z(MSM0021622419)
n4:dodaniDat
n21:2011
n4:domaciTvurceVysledku
n11:1762834 n11:5532787
n4:druhVysledku
n19:D
n4:duvernostUdaju
n14:S
n4:entitaPredkladatele
n10:predkladatel
n4:idSjednocenehoVysledku
276975
n4:idVysledku
RIV/00216224:14330/10:00044742
n4:jazykVysledku
n20:eng
n4:klicovaSlova
one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward
n4:klicoveSlovo
n5:Markov%20decision%20process n5:long%20run%20average%20reward n5:simple%20stochastic%20games n5:one-counter%20automata n5:termination
n4:kontrolniKodProRIV
[657608184FA6]
n4:mistoKonaniAkce
Chennai, Indie
n4:mistoVydani
Dagstuhl, Germany
n4:nazevZdroje
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
n4:obor
n12:IN
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
3
n4:projekt
n17:GAP202%2F10%2F1469 n17:1M0545
n4:rokUplatneniVysledku
n21:2010
n4:tvurceVysledku
Etessami, Kousha Brázdil, Tomáš Brožek, Václav
n4:typAkce
n18:WRD
n4:zahajeniAkce
2010-12-15+01:00
n4:zamer
n8:MSM0021622419
s:issn
1868-8969
s:numberOfPages
12
n15:hasPublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
n22:isbn
978-3-939897-23-1
n13:organizacniJednotka
14330