On the memory consumption of probabilistic pushdown automata

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	BRÁZDIL Tomáš ESPARZA Javier KIEFER Stefan
Rok publikování	2009
Druh	Článek ve sborníku
Konference	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	continuous time games; reachability
Popis	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.
Související projekty:	Institut Teoretické Informatiky