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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n10http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F11%3A00051537%21RIV12-MSM-14330___/
n13http://localhost/temp/predkladatel/
n18http://linked.opendata.cz/resource/domain/vavai/projekt/
n6http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n4http://linked.opendata.cz/resource/domain/vavai/subjekt/
n3http://linked.opendata.cz/ontology/domain/vavai/
n9http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n5http://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#
n8http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n20http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n12http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F11%3A00051537%21RIV12-MSM-14330___
rdf:type
n3:Vysledek skos:Concept
dcterms:description
We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint `>0' or `=1'. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in PTIME for the `>0' constraint, and in NP intersect. coNP for the `=1' constraint. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively. We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint `>0' or `=1'. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in PTIME for the `>0' constraint, and in NP intersect. coNP for the `=1' constraint. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively.
dcterms:title
Qualitative Reachability in Stochastic BPA Games Qualitative Reachability in Stochastic BPA Games
skos:prefLabel
Qualitative Reachability in Stochastic BPA Games Qualitative Reachability in Stochastic BPA Games
skos:notation
RIV/00216224:14330/11:00051537!RIV12-MSM-14330___
n3:predkladatel
n4:orjk%3A14330
n5:aktivita
n20:P n20:Z
n5:aktivity
P(1M0545), Z(MSM0021622419)
n5:cisloPeriodika
8
n5:dodaniDat
n12:2012
n5:domaciTvurceVysledku
n6:1762834 n6:9872655 n6:5532787 n6:3294099
n5:druhVysledku
n17:J
n5:duvernostUdaju
n7:S
n5:entitaPredkladatele
n10:predkladatel
n5:idSjednocenehoVysledku
225366
n5:idVysledku
RIV/00216224:14330/11:00051537
n5:jazykVysledku
n15:eng
n5:klicovaSlova
pushdown automata; turn-based games
n5:klicoveSlovo
n8:pushdown%20automata n8:turn-based%20games
n5:kodStatuVydavatele
NL - Nizozemsko
n5:kontrolniKodProRIV
[CE9003B44DF0]
n5:nazevZdroje
Information and Computation
n5:obor
n19:IN
n5:pocetDomacichTvurcuVysledku
4
n5:pocetTvurcuVysledku
4
n5:projekt
n18:1M0545
n5:rokUplatneniVysledku
n12:2011
n5:svazekPeriodika
209
n5:tvurceVysledku
Obdržálek, Jan Brázdil, Tomáš Brožek, Václav Kučera, Antonín
n5:zamer
n9:MSM0021622419
s:issn
0890-5401
s:numberOfPages
24
n13:organizacniJednotka
14330