Formal Basis of a Language Universal

Formal Basis of a Language Universal Miloˇs Stanojevi´c University of Edinburgh School of Informatics m.stanojevic@ed.ac.uk Mark Steedman University of Edinburgh School of Informatics steedman@inf.ed.ac.uk Steedman (2020) proposes as a formal universal of natural language grammar that grammatical permutations of the kind that have given rise to transformational rules are limited to a class known to mathematicians and computer scientists as the “separable” permutations. This class of permutations is exactly the class that can be expressed in combinatory categorial grammars (CCGs). The excluded non-separable permutations do in fact seem to be absent in a number of studies of crosslinguistic variation in word order in nominal and verbal constructions. The number of permutations that are separable grows in the number n of lexical elements in the construction as the Large Schr¨oder Number Sn−1. Because that number grows much more slowly than the n! number of all permutations, this generalization is also of considerable practical interest for computational applications such as parsing and machine translation. The present article examines the mathematical and computational origins of this restriction, and the reason it is exactly captured in CCG without the imposition of any further constraints. 1. Introduction Permutation of elements in a construction, either within a single language or across languages, creating discontinuous semantic dependencies, is a widespread character- istic of natural languages that has motivated transformational rules (Chomsky 1957, passim), among other expressive grammar formalisms. Steedman (2020) proposes as a formal universal of natural language grammar that grammatical permutations are limited to a class known to mathematicians and computer scientists as the “separable” permutations, which are those orders over which a tree can be constructed such that all leaves descending from any node form a continuous subset i . . . j of the original ordered set 1, . . . , n. The evidence for this claim is based on a number of studies of two data sets of alternations in two major constructions. The first concerns the permutations of the four Submission received: 29 January 2019; revised version received: 29 July 2020; accepted for publication: 10 October 2020. https://doi.org/10.1162/COLI a 00394 © 2021 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 47, Number 1 elements Det(erminer) Num(erator) Adj(ective) N(oun) that surface in that order in English noun phrases (NP) like “These five young lads,” but in Yoruba and many other languages are found in the mirror-image permutation. The crosslinguistic variation in this construction has been studied by Cinque (2005) and Abels and Neeleman (2012) (among others) for languages with a single dominant order, and also within a single language with very free word order for the same construction by Nchare (2012). The second construction is the verb group, also consisting of four elements, which we can think mnemonically of as the verb-sequence “must have been dancing,” whose varia- tions with various verb-types both across and within the various Germanic languages and dialects, has been studied by Wurmbrand (2004; 2006) and Abels …

Content truncated to 500 words