2 citations · 3 across the 4 of their papers we have counts for
6 papers
Qualitative Multi-Objective Reachability for Ordered Branching MDPs
Kousha Etessami, Emanuel Martinov
We study qualitative multi-objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context-free MDPs, building on prior results fo…
Reachability for Branching Concurrent Stochastic Games
Kousha Etessami, Emanuel Martinov, Alistair Stewart +1
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperf…
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We study the problem of computing the probability that a given stochastic context-free grammar (SCFG), G, generates a string in a given regular language L(D) (given by a DFA, D). T…
Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-typ…
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Tomáš Brázdil, Václav Brožek, Kousha Etessami +1
One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of clas…
One-Counter Markov Decision Processes
Tomáš Brázdil, Václav Brožek, Kousha Etessami +2
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…