About: Qualitative Reachability in Stochastic BPA Games

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Qualitative Reachability in Stochastic BPA Games Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. (en)
Title	Qualitative Reachability in Stochastic BPA Games Qualitative Reachability in Stochastic BPA Games (en)
skos:prefLabel	Qualitative Reachability in Stochastic BPA Games Qualitative Reachability in Stochastic BPA Games (en)
skos:notation	RIV/00216224:14330/11:00051537!RIV12-MSM-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	8
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš Brožek, Václav Kučera, Antonín Obdržálek, Jan
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	225366
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/11:00051537
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	pushdown automata; turn-based games (en)
http://linked.open.../riv/klicoveSlovo	pushdown automata turn-based games
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[CE9003B44DF0]
http://linked.open...i/riv/nazevZdroje	Information and Computation
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	4 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	209
http://linked.open...iv/tvurceVysledku	Brožek, Václav Brázdil, Tomáš Kučera, Antonín Obdržálek, Jan
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	0890-5401
number of pages	24 (xsd:int)
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software