Informace o publikaci
On the memory consumption of probabilistic pushdown automata
| Autoři | |
|---|---|
| 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 | |
| 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: |