2009
On the memory consumption of probabilistic pushdown automata
BRÁZDIL, Tomáš; Javier ESPARZA a Stefan KIEFERZákladní údaje
Originální název
On the memory consumption of probabilistic pushdown automata
Autoři
BRÁZDIL, Tomáš; Javier ESPARZA a Stefan KIEFER
Vydání
Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), od s. 49-60, 12 s. 2009
Nakladatel
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/09:00039313
Organizační jednotka
Fakulta informatiky
ISBN
978-3-939897-13-2
ISSN
Klíčová slova anglicky
continuous time games; reachability
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 12. 3. 2010 15:18, doc. RNDr. Tomáš Brázdil, Ph.D., MBA
V originále
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.
Česky
V článku se studuje problém zaplnění paměti pro systémy modelované pomocí pravděpodobnostních zásobníkových automatů (pPDA). Prostor potřebný pro daný výpočet pPDA je maximální výška zásobníku dosažená během tohoto výpočtu. Problém je motivován výzkumem v oblasti plánování procesů s vlákny. Studujeme algoritmy pro výpočet distribuce maximální výšky zásobníku a očekávanou maximální výšku. Ukazujeme, že distribuci je možné efektivně aproximovat. Dále ukazujeme, že problém konečnosti očekávané maximální výšky je rozhodnutelný v polynomiálním čase pro bezstavové pPDA (pBPA) and obecně v polynomiálním prostoru. Na závěr popisujeme iterativní metodu pro aproximaci očekávané maximální výšky.
Návaznosti
| 1M0545, projekt VaV |
|