Conjunctive grammars

Speaker(s)

Artur Jeż

Affiliation

Uniwersytet Warszawski

Date

May 16, 2007, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

I discuss the notion of conjunctive grammars, introduced by A. Okhotin in 2001. In short they can be described as extension of context-free grammars with additional operation of intersection within the body of any production. This natural extension still leads to inheriting many nice properties from context-free grammars, in particular easy parsing algorithm. On the other hand it allows us to define more languages. I will also talk about my small contribution solving the problem of expressing power of unary conjunctive grammars, that is over unary alphabet. It is easy to show, that the context-free grammars can only define regular languages over unary alphabet. I will show that this is not true in case of conjunctive grammars and also show some consequences for decision problems of unary conjunctive grammars.

---