2 papers
cs.FL2013
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…
cs.CC2012
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max(min) polynomial equations, referred to as maxPPSs (and minPP…