James Rogers & Jeffrey Heinz

Language & Computation

Week One - 17.00-18.30 - Level: A

Room: N8


This advanced course introduces the model-theory of sub-regular classes of languages with particular attention to phonology and language learning. The Sub-Regular classes resolve the class of Regular languages into a rich hierarchy of complexity levels. The model-theoretic characterizations of these classes provide an abstract notion of complexity, independent of computational mechanisms, along with powerful techniques for exploring the complexity of linguistic constraints. This notion of complexity turns out to be highly relevant to phonology, with most constraints falling in the lower levels of the hierarchy, and to formal learnability (Identification in the Limit). This perspective on complexity is also of value to those working with structures more complicated than strings.

The first session provides motivatation, the foundations of model-theory and phonology, and an overview of the Sub-Regular hierarchies. The second, third and fourth sessions present the Sub-Regular classes along two dimensions: the choice of signature (successor or precedence) and the power of the logic (restricted propositional, propositional, first-order, or monadic second-order). The last session covers areas of current research, including signatures utilizing both precedence and successor, Sub-Regular classes based on phonological tiers, Sub-Regular classes of transductions, and model-theoretic approaches to autosegmental phonology.