Functorial Question Answering

Abstract

We study the relational variant of the categorical compositional distributional (DisCoCat) models of Coecke et al, where we replace vector spaces and linear maps by sets and relations. We show that RelCoCat models factorise through Cartesian bicategories, as a corollary we get logspace reductions from semantics and entailment to evaluation and containment of conjunctive queries respectively. Finally, we define question answering as an NP-complete problem.