Technical Report PHD-2010-14

Title: Synchronized Alternating Pushdown Automata
Authors: Tamar Aizikowitz
Supervisors: Michael Kaminski
Abstract: Context-free languages combine expressiveness with polynomial parsing, making them very appealing for practical applications. In fact, they are possibly the most widely used class of languages in Computer Science. Thus, models of computation that slightly extend context-free models, without losing parsing efficiency, have great potential for applications in fields such as Programming Languages, Formal Verification, and Computational Linguistics, and are therefore of interest for theoretical research.

Conjunctive Grammars (CG) are an example of such a model. Introduced in 2001, they extend Context-free Grammars by adding explicit intersection rules, while retaining polynomial parsing. CG greatly resembles classical Context-free Grammars, making them more approachable to a wide audience, and a good candidate for practical applications. We present a new automaton model, Synchronized Alternating Pushdown Automata (SAPDA), which is the first automaton counterpart shown for CG.

The SAPDA model is a variation on Alternating Pushdown Automata that uses a limited form of synchronization to create localized parallel computations. The correlation between SAPDA and CG is analogous to the classical correlation between context-free grammars and PDA, making them a natural automaton counterpart for CG. We show that the correlation extends the one-turn sub-family of SAPDA, which is equivalent to the linear sub-family of CG, analogously to the classical equivalence between one-turn PDA and linear context-free grammars.

Furthermore, we define a notion of LR(0) conjunctive grammars, and prove that they are equivalent to deterministic SAPDA. Through this equivalence we develop a linear-time parser for a strong class of languages that strictly includes the boolean closure of classical LR(0) languages, thus extending previous linear-time parsing results.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2010
To the main CS technical reports page

Computer science department, Technion