抄録
The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.
| 本文言語 | English |
|---|---|
| ページ（範囲） | 959-966 |
| ページ数 | 8 |
| ジャーナル | IEICE Transactions on Information and Systems |
| 巻 | E87-D |
| 号 | 4 |
| 出版ステータス | Published - 2004 4月 |
ASJC Scopus subject areas
- 情報システム
- コンピュータ グラフィックスおよびコンピュータ支援設計
- ソフトウェア