A grammatical characterization of alternating pushdown automata (Q1123637)

An alternating context-free grammar (ACFG for short) is a quintuple \(G=(N,U,\Sigma,P,S)\) where \((N,\Sigma,P,S)\) is a context-free grammar (CFG), called the underlying CFG of \(G\), and \(U\) is a subset of \(N\). A convenient concept of acceptable derivation is introduced and then the language generated by \(G\) is defined to be the set \(L(G)=\{\text{value}(T)\mid T \text{is an acceptable derivation in } G\}\), where value \((T)\) denotes the value of the derivation \(T\), a parameter related to the root of \(T\). The concept of an ACFG is used in order to characterize grammatically the alternating pushdown automata, which are proved to be equivalent to ACFG. The importance of this result can be understood in connection with the general concept of alternation as a generalization of the notion of nondeterminism. The author recalls that the notion of alternation has contributed a considerable development to computational complexity theory.