2005年6月
On state-alternating context-free grammars
THEORETICAL COMPUTER SCIENCE
- ,
- ,
- ,
- 巻
- 337
- 号
- 1-3
- 開始ページ
- 183
- 終了ページ
- 216
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2004.12.029
- 出版者・発行元
- ELSEVIER SCIENCE BV
State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75-85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated. (c) 2005 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.tcs.2004.12.029
- ISSN : 0304-3975
- Web of Science ID : WOS:000229668700008