Conjunctive Grammars and Synchronized Alternating Pushdown Automata

Опубликовано 7 сентября 2016, 17:32

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, seem to have great potential for applications in fields such as Programming Languages, Formal Verification, Computational Linguistics, and Computational Biology, and are therefore of interest for theoretical research. Conjunctive Grammars are an example of such a model. Introduced in 2001, this grammar model extends Context-free Grammars by adding explicit intersection rules, while retaining polynomial parsing. We present a new automaton model, Synchronized Alternating Pushdown Automata (SAPDA), which is the first automaton counterpart shown for Conjunctive Grammars. The SAPDA model is a variation on Alternating Pushdown Automata which uses a limited form of synchronization to create localized parallel computations. In this talk, I will present both Conjunctive Grammars and Synchronized Alternating Pushdown Automata, discuss the relationship between them, and show some interesting examples of languages that they can accept. Joint work with Michael Kaminski.