Functorial Question Answering
This work addresses foundational issues in computational linguistics and AI by linking linguistic models to database theory, though it appears incremental in extending existing frameworks.
The paper tackles the problem of modeling natural language semantics by establishing a correspondence between distributional compositional models in the category of sets and relations and relational databases, resulting in complexity-theoretic reductions that define question answering as an NP-complete problem.
Distributional compositional (DisCo) models are functors that compute the meaning of a sentence from the meaning of its words. We show that DisCo models in the category of sets and relations correspond precisely to relational databases. As a consequence, we get complexity-theoretic reductions from semantics and entailment of a fragment of natural language to evaluation and containment of conjunctive queries, respectively. Finally, we define question answering as an NP-complete problem.