LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA

摘要

In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.