Functorial question answering. (English) Zbl 07453972
Baez, John (ed.) et al., Proceedings of the applied category theory 2019, ACT 2019, University of Oxford, UK, July 15–19, 2019. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 323, 84-94 (2020).
Summary: 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.
For the entire collection see [Zbl 1466.68006].
For the entire collection see [Zbl 1466.68006].
References:
| [1] | Samson Abramsky & Nihil Shah (2018): Relating Structure and Power: Comonadic Semantics for Compu-tational Resources. arXiv . cs , doi:10.4230/LIPIcs.CSL.2018.2. · Zbl 1509.03096 · doi:10.4230/LIPIcs.CSL.2018.2 |
| [2] | J. F. Baget & M. L. Mugnier (2002): Extensions of Simple Conceptual Graphs: The Complexity of Rules and Constraints. Journal of Artificial Intelligence Research 16, pp. 425-465, doi:10.1613/jair.918. · Zbl 1032.68115 · doi:10.1613/jair.918 |
| [3] | Filippo Bonchi, Jens Seeber & Pawel Sobocinski (2018): Graphical Conjunctive Queries. arXiv . cs , doi:10.4230/LIPIcs.CSL.2018.13. · Zbl 1528.68098 · doi:10.4230/LIPIcs.CSL.2018.13 |
| [4] | Andrei A. Bulatov (2017): A Dichotomy Theorem for Nonuniform CSPs. arXiv . cs , doi:10.1109/FOCS.2017.37. · doi:10.1109/FOCS.2017.37 |
| [5] | Wojciech Buszkowski & Katarzyna Moroz (2008): Pregroup Grammars and Context-Free Grammars. Com-putational Algebraic Approaches to Natural Language, Polimetrica 121. |
| [6] | A. Carboni & R. F. C. Walters (1987): Cartesian Bicategories I. Journal of Pure and Applied Algebra 49(1), pp. 11-32, doi:10.1016/0022-4049(87)90121-6. · Zbl 0637.18003 · doi:10.1016/0022-4049(87)90121-6 |
| [7] | Ashok K. Chandra & Philip M. Merlin (1977): Optimal Implementation of Conjunctive Queries in Relational Data Bases. In: Proceedings of the Ninth Annual ACM Symposium on Theory of Computing -STOC ’ , ACM Press, Boulder, Colorado, United States, pp. 77-90, doi:10.1145/800105.803397. · doi:10.1145/800105.803397 |
| [8] | Chandra Chekuri & Anand Rajaraman (2000): Conjunctive Query Containment Revisited. Theoretical Computer Science, p. 19, doi:10.1016/S0304-3975(99)00220-0. · Zbl 0944.68046 · doi:10.1016/S0304-3975(99)00220-0 |
| [9] | Stephen Clark, Bob Coecke & Mehrnoosh Sadrzadeh (2008): A Compositional Distributional Model of Meaning. In: Proceedings of the Second Symposium on Quantum Interaction QI-, pp. 133-140. |
| [10] | Stephen Clark, Bob Coecke & Mehrnoosh Sadrzadeh (2010): Mathematical Foundations for a Compositional Distributional Model of Meaning. In J. van Benthem, M. Moortgat & W. Buszkowski, editors: A Festschrift for Jim Lambek, Linguistic Analysis 36, pp. 345-384. Available at https://arxiv.org/abs/1003.4394. |
| [11] | Bob Coecke, Giovanni de Felice, Dan Marsden & Alexis Toumi (2018): Towards Compositional Dis-tributional Discourse Analysis. Electronic Proceedings in Theoretical Computer Science 283, pp. 1-12, doi:10.4204/EPTCS.283.1. · doi:10.4204/EPTCS.283.1 |
| [12] | Bob Coecke, Fabrizio Genovese, Martha Lewis, Dan Marsden & Alex Toumi (2018): Generalized Relations in Linguistics & Cognition. Theoretical Computer Science, doi:10.1016/j.tcs.2018.03.008. · Zbl 1408.91187 · doi:10.1016/j.tcs.2018.03.008 |
| [13] | Brendan Fong & David I. Spivak (2018): Graphical Regular Logic. arXiv . . Available at https://arxiv.org/abs/1812.05765. |
| [14] | Michael R. Garey & David S. Johnson (1990): Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA. · Zbl 0411.68039 |
| [15] | André Joyal & Ross Street (1988): Planar Diagrams and Tensor Algebra. |
| [16] | Joachim Lambek (1999): Type Grammar Revisited. In Alain Lecomte, François Lamarche & Guy Perrier, editors: Logical Aspects of Computational Linguistics, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 1-27, doi:10.1016/0168-0072(94)00063-9. · Zbl 0829.03022 · doi:10.1016/0168-0072(94)00063-9 |
| [17] | Joachim Lambek (2008): From Word to Sentence: A Computational Algebraic Approach to Grammar. Open Access Publications, Polimetrica. · Zbl 1166.03315 |
| [18] | Katarzyna Moroz (2011): A Savateev-Style Parsing Algorithm for Pregroup Grammars. In: For-mal Grammar, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 133-149, doi:10.1007/978-3-642-20169-1_9. · Zbl 1325.68122 · doi:10.1007/978-3-642-20169-1_9 |
| [19] | Evan Patterson (2017): Knowledge Representation in Bicategories of Relations. arXiv . cs, math . |
| [20] | Anne Preller (2007): Linear Processing with Pregroups. Studia Logica An International Journal for Symbolic Logic 87(2/3), pp. 171-197, doi:10.1007/s11225-007-9087-0. · Zbl 1132.03011 · doi:10.1007/s11225-007-9087-0 |
| [21] | Anne Preller (2014): From Logical to Distributional Models. Electronic Proceedings in Theoretical Computer Science 171, pp. 113-131, doi:10.4204/EPTCS.171.11. · Zbl 1464.03034 · doi:10.4204/EPTCS.171.11 |
| [22] | Anne Preller (2014): Natural Language Semantics in Biproduct Dagger Categories. J. Applied Logic 12(1), pp. 88-108, doi:10.1016/j.jal.2013.08.001. · Zbl 1335.03029 · doi:10.1016/j.jal.2013.08.001 |
| [23] | Anne Preller & Joachim Lambek (2007): Free Compact 2-Categories. Mathematical Structures in Computer Science 17(2), pp. 309-340, doi:10.1017/S0960129506005901. · Zbl 1151.18007 · doi:10.1017/S0960129506005901 |
| [24] | Anne Preller & Mehrnoosh Sadrzadeh (2011): Semantic Vector Models and Functional Mod-els for Pregroup Grammars. Journal of Logic, Language and Information 20(4), pp. 419-443, doi:10.1007/s10849-011-9132-2. · Zbl 1305.03028 · doi:10.1007/s10849-011-9132-2 |
| [25] | Mehrnoosh Sadrzadeh, Stephen Clark & Bob Coecke (2013): The Frobenius Anatomy of Word Mean-ings I: Subject and Object Relative Pronouns. Journal of Logic and Computation 23, pp. 1293-1317, doi:10.1093/logcom/ext044. · Zbl 1320.68207 · doi:10.1093/logcom/ext044 |
| [26] | Mehrnoosh Sadrzadeh, Dimitri Kartsaklis & Esma Balkır (2018): Sentence Entailment in Composi-tional Distributional Semantics. Annals of Mathematics and Artificial Intelligence 82(4), pp. 189-218, doi:10.1007/s10472-017-9570-x. · Zbl 1459.03030 · doi:10.1007/s10472-017-9570-x |
| [27] | Peter Selinger (2009): A Survey of Graphical Languages for Monoidal Categories. arXiv . , doi:10.1007/978-3-642-12821-9_4. · Zbl 1217.18002 · doi:10.1007/978-3-642-12821-9_4 |
| [28] | Giorgio Stefanoni, Boris Motik & Egor V. Kostylev (2018): Estimating the Cardinality of Conjunc-tive Queries over RDF Data Using Graph Summarisation. In: Proceedings of the World Wide Web Conference on World Wide Web, WWW , Lyon, France, April -, , pp. 1043-1052, doi:10.1145/3178876.3186003. · doi:10.1145/3178876.3186003 |
| [29] | Michaël Thomazo (2013): Conjunctive Query Answering Under Existential Rules -Decidability, Complexity, and Algorithms. Ph.D. thesis. Available at https://tel.archives-ouvertes.fr/tel-00925722. |
| [30] | William Zeng & Bob Coecke (2016): Quantum Algorithms for Compositional Natural Language Processing. Electronic Proceedings in Theoretical Computer Science 221, pp. 67-75, doi:10.4204/EPTCS.221.8. · doi:10.4204/EPTCS.221.8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
