About: One-Counter Stochastic Games

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

About: One-Counter Stochastic 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 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. (en)
Title	One-Counter Stochastic Games One-Counter Stochastic Games (en)
skos:prefLabel	One-Counter Stochastic Games One-Counter Stochastic Games (en)
skos:notation	RIV/00216224:14330/10:00044742!RIV11-GA0-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GAP202/10/1469), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš Brožek, Václav
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	276975
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/10:00044742
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward (en)
http://linked.open.../riv/klicoveSlovo	one-counter automata termination Markov decision process long run average reward simple stochastic games
http://linked.open...ontrolniKodProRIV	[657608184FA6]
http://linked.open...v/mistoKonaniAkce	Chennai, Indie
http://linked.open...i/riv/mistoVydani	Dagstuhl, Germany
http://linked.open...i/riv/nazevZdroje	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Formal methods for analysis and verification of complex systems Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2010
http://linked.open...iv/tvurceVysledku	Brožek, Václav Brázdil, Tomáš Etessami, Kousha
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2010-12-15 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	1868-8969
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
https://schema.org/isbn	978-3-939897-23-1
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, 24 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software