Conjunctive grammars

Prelegent(ci)

Artur Jeż

Afiliacja

Uniwersytet Warszawski

Termin

16 maja 2007 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---