TY - JOUR
T1 - On state-alternating context-free grammars
AU - Moriya, Etsuro
AU - Hofbauer, Dieter
AU - Huber, Maria
AU - Otto, Friedrich
PY - 2005/6/9
Y1 - 2005/6/9
N2 - 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.
AB - 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.
KW - Alternating context-free grammar
KW - Alternating pushdown automaton
KW - Context-free grammar with states
KW - State-alternating context-free grammar
UR - http://www.scopus.com/inward/record.url?scp=18444383376&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=18444383376&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2004.12.029
DO - 10.1016/j.tcs.2004.12.029
M3 - Article
AN - SCOPUS:18444383376
SN - 0304-3975
VL - 337
SP - 183
EP - 216
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -