Constraints in (computational) linguistics

The notion of constraints started to occupy a central position in linguistic theories from the introduction of unification in grammars.We propose in this chapter to explore the evolution of the notion of constraints in syntactic theories and how the computational and the linguistic perspective progressively get closer. In a first part, we propose an overview of constraint programming, showing how constraints not only introduce a way to control the processing (typically by reducing the search space), but also constitute an alternative way of representing and processing information (renewing the notion of declarativity). In a second part, we will detail the evolution of linguistic theories, from unification to constraints, showing how the notion of satisfaction can become the core of the theory. We will illustrate this evolution with the description of different theories, among which HPSG \citepPollard94, Optimality Theory \citepPrince93 and Property Grammars \citepBlache00. In the last section, we will situate this evolution in the model-theoretic perspective, and discuss how constraint can deeply renew our view of linguistic theory