Functorial Question Answering

Giovanni de Felice
(University of Oxford)
Konstantinos Meichanetzidis
(University of Oxford, Cambridge Quantum Computing Ltd.)
Alexis Toumi
(University of Oxford)

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.

In John Baez and Bob Coecke: Proceedings Applied Category Theory 2019 (ACT 2019), University of Oxford, UK, 15-19 July 2019, Electronic Proceedings in Theoretical Computer Science 323, pp. 84–94.
Published: 15th September 2020.

ArXived at: https://dx.doi.org/10.4204/EPTCS.323.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org