Deep Pushdown Automata and Their Restricted Versions

Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející pouze na dně zásobníku, a jediným dalším nevstupním symbolem. Z tohoto závěru vyplývá nekonečná hierarchie jazyků přijímaných těmito automaty