On the memory consumption of probabilistic pushdown automata

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš ESPARZA Javier KIEFER Stefan

Year of publication 2009
Type Article in Proceedings
Conference IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords continuous time games; reachability
Description We investigate the problem of evaluating memory consumption for systems modelled by probabilistic pushdown automata (pPDA). The space needed by a run of a pPDA is the maximal height reached by the stack during the run. The problem is motivated by the investigation of depth-first computations that play an important role for space-efficient schedulings of multithreaded programs. We study the computation of both the distribution of the memory consumption and its expectation. For the distribution, we develop an efficient approximation method. For the expected memory consumption, we show that whether it is infinite can be decided in polynomial time for stateless pPDA (pBPA) and in polynomial space for pPDA. We also provide an iterative method for approximating the expectation.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.