טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAizikowitz Tamar
SubjectSynchronized Alternating Pushdown Automata
DepartmentDepartment of Computer Science
Supervisor Professor Michael Kaminski
Full Thesis textFull thesis text - English Version


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 which 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 which 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 which strictly includes the boolean closure of classical LR(0) languages, thus extending previous linear-time parsing results.