Formal Basis of a Language Universal

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 (CCG). The excluded non-separable permutations do in fact seem to be absent in a number of studies of cross-linguistic 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öder Number S_n-1. Since 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 paper 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.