Introduction to linguistic computation

An explanatory adequate linguistic theory, according to Chomsky 1965, is an abstraction, over a finite set of empirical phenomena, that is able to predict facts that are not included in the finite empirical domain, including the degree of difficulty perceived during sentence processing. Following Turing (1950), a first necessary step is the explicit (procedural) definition of the components used in the theory as well as the exact task we aim to solve.
In this course, our task is the generation of well-formed linguistic expressions given some relevant (structural) constraints. The notions of "well-formed" sentence, lexicon, feature, structure building operations will be the core definitions provided. During these classes we will see various ways to approach the structure building task from an algorithmic (that is, computational) perspective. We will discuss how these different approaches have a different computational complexity cost (expressed in terms of time and memory resources used) and how this precise notion of complexity can be related to the perception of difficulty in various performance tasks (i.e. comprehension/parsing and production/generation).