Hypergraph Basic Categorial Grammars

Pshenitsyn, Tikhon

This work is an attempt to generalize categorial grammars, which deal with string languages, to hypergraphs. We consider a particular approach called basic categorial grammar (BCG) and introduce its natural extension to hypergraphs — hypergraph basic categorial grammar (HBCG). We show that BCGs can be naturally embedded in HBCGs. It turns out that, as BCGs are equivalent to context-free grammars, HBCGs are equivalent to hyperedge replacement grammars in generalized Greibach normal form. We also present several structural properties of HBCGs. From practical point of view, we show that HBCGs can be used to describe semantics of sentences of natural languages. We incorporate the lambda semantics into the new mechanism in the same way as it is done for BCGs and show that such an embedding allows one to describe semantics of sentences with cross-serial dependencies.