{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T13:34:15Z","timestamp":1767879255355,"version":"3.49.0"},"reference-count":75,"publisher":"MIT Press","issue":"1","license":[{"start":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:00:00Z","timestamp":1614988800000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,4,21]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 \u201cseparable\u201d 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.<\/jats:p><jats:p>The number of permutations that are separable grows in the number n of lexical elements in the construction as the Large Schr\u00f6der Number Sn\u22121. 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.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1162\/coli_a_00394","type":"journal-article","created":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T18:59:47Z","timestamp":1614970787000},"page":"9-42","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":3,"title":["Formal Basis of a Language Universal"],"prefix":"10.1162","volume":"47","author":[{"given":"Milo\u0161","family":"Stanojevi\u0107","sequence":"first","affiliation":[{"name":"University of Edinburgh, School of Informatics. m.stanojevic@ed.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Steedman","sequence":"additional","affiliation":[{"name":"University of Edinburgh, School of Informatics. steedman@inf.ed.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2021,4,21]]},"reference":[{"key":"2022041319414554200_bib1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s10828-016-9082-9","article-title":"The fundamental left\u2013right asymmetry in the Germanic verb cluster","volume":"19","author":"Abels","year":"2016","journal-title":"Journal of Comparative Germanic Linguistics"},{"key":"2022041319414554200_bib2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1111\/j.1467-9612.2011.00163.x","article-title":"Linear asymmetries and the LCA","volume":"15","author":"Abels","year":"2012","journal-title":"Syntax"},{"key":"2022041319414554200_bib3","volume-title":"A Syntax of Substance","author":"Adger","year":"2013"},{"key":"2022041319414554200_bib4","first-page":"129","article-title":"On pop-stacks in series","volume":"19","author":"Avis","year":"1981","journal-title":"Utilitas Mathematica"},{"key":"2022041319414554200_bib5","article-title":"Neural machine translation by jointly learning to align and translate","volume-title":"Proceedings of the International Conference on Learning Research","author":"Bahdanau","year":"2015"},{"key":"2022041319414554200_bib6","first-page":"211","article-title":"Multi-Modal Combinatory Categorial Grammar","volume-title":"Proceedings of 11th Annual Meeting of the European Association for Computational Linguistics","author":"Baldridge","year":"2003"},{"key":"2022041319414554200_bib7","article-title":"The derivational generative power, or, scrambling is beyond LCFRS","author":"Becker","year":"1992"},{"issue":"5","key":"2022041319414554200_bib8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","article-title":"Pattern matching for permutations","volume":"65","author":"Bose","year":"1998","journal-title":"Information Processing Letters"},{"key":"2022041319414554200_bib9","first-page":"613","article-title":"Cross-serial dependencies in Dutch","volume":"13","author":"Bresnan","year":"1982","journal-title":"Linguistic Inquiry"},{"key":"2022041319414554200_bib10","unstructured":"Cain, Bruce Dwayne . 2000. Dhivehi (Maldivian): A synchronic and diachronic study. Ph.D. thesis, Cornell, Ithaca, NY."},{"key":"2022041319414554200_bib11","first-page":"9","article-title":"Flexible composition, multiple adjoining and word order variation","volume-title":"Proceedings of the Ninth International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+9)","author":"Chen-Main","year":"2008"},{"key":"2022041319414554200_bib12","doi-asserted-by":"crossref","DOI":"10.1515\/9783112316009","volume-title":"Syntactic Structures","author":"Chomsky","year":"1957"},{"key":"2022041319414554200_bib13","first-page":"184","article-title":"Remarks on nominalization","volume-title":"Readings in English Transformational Grammar","author":"Chomsky","year":"1970"},{"key":"2022041319414554200_bib14","first-page":"383","article-title":"Bare phrase structure","volume-title":"Government and Binding Theory and the Minimalist Program","author":"Chomsky","year":"1995"},{"key":"2022041319414554200_bib15","volume-title":"The Minimalist Program","author":"Chomsky","year":"1995"},{"key":"2022041319414554200_bib16","first-page":"89","article-title":"Minimalist inquiries: The framework","volume-title":"Step by Step: Essays in Minimalist Syntax in Honor of Howard Lasnik","author":"Chomsky","year":"2000"},{"key":"2022041319414554200_bib17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7551\/mitpress\/4056.003.0004","article-title":"Derivation by phase","volume-title":"Ken Hale: A Life in Language","author":"Chomsky","year":"2001"},{"key":"2022041319414554200_bib18","first-page":"139","article-title":"Coping with syntactic ambiguity","volume":"8","author":"Church","year":"1982","journal-title":"Computational Linguistics"},{"key":"2022041319414554200_bib19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1162\/0024389054396917","article-title":"Deriving Greenberg\u2019s universal 20 and its exceptions","volume":"36","author":"Cinque","year":"2005","journal-title":"Linguistic Inquiry"},{"key":"2022041319414554200_bib20","first-page":"77","article-title":"The fundamental left-right asymmetry of natural languages","volume":"17","author":"Cinque","year":"2007","journal-title":"Working Papers in Linguistics"},{"key":"2022041319414554200_bib21","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262014168.001.0001","volume-title":"The Syntax of Adjectives","author":"Cinque","year":"2010"},{"key":"2022041319414554200_bib22","article-title":"On the movement account of Greenberg\u2019s universal 20: Refinements and replies: Materials","author":"Cinque","year":"2013"},{"key":"2022041319414554200_bib23","first-page":"43","article-title":"The cartography of syntactic structures","volume":"2","author":"Cinque","year":"2008","journal-title":"Studies in Linguistics: CISCL Working Papers on Language and Cognition"},{"key":"2022041319414554200_bib24","doi-asserted-by":"crossref","DOI":"10.1002\/9781444324044.ch8","article-title":"Unsupervised learning and grammar induction","volume-title":"The Handbook of Computational Linguistics and Natural Language Processing","author":"Clark","year":"2010"},{"key":"2022041319414554200_bib25","first-page":"21","article-title":"The Katu noun phrase","volume":"3","author":"Costello","year":"1969","journal-title":"Mon-Khmer Studies"},{"key":"2022041319414554200_bib26","doi-asserted-by":"crossref","first-page":"5842","DOI":"10.1073\/pnas.1320525111","article-title":"Language learners privilege structured meaning over surface frequency","volume":"111","author":"Culbertson","year":"2014","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2022041319414554200_bib27","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.cognition.2011.10.017","article-title":"Learning biases predict a word order universal","volume":"122","author":"Culbertson","year":"2012","journal-title":"Cognition"},{"key":"2022041319414554200_bib28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.18653\/v1\/P16-1004","article-title":"Language to logical form with neural attention","volume-title":"Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Dong","year":"2016"},{"key":"2022041319414554200_bib29","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-94-015-6878-4_7","article-title":"Type-raising, functional composition, and nonconstituent coordination","volume-title":"Categorial Grammars and Natural Language Structures","author":"Dowty","year":"1988"},{"key":"2022041319414554200_bib30","first-page":"81","article-title":"On the order of demonstrative, numeral, adjective, and noun","volume":"94","author":"Dryer","year":"2018","journal-title":"Language"},{"key":"2022041319414554200_bib31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801136","volume-title":"An Introduction to Mathematical Reasoning: Numbers, Sets and Functions","author":"Eccles","year":"1997"},{"key":"2022041319414554200_bib32","doi-asserted-by":"crossref","first-page":"79","DOI":"10.3115\/981863.981874","article-title":"Efficient normal-form parsing for Combinatory Categorial Grammar","volume-title":"Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics","author":"Eisner","year":"1996"},{"key":"2022041319414554200_bib33","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1515\/9783110197723.3.163","article-title":"Parallels in clausal and nominal periphery","volume-title":"Phases of Interpretation","author":"Giusti","year":"2006"},{"key":"2022041319414554200_bib34","doi-asserted-by":"crossref","DOI":"10.1201\/b16005","volume-title":"Handbook of Mathematical Induction: Theory and Applications","author":"Gunderson","year":"2014"},{"key":"2022041319414554200_bib35","volume-title":"Word Order Universals","author":"Hawkins","year":"1983"},{"key":"2022041319414554200_bib36","first-page":"465","article-title":"Normal-form parsing for Combinatory Categorial Grammars with generalized composition and type-raising","volume-title":"Proceedings of the 23nd International Conference on Computational Linguistics","author":"Hockenmaier","year":"2010"},{"key":"2022041319414554200_bib37","article-title":"Non-local scrambling: The equivalence of TAG and CCG revisited","volume-title":"Proceedings of the 9th International Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+9)","author":"Hockenmaier","year":"2008"},{"key":"2022041319414554200_bib38","volume-title":"Yapese Reference Grammar","author":"Jensen","year":"1977"},{"key":"2022041319414554200_bib39","first-page":"167","article-title":"Complexity of scrambling: A new twist to the competence-performance distinction","volume-title":"Tree-Adjoining Grammar","author":"Joshi","year":"2000"},{"key":"2022041319414554200_bib40","first-page":"31","article-title":"The convergence of mildly context-sensitive formalisms","volume-title":"Processing of Linguistic Structure","author":"Joshi","year":"1991"},{"key":"2022041319414554200_bib41","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1017\/CBO9780511597855.007","article-title":"Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?","volume-title":"Natural Language Parsing: Psychological, Computational, and Theoretical Perspectives","author":"Joshi","year":"1985"},{"key":"2022041319414554200_bib42","volume-title":"The Art of Computer Programming, Volume 1: Fundamental Algorithms","author":"Knuth","year":"1968"},{"key":"2022041319414554200_bib43","first-page":"460","article-title":"Dependency trees and the strong generative capacity of CCG","volume-title":"Proceedings of the 12th Conference of the European Chapter of the ACL","author":"Koller","year":"2009"},{"key":"2022041319414554200_bib44","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1162\/COLI_a_00219","article-title":"Lexicalization and generative power in CCG","volume":"41","author":"Kuhlmann","year":"2015","journal-title":"Computational Linguistics"},{"key":"2022041319414554200_bib45","doi-asserted-by":"crossref","DOI":"10.1201\/9781439888926","volume-title":"A Concise Introduction to Pure Mathematics","author":"Liebeck","year":"2010"},{"key":"2022041319414554200_bib46","doi-asserted-by":"crossref","first-page":"155","DOI":"10.3389\/fpsyg.2018.00155","article-title":"ULTRA: Universal Grammar as a Universal Parser","volume":"9","author":"Medeiros","year":"2018","journal-title":"Frontiers in Psychology"},{"key":"2022041319414554200_bib47","doi-asserted-by":"crossref","first-page":"317","DOI":"10.15398\/jlm.v3i2.112","article-title":"Predicting word order universals","volume":"3","author":"Merlo","year":"2015","journal-title":"Journal of Language Modelling"},{"key":"2022041319414554200_bib48","doi-asserted-by":"crossref","first-page":"1","DOI":"10.5334\/gjgl.149","article-title":"Movement and structure effects on universal 20 word order frequencies: A quantitative study","volume":"3","author":"Merlo","year":"2018","journal-title":"Glossa"},{"key":"2022041319414554200_bib49","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1075\/sl.41.2.02mos","article-title":"Teop\u2013an oceanic language with multifunctional verbs, nouns and adjectives","volume":"41","author":"Mosel","year":"2017","journal-title":"Studies in Language"},{"key":"2022041319414554200_bib50","unstructured":"Nchare, Abdoulaye Laziz . 2012. The Grammar of Shupamem. Ph.D. thesis, New York University."},{"key":"2022041319414554200_bib51","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1515\/9783110852820.361","article-title":"Generalised conjunction and type ambiguity","volume-title":"Meaning, Use, and Interpretation of Language","author":"Partee","year":"1983"},{"key":"2022041319414554200_bib52","doi-asserted-by":"crossref","DOI":"10.1515\/9783110861846","volume-title":"Kilivila: The Language of the Trobriand Islanders","author":"Senft","year":"1986"},{"issue":"2","key":"2022041319414554200_bib53","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1137\/0404025","article-title":"Bootstrap percolation, the Schroder numbers, and the N-kings problem","volume":"4","author":"Shapiro","year":"1991","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2022041319414554200_bib54","first-page":"68","article-title":"Derivational minimalism","volume-title":"International Conference on Logical Aspects of Computational Linguistics","author":"Stabler","year":"1996"},{"key":"2022041319414554200_bib55","first-page":"617","article-title":"Computational perspectives on minimalism","volume-title":"Oxford Handbook of Linguistic Minimalism","author":"Stabler","year":"2011"},{"key":"2022041319414554200_bib56","doi-asserted-by":"crossref","first-page":"44","DOI":"10.18653\/v1\/D15-1005","article-title":"Reordering grammar induction","volume-title":"Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing","author":"Stanojevi\u0107","year":"2015"},{"key":"2022041319414554200_bib57","doi-asserted-by":"crossref","first-page":"523","DOI":"10.2307\/414385","article-title":"Dependency and coordination in the grammar of Dutch and English","volume":"61","author":"Steedman","year":"1985","journal-title":"Language"},{"key":"2022041319414554200_bib58","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6591.001.0001","volume-title":"The Syntactic Process","author":"Steedman","year":"2000"},{"key":"2022041319414554200_bib59","first-page":"19","article-title":"Interfaces and the grammar","volume-title":"Proceedings of the 24th West Coast Conference on Formal Linguistics","author":"Steedman","year":"2005"},{"key":"2022041319414554200_bib60","volume-title":"Taking Scope: The Natural Semantics of Quantifiers","author":"Steedman","year":"2012"},{"key":"2022041319414554200_bib61","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1353\/lan.2014.0010","article-title":"The surface-compositional semantics of English intonation","volume":"90","author":"Steedman","year":"2014","journal-title":"Language"},{"key":"2022041319414554200_bib62","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1353\/lan.2020.0043","article-title":"A formal universal of natural language grammar","volume":"96","author":"Steedman","year":"2020","journal-title":"Language"},{"key":"2022041319414554200_bib63","first-page":"239","article-title":"1 \u2026 3\u20132","volume-title":"The Oxford Handbook of Linguistic Interfaces","author":"Svenonius","year":"2007"},{"key":"2022041319414554200_bib64","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1515\/tlir.1983.3.1.89","article-title":"The possessor that ran away from home","volume":"3","author":"Szabolcsi","year":"1983","journal-title":"Linguistic Review"},{"key":"2022041319414554200_bib65","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1163\/9789004373174_004","article-title":"The noun phrase","volume-title":"Syntax and Semantics 27: The Syntactic Structure of Hungarian","author":"Szabolcsi","year":"1994"},{"key":"2022041319414554200_bib66","doi-asserted-by":"crossref","unstructured":"Tryon, Darrell . 1967. The Languages of the Loyalty Islands. Ph.D. thesis, The Australian National University. DOI: https:\/\/doi.org\/10.1002\/j.1834-4461.1967.tb00937.x","DOI":"10.1002\/j.1834-4461.1967.tb00937.x"},{"key":"2022041319414554200_bib67","article-title":"Schr\u00f6der number","volume-title":"MathWorld","author":"Weisstein","year":"2018"},{"issue":"1\u20133","key":"2022041319414554200_bib68","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0012-365X(96)83023-8","article-title":"Generating trees and forbidden subsequences","volume":"157","author":"West","year":"1996","journal-title":"Discrete Mathematics"},{"key":"2022041319414554200_bib69","doi-asserted-by":"crossref","first-page":"784","DOI":"10.3115\/992133.992190","article-title":"Shake-and-bake translation","volume-title":"Proceedings of the 14th conference on Computational linguistics","author":"Whitelock","year":"1992"},{"key":"2022041319414554200_bib70","volume-title":"Representation Theory","author":"Williams","year":"2003"},{"key":"2022041319414554200_bib71","doi-asserted-by":"crossref","first-page":"152","DOI":"10.3115\/981863.981884","article-title":"A polynomial-time algorithm for statistical machine translation","volume-title":"Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics","author":"Wu","year":"1996"},{"key":"2022041319414554200_bib72","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1075\/la.69.05wur","article-title":"West Germanic verb clusters: The empirical domain","volume-title":"Verb Clusters: A Study of Hungarian, German, and Dutch","author":"Wurmbrand","year":"2004"},{"key":"2022041319414554200_bib73","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1002\/9780470996591.ch75","article-title":"Verb clusters, verb raising, and restructuring","volume-title":"The Blackwell Companion to Syntax","author":"Wurmbrand","year":"2006"},{"key":"2022041319414554200_bib74","first-page":"475","article-title":"Stochastic Lexicalized Inversion Transduction Grammar for alignment","volume-title":"Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL\u201905)","author":"Zhang","year":"2005"},{"key":"2022041319414554200_bib75","first-page":"25","article-title":"Factorization of Synchronous Context-Free Grammars in linear time","volume-title":"NAACL Workshop on Syntax and Structure in Statistical Translation (SSST)","author":"Zhang","year":"2007"}],"updated-by":[{"DOI":"10.1162\/coli_x_00432","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T00:00:00Z","timestamp":1649030400000}}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/47\/1\/9\/2008440\/coli_a_00394.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/47\/1\/9\/2008440\/coli_a_00394.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T12:55:46Z","timestamp":1724590546000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/47\/1\/9\/97333\/Formal-Basis-of-a-Language-Universal"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3]]},"references-count":75,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,4,21]]},"published-print":{"date-parts":[[2021,4,21]]}},"URL":"https:\/\/doi.org\/10.1162\/coli_a_00394","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,3]]},"published":{"date-parts":[[2021,3]]}}}