Prof Mark Steedman Seminar
Date: Monday, 30th July 2018, 11.00am - 12noon
Venue: The Australian Hearing Hub, Level 3, Room 3.610, Macquarie University
Speaker: Professor Mark Steedman, School of Informatics, The University of Edinburgh
Host: Professor Mark Johnson
Topic: A formal universal of natural language grammar
Formal universals are generalizations across natural language grammars that stem from the theory of grammar itself, and concern phenomena that the theory can and cannot in principle express. The present paper concerns the phenomenon of word-order variation, where the same grammatical categories can occur in different orders or permutations, either across or within languages. The question is, which permutations of a set of N grammatical elements are allowed in natural grammars? The question has been extensively studied by Cinque and others in the case of the noun phrase consisting of four elements Demonstrative Numerator Adjective Noun, as in English "These five young lads".
The present paper proposes that the permissible permutations are exactly the Separable Permutations, whose number grows as the Large Schroeder Number in N. The paper examines in detail the evidence from the NP construction in support of the hypothesis, and shows that a high degree of confidence can be assigned to its correctness. It also shows that some well-known cases of permutation among serial verb orders are also confined to separable permutations, and have similarly parsimonious analyses in CCG.
The paper concludes by briefly discussing some computational implications for natural language processing. The Large Schroeder Number grows much more slowly in N than N!, the number of all permutations. Search spaces for tasks like alignment in machine translation are correspondingly reduced.
Mark Steedman is Professor of Cognitive Science in the School of Informatics, The University of Edinburgh, working in Computational Linguistics, Artificial Intelligence, and Cognitive Science, on Generation of Meaningful Intonation for Speech by Artificial Agents, The Communicative Use of Gesture, Tense and Aspect, and Wide coverage parsing and robust semantics for Combinatory Categorial Grammar (CCG). He is also interested in Computational Musical Analysis and Combinatory Logic.