Journal article
On state-alternating context-free grammars



Publication Details
Authors:
Otto, F.; Hofbauer, D.; Huber, M.; Moriya, E.
Publication year:
2005
Journal:
Theoretical Computer Science
Pages range:
183-216
Volume number:
337
Start page:
183
End page:
216
ISSN:
0304-3975

Abstract
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.


Authors/Editors

Last updated on 2019-01-11 at 16:06