ABSTRACT
"Spider" is a nickname of special Frobenius algebras, a fundamental structure from mathematics, physics, and computer science. Pregroups are a fundamental structure from linguistics. Pregroups and spiders have been used together in natural language processing: one for syntax, the other for semantics. It turns out that pregroups themselves can be characterized as pointed spiders in the category of preordered relations, where they naturally arise from grammars. The other way around, preordered spider algebras in general can be characterized as unions of pregroups. This extends the characterization of relational spider algebras as disjoint unions of groups. The compositional framework that emerged with the results suggests new ways to understand and apply the basis structures in machine learning and data analysis.
► BibTeX data
► References
[1] Kazimierz Ajdukiewicz. Die syntaktische konnexität. Studia Philosophica, 1:1–27, 1935. Translation in: Polish Logic 1920–1939 (S. McCall, ed), Oxford University Press 1967, pp 202–231.
[2] Yehoshua Bar-Hillel. A quasi-arithmetical notation for syntactic description. Language, 29(1):47–58, 1953. doi:10.2307/410452.
https://doi.org/10.2307/410452
[3] Michael Barr. On categories with effective unions. In F. Bourceux, editor, Categorical algebra and its applications, volume 1348 of Lecture Notes in Mathematics, pages 19–35. Springer-Verlag, 1988. doi:10.1007/bfb0081346.
https://doi.org/10.1007/bfb0081346
[4] Garrett Birkhoff. Lattice Theory, volume 25 of American Mathematical Society Colloquium Publications. American Mathematical Society, 1940. doi:10.1090/coll/025.
https://doi.org/10.1090/coll/025
[5] Leonard Bloomfield. On some rules of Panini. Journal of the American Oriental Society, 47:61–70, 1927. URL: http://www.jstor.org/stable/593241.
http://www.jstor.org/stable/593241
[6] Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. Rewriting with frobenius. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 165–174. ACM, 2018. doi:10.1145/3209108.3209137.
https://doi.org/10.1145/3209108.3209137
[7] Filippo Bonchi, Dusko Pavlovic, and Paweł Sobociński. Functorial Semantics for Relational Theories. Technical report, ASECOLab, November 2017. doi:https://doi.org/10.48550/arXiv.1711.08699.
https://doi.org/10.48550/arXiv.1711.08699
[8] Tai-Danae Bradley, Martha Lewis, Jade Master, and Brad Theilman. Translating and evolving: Towards a model of language change in DisCoCat. In M. Lewis et al, editor, Proceedings of the CAPNS@QI 2018, volume 283 of EPTCS, pages 50–61, 2018. doi:10.4204/EPTCS.283.4.
https://doi.org/10.4204/EPTCS.283.4
[9] Ronald Brown. Topology and Groupoids. BookSurge Publishing, 3 edition. URL: https://groupoids.org.uk/topgpds.html.
https://groupoids.org.uk/topgpds.html
[10] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, abs/2005.14165, 2020. arXiv:2005.14165, doi:10.48550/arXiv.2005.14165.
https://doi.org/10.48550/arXiv.2005.14165
arXiv:2005.14165
[11] Wojciech Buszkowski. Type logics and pregroups. Studia Logica, 87(2-3):145–169, 2007. doi:10.1007/s11225-007-9083-4.
https://doi.org/10.1007/s11225-007-9083-4
[12] Wojciech Buszkowski, Zhe Lin, and Katarzyna Moroz. Pregroup grammars with letter promotions: Complexity and context-freeness. J. Comput. Syst. Sci., 78(6):1899–1909, 2012. doi:10.1016/j.jcss.2011.12.010.
https://doi.org/10.1016/j.jcss.2011.12.010
[13] Aurelio Carboni. Matrices, relations, and group representations. Journal of Algebra, 136(2):497–529, 1991. doi:10.1016/0021-8693(91)90057-f.
https://doi.org/10.1016/0021-8693(91)90057-f
[14] Aurelio Carboni and Robert F.C. Walters. Cartesian bicategories, I. J. of Pure and Applied Algebra, 49:11–32, 1987. doi:10.1016/0022-4049(87)90121-6.
https://doi.org/10.1016/0022-4049(87)90121-6
[15] Claudia Casadio and Joachim Lambek. A tale of four grammars. Studia Logica, 71(3):315–329, 2002. doi:10.1023/A:1020564714107.
https://doi.org/10.1023/A:1020564714107
[16] N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124, 1956. doi:10.1109/TIT.1956.1056813.
https://doi.org/10.1109/TIT.1956.1056813
[17] Noam Chomsky. Syntactic Structures. Mouton, The Hague, 1957. doi:10.1515/9783110218329.
https://doi.org/10.1515/9783110218329
[18] Bob Coecke, Fabrizio Genovese, Martha Lewis, Dan Marsden, and Alexis Toumi. Generalized relations in linguistics & cognition. Theor. Comput. Sci., 752:104–115, 2018. doi:10.1016/j.tcs.2018.03.008.
https://doi.org/10.1016/j.tcs.2018.03.008
[19] Bob Coecke, Edward Grefenstette, and Mehrnoosh Sadrzadeh. Lambek vs. Lambek: Functorial vector space semantics and string diagrams for Lambek calculus. Ann. Pure Appl. Log., 164(11):1079–1100, 2013. doi:10.1016/j.apal.2013.05.009.
https://doi.org/10.1016/j.apal.2013.05.009
[20] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. doi:10.1017/9781316219317.
https://doi.org/10.1017/9781316219317
[21] Bob Coecke, Éric Oliver Paquette, and Dusko Pavlovic. Classical and quantum structuralism. In Simon Gay and IanEditors Mackie, editors, Semantic Techniques in Quantum Computation, page 29–69. Cambridge University Press, 2009. doi:10.1017/CBO9781139193313.003.
https://doi.org/10.1017/CBO9781139193313.003
[22] Bob Coecke and Dusko Pavlovic. Quantum measurements without sums. In G. Chen, L. Kauffman, and S. Lamonaco, editors, Mathematics of Quantum Computing and Technology, page 36pp. Taylor and Francis, 2007.
[23] Bob Coecke, Dusko Pavlovic, and Jamie Vicary. A new description of orthogonal bases. Math. Structures in Comp. Sci., 23(3):555–567, 2013. doi:10.1017/S0960129512000047.
https://doi.org/10.1017/S0960129512000047
[24] Bob Coecke, Mehrnoosh Sadrzadeh, and Stephen Clark. Mathematical foundations for a compositional distributional model of meaning. In J. van Benthem, M. Moortgat, and W. Buszkowski, editors, A Festschrift for Jim Lambek, Linguistic Analysis, pages 345–384. Springer, 2010.
[25] Ivan Di Liberti, Fosco Loregiàn, Chad Nester, and Pawel Sobocinski. Functorial semantics for partial theories. Proc. ACM Program. Lang., 5(POPL):1–28, 2021. doi:10.1145/3434338.
https://doi.org/10.1145/3434338
[26] Gerhard Gentzen. Untersuchungen über das logische Schließen. Mathematische Zeitschrift, 39(1):176–210, 405–431, 1935.
[27] Chris Heunen, Ivan Contreras, and Alberto S. Cattaneo. Relative Frobenius algebras are groupoids. Journal of Pure and Applied Algebra, 217(1):114–124, 2013. doi:10.1016/j.jpaa.2012.04.002.
https://doi.org/10.1016/j.jpaa.2012.04.002
[28] Chris Heunen, Mehrnoosh Sadrzadeh, and Edward Grefenstette, editors. Quantum Physics and Linguistics - A Compositional, Diagrammatic Discourse. Oxford University Press, 2013. doi:10.1093/acprof:oso/9780199646296.001.0001.
https://doi.org/10.1093/acprof:oso/9780199646296.001.0001
[29] Philip J. Higgins. Categories and groupoids. Van Nostrand Reinhold, 1971. also in Reprints of Theory and Applications of Categories, No. 7 (2005) pp 1-195.
[30] Dominic J.D. Hughes and Dusko Pavlovic. Sign as an adjunction. working paper.
[31] Edmund Husserl. The Shorter Logical Investigations. International Library of Philosophy. Routledge, 2001. doi:10.4324/9780203420034.
https://doi.org/10.4324/9780203420034
[32] Daniel Jurafsky and James H. Martin. Speech and language processing, December 2020. partial manuscript of 3rd edition, revised and expanded, available through authors' home page.
[33] Toshiki Kataoka and Dusko Pavlovic. Towards Concept Analysis in Categories: Limit Inferior as Algebra, Limit Superior as Coalgebra. In L.S. Moss and P. Sobocinski, editors, Proceedings of CALCO 2015, volume 35 of LIPIcs, pages 130–155, Dagstuhl, Germany, 2015. Leibniz-Zentrum für Informatik. doi:10.48550/arXiv.1505.01098.
https://doi.org/10.48550/arXiv.1505.01098
[34] Joachim Kock. Frobenius Algebras and 2-D Topological Quantum Field Theories, volume 59 of Londong Mathematical Society Student Texts. Cambridge University Press, 2004. doi:10.1017/cbo9780511615443.
https://doi.org/10.1017/cbo9780511615443
[35] Jim Lambek. Pregroups: A new algebraic approach to sentence structure. In Carlos Martín-Vide and Gheorghe Paun, editors, Recent Topics in Mathematical and Computational Linguistics, pages 182–195. Editura Academiei Române, Bucuresti, 2000.
[36] Joachim Lambek. The mathematics of sentence structure. The American Mathematical Monthly, 65(3):154–170, 1958. doi:10.1080/00029890.1958.11989160.
https://doi.org/10.1080/00029890.1958.11989160
[37] Joachim Lambek. Lectures on Rings and Modules. Blaisdell Publishing Co., 1966. doi:10.2307/2317170.
https://doi.org/10.2307/2317170
[38] Joachim Lambek. Type grammar revisited. In A. Lecomte et al, editor, Logical Aspects of Computational Linguistics (LACL) '97, volume 1582 of Lecture Notes in Computer Science, pages 1–27. Springer, 1997. doi:10.1007/3-540-48975-4_1.
https://doi.org/10.1007/3-540-48975-4_1
[39] Joachim Lambek. Iterated galois connections in arithmetic and linguistics. In K. Denecke et al, editor, Galois Connections and Applications, Mathematics and Its Applications, pages 389–397. Springer, 2004. doi:10.1007/978-1-4020-1898-5_11.
https://doi.org/10.1007/978-1-4020-1898-5_11
[40] Joachim Lambek. From Word to Sentence: A Computational Algebraic Approach to Grammar. Open access publications. Polimetrica, 2008.
[41] Joachim Lambek and Leo Moser. Inverse and complementary sequences of natural numbers. The American Mathematical Monthly, 61(7):454–458, 1954. doi:10.2307/2308078.
https://doi.org/10.2307/2308078
[42] F. William Lawvere. Adjointness in foundations. Dialectica, 23:281–296, 1969. reprint in Theory and Applications of Categories, No. 16, 2006, pp.1–16. doi:10.1111/j.1746-8361.1969.tb01194.x.
https://doi.org/10.1111/j.1746-8361.1969.tb01194.x
[43] F. William Lawvere. Equality in hyperdoctrines and the comprehension schema as an adjoint functor. In Alex Heller, editor, Applications of Categorical Algebra, number 17 in Proceedings of Symposia in Pure Mathematics, pages 1–14. American Mathematical Society, 1970. doi:10.1090/pspum/017.
https://doi.org/10.1090/pspum/017
[44] Martha Lewis. Compositionality for recursive neural networks. J. Appl. Logics, 6(4):709–724, 2019.
[45] Robin Lorenz, Anna Pearson, Konstantinos Meichanetzidis, Dimitri Kartsaklis, and Bob Coecke. QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer. CoRR, abs/2102.12846, 2021. arXiv:2102.12846.
arXiv:2102.12846
[46] Andrei A. Markov. An example of statistical investigation in the text of Eugene Onyegin, illustrating coupling of tests in chains. Proceedings of the Academy of Sciences of St. Petersburg, VI(7):153–162, 1913. doi:10.1017/S0269889706001074.
https://doi.org/10.1017/S0269889706001074
[47] Konstantinos Meichanetzidis, Stefano Gogioso, Giovanni de Felice, Nicolò Chiappori, Alexis Toumi, and Bob Coecke. Quantum Natural Language Processing on Near-Term Quantum Computers. CoRR, abs/2005.04147, 2020. arXiv:2005.04147.
arXiv:2005.04147
[48] Michael Moortgat. A note on multidimensional dyck languages. In Claudia Casadio, Bob Coecke, Michael Moortgat, and Philip Scott, editors, Categories and Types in Logic, Language, and Physics - Essays Dedicated to Jim Lambek on the Occasion of His 90th Birthday, volume 8222 of Lecture Notes in Computer Science, pages 279–296. Springer, 2014. doi:10.1007/978-3-642-54789-8_16.
https://doi.org/10.1007/978-3-642-54789-8_16
[49] Michael Moortgat, Mehrnoosh Sadrzadeh, and Gijs Wijnholds. A Frobenius algebraic analysis for parasitic gaps. FLAP, 7(5):823–852, 2020. URL: http://collegepublications.co.uk/ifcolog/?00041.
http://collegepublications.co.uk/ifcolog/?00041
[50] Peter Naur. A course of algol 60 programming. ALGOL Bull., (Sup 9):1–38, jan 1961.
[51] Dusko Pavlovic. Maps II: Chasing diagrams in categorical proof theory. J. of the IGPL, 4(2):1–36, 1996. doi:10.1093/jigpal/4.2.159.
https://doi.org/10.1093/jigpal/4.2.159
[52] Dusko Pavlovic. Quantum and classical structures in nondeterministic computation. In Peter Bruza, Don Sofge, and Keith van Rijsbergen, editors, Proceedings of Quantum Interaction 2009, volume 5494 of Lecture Notes in Artificial Intelligence, pages 143–158. Springer Verlag, 2009. doi:10.1007/978-3-642-00834-4_13.
https://doi.org/10.1007/978-3-642-00834-4_13
[53] Dusko Pavlovic. Geometry of abstraction in quantum computation. Proceedings of Symposia in Applied Mathematics, 71:233–267, 2012. arxiv.org:1006.1010. doi:10.1090/psapm/071/607.
https://doi.org/10.1090/psapm/071/607
[54] Dusko Pavlovic. Quantitative Concept Analysis. In Florent Domenach, Dmitry I. Ignatov, and Jonas Poelmans, editors, Proceedings of ICFCA 2012, volume 7278 of Lecture Notes in Artificial Intelligence, pages 260–277. Springer Verlag, 2012. doi:10.1007/978-3-642-29892-9_24.
https://doi.org/10.1007/978-3-642-29892-9_24
[55] Dusko Pavlovic. Bicompletions of distance matrices. In Bob Coecke, Luke Ong, and Prakash Panangaden, editors, Computation, Logic, Games and Quantum Foundations. The Many Facets of Samson Abramsky, volume 7860 of Lecture Notes in Computer Science, pages 291–310. Springer Verlag, 2013. doi:10.1007/978-3-642-38164-5_20.
https://doi.org/10.1007/978-3-642-38164-5_20
[56] Dusko Pavlovic. Monoidal computer I: Basic computability by string diagrams. Information and Computation, 226:94–116, 2013. doi:10.1016/j.ic.2013.03.007.
https://doi.org/10.1016/j.ic.2013.03.007
[57] Dusko Pavlovic. Computer Science in Diagrams. textbook manuscript, in process by publisher, 2021.
[58] Dusko Pavlovic and Dominic J.D. Hughes. The nucleus of an adjunction and the Street monad on monads. CoRR, abs/2004.07353:87 pages, 2020. submitted. URL: http://arxiv.org/abs/2004.07353, arXiv:2004.07353.
arXiv:2004.07353
[59] Dusko Pavlovic and Muzamil Yahia. Monoidal computer III: A coalgebraic view of computability and complexity. In Corina Cı̂rstea, editor, Coalgebraic Methods in Computer Science (CMCS) 2018 — Selected Papers, volume 11202 of Lecture Notes in Computer Science, pages 167–189. Springer, 2018. doi:10.1007/978-3-030-00389-0.
https://doi.org/10.1007/978-3-030-00389-0
[60] Gordon D Plotkin. A structural approach to operational semantics. The Journal of Logic and Algebraic Programming, 60-61:3–139, 2004. lecture notes from 1981, circulated as Tech. Rep. DAIMI FN-19, Computer Science Department, Aarhus University.
[61] Anne Preller. Linear processing with pregroups. Stud. Logica, 87(2-3):171–197, 2007. doi:10.1007/s11225-007-9087-0.
https://doi.org/10.1007/s11225-007-9087-0
[62] Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The Frobenius anatomy of word meanings I: subject and object relative pronouns. J. Log. Comput., 23(6):1293–1317, 2013.
[63] Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The Frobenius anatomy of word meanings II: possessive relative pronouns. J. Log. Comput., 26(2):785–815, 2016.
[64] L. Schneps and P. Lochak, editors. Geometric Galois Actions. 1. Around Grothendieck's Esquisse D'un Programme, volume 242 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1997. doi:10.1017/CBO9780511758874.002.
https://doi.org/10.1017/CBO9780511758874.002
[65] Ross Street. Frobenius monads and pseudomonoids. Journal of mathematical physics, 45(10):3930–3948, 2004. doi:10.1063/1.1788852.
https://doi.org/10.1063/1.1788852
[66] Axel Thue, C.L. Siegel, and T. Nagell. Selected mathematical papers of Axel Thue. Universitetsforlaget, 1977. doi:10.1090/S0002-9904-1978-14535-2.
https://doi.org/10.1090/S0002-9904-1978-14535-2
[67] Morgan Ward and Robert P Dilworth. Residuated lattices. Transactions of the American Mathematical Society, 45(3):335–354, 1939. doi:10.1090/S0002-9947-1939-1501995-3.
https://doi.org/10.1090/S0002-9947-1939-1501995-3
[68] Simon Willerton. Tight spans, Isbell completions and semi-tropical modules. Theory and Applications of Categories, 28(22):696–732, August 2013.
Cited by
On Crossref's cited-by service no data on citing works was found (last attempt 2023-06-16 04:21:18). On SAO/NASA ADS no data on citing works was found (last attempt 2023-06-16 04:21:18).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.