About: Reachability in Recursive Markov Decision Processes

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

About: Reachability in Recursive Markov Decision Processes 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 Markov decision processes generated by stateless pushdown automata. This class corresponds to 1.5-player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets S and T of safe and terminal stack configurations, where the membership to S and T depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given x in {0,1}. We show that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states. We consider a class of infinite-state Markov decision processes generated by stateless pushdown automata. This class corresponds to 1.5-player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets S and T of safe and terminal stack configurations, where the membership to S and T depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given x in {0,1}. We show that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states. (en)
Title	Reachability in Recursive Markov Decision Processes Reachability in Recursive Markov Decision Processes (en)
skos:prefLabel	Reachability in Recursive Markov Decision Processes Reachability in Recursive Markov Decision Processes (en)
skos:notation	RIV/00216224:14330/08:00024683!RIV10-GA0-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GD102/05/H050), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	5
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš Forejt, Vojtěch Brožek, Václav Kučera, Antonín
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	391530
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/08:00024683
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Markov decision processes; temporal logics; reachability (en)
http://linked.open.../riv/klicoveSlovo	Markov decision processes reachability temporal logics
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[02FB1C3C44F7]
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 Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems
http://linked.open...UplatneniVysledku	2008
http://linked.open...v/svazekPeriodika	206
http://linked.open...iv/tvurceVysledku	Brožek, Václav Brázdil, Tomáš Forejt, Vojtěch Kučera, Antonín
http://linked.open...ain/vavai/riv/wos	000256002800003
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	0890-5401
number of pages	18 (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