Speaker: Alexander Okhotin

Title: Formal grammars are not dead: models of syntax beyond the 
context-free grammars.

Abstract:
Formal models of syntax have long been out of focus of attention of computer 
scientists. Today it is widely assumed that the first and the last reasonable 
model is a context-free grammar, while all other kinds of grammars proposed in 
the literature  are nothing but curiosities used to fill up the pages of 
obscure theoretical journals.

The goal of this talk is to justify that there is life beyond context-free 
grammars. The recent work on formal grammars shall be presented according to 
the imperative goal of maintaining whatever properties make the context-free 
grammars a good model of syntax. First, there are natural questions to be 
asked: why does a context-free grammar give an intuitively clear description 
of a language? why can it be processed by a variety of efficient algorithms? 
This discussion leads to perceiving a context-free grammar as a logical theory 
of disjunction and concatenation. And it turns out that in such a theory, one 
can safely introduce the remaining propositional connectives, conjunction and 
negation, and thus define the more general conjunctive grammars and Boolean 
grammars. These grammars inherit all known parsing algorithms for general 
context-free grammars, and at the same time have a substantially higher 
expressive power. Theoretical and practical results on these grammars obtained 
by the speaker and his colleagues over the last decade shall be presented in 
the talk. The talk will be concluded with a list of problems to investigate, 
including software implementation of Boolean grammars, further parsing 
algorithms and additional theoretical questions to study.