On the memory consumption of probabilistic pushdown automata

Varování

Publikace nespadá pod Filozofickou fakultu, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.