SAPDA

In this paper we introduce a sub-family of SAPDA, one-turn Synchronized Alternating Pushdown Automata, and prove that they are equivalent to Linear Conjunctive Grammars

— Linear Conjunctive Grammars and One-Turn Synchronized Alternating Pushdown Automata, 2009

This is similar to the pushdown automata of 2.4. As, we have shown that the class of context-free grammars is equal to the class of languages accepted by PDAs, we will show the equivalence of the class of conjunctive languages with the class of languages accepted by SAPDA. The original paper introducing this concept is [11]. For making our model similar to automata and to pushdown automata as introduced in 2.4, we give a different but equivalent definition of SAPDA as it’s given in [11]. So, the proof of equivalence of the class of conjunctive grammars with the class of SAPDA is also different than the one given in the orininal paper.

— Conjunctive and Boolean Grammars, 2010