On the memory consumption of probabilistic pushdown automata
| Authors | |
|---|---|
| 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 | |
| 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: |