Introduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus

Abstract: In this paper hypergraph Lambek calculus (

m a t h r m H L

) is presented. This formalism aims to generalize the Lambek calculus (

m a t h r m L

) to hypergraphs as hyperedge replacement grammars extend context-free grammars. In contrast to the Lambek calculus,

m a t h r m H L

deals with hypergraph types and sequents; its axioms and rules naturally generalize those of

m a t h r m L

. Consequently, certain properties (e.g. the cut elimination) can be lifted from

m a t h r m L

to

m a t h r m H L

. It is shown that

m a t h r m L

can be naturally embedded in

m a t h r m H L

; moreover, a number of its variants (

m a t h r m L P

,

m a t h r m N L

,

m a t h r m N L P

,

m a t h r m L

with modalities,

m a t h r m L^{a} s t (m a t h b f 1)

,

m a t h r m L^{m a t h r m R}

) can also be embedded in

m a t h r m H L

via different graph constructions. We also establish a connection between

m a t h r m H L

and Datalog with embedded implications. It is proved that the parsing problem for

m a t h r m H L

is NP-complete.

This page was built for publication: Introduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus