時間制約付きコンピュータに関するプッシュダウン機械の特徴

補助プッシュダウン機械と呼ばれる機械のクラスが導入される。スタックオートマトンを含むいくつかのタイプのプッシュダウンオートマトンがこれらの機械に関して特徴づけられる。問題となる各クラスの機械の計算能力は時間制約付きチューリング機械に関して特徴づけられ、分野の未解決問題に対するいくつかの副次的結果が導出される。