# zbMATH — the first resource for mathematics

Natural language semantics and computability. (English) Zbl 07073681
Summary: This paper is a reflexion on the computability of natural language semantics. It does not contain a new model or new results in the formal semantics of natural language: it is rather a computational analysis, in the context for type-logical grammars, of the logical models and algorithms currently used in natural language semantics, defined as a function from a grammatical sentence to a (non-empty) set of logical formulas – because a statement can be ambiguous, it can correspond to multiple formulas, one for each reading. We argue that as long as we do not explicitly compute the interpretation in terms of possible world models, one can compute the semantic representation(s) of a given statement, including aspects of lexical meaning. This is a very generic process, so the results are, at least in principle, widely applicable. We also discuss the algorithmic complexity of this process.
##### MSC:
 03 Mathematical logic and foundations 68 Computer science
##### Keywords:
categorial grammar; complexity; proof theory
##### Software:
CatLog3; GitHub; Grail; LinearOne
Full Text:
##### References:
 [1] Asher, N. (2011). Lexical meaning in context: A web of words. Cambridge: Cambridge University Press. [2] Baillot, P., & Mogbil, V. (2004). Soft lambda-calculus: A language for polynomial time computation. In Foundations of software science and computation structures (pp. 27-41). Springer. · Zbl 1126.03306 [3] Barker, C.; Lapping, S. (ed.); Fox, C. (ed.), Scope, 40-76, (2015), Hoboken [4] Bassac, C.; Mery, B.; Retoré, C., Towards a type-theoretical account of lexical semantics, Journal of Logic, Language and Information, 19, 229-245, (2010) [5] Blackburn, P., & Bos, J. (2005). Representation and inference for natural language: A first course in computational semantics. Stanford: CSLI. [6] Bos, J., Clark, S., Steedman, M., Curran, J. R., & Hockenmaier, J. (2004). Wide-coverage semantic representation from a CCG parser. In Proceedings of COLING-2004 (pp. 1240-1246). [7] Buszkowski, W.; Benthem, J. (ed.); Meulen, A. (ed.), Mathematical linguistics and proof theory, 683-736, (1997), Amsterdam [8] Carpenter, B. (1994). Quantification and scoping: A deductive account. In The proceedings of the 13th west coast conference on formal linguistics. [9] Chatzikyriakidis, S.; Luo, Z., Natural language inference in Coq, Journal of Logic, Language and Information, 23, 441-480, (2014) · Zbl 1305.68193 [10] Church, A., A formulation of the simple theory of types, Journal of Symbolic Logic, 5, 56-68, (1940) · JFM 66.1192.06 [11] Cooper, R. (1975). Montague’s semantic theory and transformational grammar. Ph.D. thesis, University of Massachusetts. [12] Corblin, F. (2013). Cours de sémantique: Introduction. Paris: Armand Colin. [13] de Groote, PD; Pogodalla, S., On the expressive power of abstract categorial grammars: Representing context-free formalisms, Journal of Logic, Language, and Information, 13, 421-438, (2004) · Zbl 1062.03024 [14] Ebert, C. (2005). Formal investigations of underspecified representations. Ph.D. thesis, King’s College, University of London. [15] Fox, C.; Lappin, S., Expressiveness and complexity in underspecified semantics, Linguistic Analysis, 36, 385-417, (2010) [16] Gómez-Rodríguez, C., Alonso, M. A., & Vilares, M. (2006). On the theoretical and practical complexity of TAG parsers. In Proceedings of formal grammar (FG 2006) (pp. 87-101). [17] Hobbs, JR; Shieber, SM, An algorithm for generating quantifier scopings, Computational Linguistics, 13, 47-63, (1987) [18] Jacobson, P., The (dis)organization of the grammar: 25 years, Linguistics and Philosophy, 25, 601-626, (2002) [19] Joshi, A. (1985). Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In D. R. Dowty, L. Karttunen & A. Zwicky (Eds.), Natural language parsing (pp. 206-250). Cambridge: Cambridge University Press. [20] Joshi, A. (1997). Parsing techniques. In R. A. Cole, J. Mariani, H. Uszkoreit, A. Zaenen, & V. Zue (Eds.), Survey of the state of the art in human language technology, chap. 11.4 (pp. 351-356). Cambridge University Press and Giardini. [21] Koller, A., & Thater, S. (2010). Computing weakest readings. In Proceedings of the 48th annual meeting of the association for computational linguistics (pp. 30-39). [22] Kubota, Y.; Levine, R.; Béchet, D. (ed.); Dikovsky, A. (ed.), Gapping as like-category coordination, No. 7351, 135-150, (2012), Nantes · Zbl 1291.03056 [23] Lafont, Y., Soft linear logic and polynomial time, Theoretical Computer Science, 318, 163-180, (2004) · Zbl 1079.03057 [24] Langacker, R. (2008). Cognitive grammar: A basic introduction. Oxford: Oxford University Press. [25] Luo, Z., Formal semantics in modern type theories with coercive subtyping, Linguistics and Philosophy, 35, 491-513, (2012) [26] Mineshima, K., Martınez-Gómez, P., Miyao, Y., & Bekki, D. (2015). Higher-order logical inference with compositional semantics. In Proceedings of EMNLP (pp. 2055-2061). [27] Montague, R. (1970). English as a formal language. In B. Visentini (Ed.), Linguaggi nella societa e nella tecnica (pp. 188-221). Edizioni di Communita. [28] Montague, R.; Thomason, R. (ed.), The proper treatment of quantification in ordinary English, (1974), New Haven [29] Moortgat, M.; Benthem, J. (ed.); Meulen, A. (ed.), Categorial type logics, 93-177, (1997), Amsterdam [30] Moot, R. (2002). Proof nets for linguistic analysis. Ph.D. thesis, Utrecht Institute of Linguistics OTS, Utrecht University. · Zbl 1013.03016 [31] Moot, R. (2007). Filtering axiom links for proof nets. In L. Kallmeyer, P. Monachesi, G. Penn, & G. Satta (Eds.), Proccedings of formal grammar 2007. [32] Moot, R. (2010). Wide-coverage French syntax and semantics using Grail. In Proceedings of traitement automatique des langues naturelles (TALN), Montreal. System Demo [33] Moot, R. (2015a). Linear one: A theorem prover for first-order linear logic. https://github.com/RichardMoot/LinearOne. Accessed 16 Apr 2019. [34] Moot, R., A type-logical treebank for french, Journal of Language Modelling, 3, 229-264, (2015) [35] Moot, R.; Piazza, M., Linguistic applications of first order multiplicative linear logic, Journal of Logic, Language and Information, 10, 211-232, (2001) · Zbl 0984.03028 [36] Moot, R., & Retoré, C. (2012). The logic of categorial grammars: A deductive account of natural language syntax and semantics. Berlin: Springer. · Zbl 1261.03001 [37] Morrill, G. (2019). Parsing/theorem-proving for logical grammar CatLog3. Journal of Logic, Language and Information. https://doi.org/10.1007/s10849-018-09277-w. [38] Morrill, G., & Valentín, O. (2015). Computational coverage of TLG: The Montague test. In Proceedings CSSP 2015 Le onzième Colloque de Syntaxe et Sémantique à Paris (pp. 63-68). [39] Morrill, G.; Valentín, O.; Fadda, M., The displacement calculus, Journal of Logic, Language and Information, 20, 1-48, (2011) · Zbl 1233.03035 [40] Park, J. C. (1996). Quantifier scope, lexical semantics, and surface structure constituency. Technical report, University of Pennsylvania. [41] Partee, B.; Smelser, NJ (ed.); Baltes, PB (ed.), Montague grammar, (2001), Oxford [42] Pentus, M. (1995). Lambek grammars are context free. In Proceedings of logic in computer science (pp. 429-433). [43] Pentus, M., A polynomial-time algorithm for Lambek grammars of bounded order, Linguistic Analysis, 36, 441-471, (2010) [44] Pinker, S. (1994). The language instinct. Penguin Science. [45] Retoré, C. (2014). The Montagovian generative lexicon $$\Lambda Ty_n$$: A type theoretical framework for natural language semantics. In Proceedings of TYPES (pp. 202-229). 10.4230/LIPIcs.TYPES.2013.202. · Zbl 1359.03025 [46] Sarkar, A. (2000). Practical experiments in parsing using tree adjoining grammars. In Proceeding of TAG+5. [47] Savateev, Y. (2009). Product-free Lambek calculus is NP-complete. In Symposium on logical foundations of computer science (LFCS) (pp. 380-394). · Zbl 1211.03041 [48] Schwichtenberg, H. (1982). Complexity of normalization in the pure typed lambda-calculus. In The L. E. J. Brouwer centenary symposium (pp. 453-457). North-Holland. · Zbl 0537.03028 [49] Shapiro, S. (1991). Foundations without foundationalism: A case for second-order logic. Oxford: Clarendon Press. [50] Shieber, S., Evidence against the context-freeness of natural language, Linguistics & Philosophy, 8, 333-343, (1985) [51] Stanley, R. P. (2015). Catalan numbers. Cambridge: Cambridge University Press. [52] Thomason, R. (Ed.). (1974). Formal philosophy: Selected papers of Richard Montague. New Haven: Yale University Press. [53] Turing, A., Computing machinery and intelligence, Mind, 49, 433-460, (1950) [54] van Benthem, J. (1986). Categorial grammar. In Essays in logical semantics, chap. 7 (pp. 123-150). Dordrecht: Reidel. [55] van Dalen, D. (2013). Logic and structure (5th ed.). Berlin: Springer. [56] Wijnholds, G. (2011). Investigations into categorial grammar: Symmetric pregroup grammar and displacement calculus. Master’s thesis, Utrecht University.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.