All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Reachability in Recursive Markov Decision Processes

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00024683" target="_blank" >RIV/00216224:14330/08:00024683 - isvavai.cz</a>

  • Result on the web

  • DOI - Digital Object Identifier

Alternative languages

  • Result language

    angličtina

  • Original language name

    Reachability in Recursive Markov Decision Processes

  • Original language 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. This result is a generalization of a re

  • Czech name

    Dosažitelnost v rekurzivních Markovových rozhodovacích procesech

  • Czech description

    V článku se zkoumá třída nekonečně-stavových Markovových rozhodovacích procesů generovaná zásobníkovými automaty bez stavové jednotky. Tato třída odpovídá hrám s 1.5 hráči nad grafy generovanými BPA systémy nebo (ekvivalentně) rekuzivními stavovými automaty s jedním exitem. Rozšířený problém dosažitelnosti je dán dvěma množinami S a T bezpečných a koncových stavů, kde příslušnost do S a T závisí pouza na symbolu na vrcholu zásobníku. V článku se zkoumá algortimická rozhodnutelnost a složitost otázky existence vhodné strategie, která zajistí, že pravděpodobnost dosažení koncového stavu přes bezpečné stavy je rovna danému x z množiny {0,1}. Je ukázáno, že tato otázka je algoritmicky rozhodnutelná v polynomiálním čase, a že množina všech konfigurací, prokteré vhodná strategie existuje, je efektivně regulární.

Classification

  • Type

    J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

  • CEP classification

    IN - Informatics

  • OECD FORD branch

Result continuities

  • Project

    Result was created during the realization of more than one project. More information in the Projects tab.

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Others

  • Publication year

    2008

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    Information and Computation

  • ISSN

    0890-5401

  • e-ISSN

  • Volume of the periodical

    206

  • Issue of the periodical within the volume

    5

  • Country of publishing house

    US - UNITED STATES

  • Number of pages

    18

  • Pages from-to

  • UT code for WoS article

    000256002800003

  • EID of the result in the Scopus database