Главная

Václav Brožek

  1. Qualitative Reachability in Stochastic BPA Games.

    Втр, 03/02/2010 - 16:02 — SomNambul
    Authors: Tomáš Brázdil, Václav Brožek, Antonín Kučera, Jan Obdržálek
    Subjects: Computer Science and Game Theory
    Abstract

    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 both in NP and coNP for the `=1' constraint.

  2. One-Counter Markov Decision Processes.

    Пнд, 09/14/2009 - 09:02 — SomNambul
    Authors: Tomáš Brázdil, Václav Brožek, Kousha Etessami, Antonín Kučera, Dominik Wojtczak
    Subjects: Computer Science and Game Theory
    Abstract

    We study the computational complexity of central analysis problems for
    One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented,
    countable-state MDPs. OC-MDPs are equivalent to a controlled extension of
    (discrete-time) Quasi-Birth-Death processes (QBDs), a stochastic model studied
    heavily in queueing theory and applied probability. They can thus be viewed as
    a natural ``adversarial'' version of a classic stochastic model. Alternatively,
    they can also be viewed as a natural probabilistic/controlled extension of
    classic one-counter automata.

Math-arch

RSS-материал