The information flow in natural language syntax and semantics establishes dependency patterns that go beyond the expressivity of context-free grammars. Examples in syntax are discontinuous dependencies as in long-distance displacement or cross-serial constructions. In semantics, scope construal often appears to be out of sync with syntactic composition.

In the tradition of extended rewriting systems, a family of grammar formalisms has emerged that deals with such patterns in a graceful way. These so-called 'mildly context-sensitive' formalisms combine controlled expressivity beyond CF with pleasant computational properties (polynomial parsability). In that sense, they throw an interesting light on the computational limitations of the human language processing device.

The thesis of this course is that we can gain a deeper understanding of these limitations by modeling grammars as substructural logics. In a substructural logic, assumptions take the form of finite material resources that are effectively 'used up' in the process of reasoning. We compare two recent resource-logical developments that address the balance between expressivity and complexity.

• Abstract Categorial Grammar (ACG): a compositional architecture formulated in terms of intuitionistic multiplicative linear logic. Surface forms and semantic interpretations are derived from an abstract 'tectogrammatical' source logic by means of compositional mappings. The Chomsky hierarchy and its mildly context-sensitive refinements are obtained in terms of a double complexity measure: the maximal order of constants in the source logic, and the order introduced by the mappings that send it to the target interpretations.

• Symmetric Categorial Grammar. ACGs are situated in the intuitionistic world, where judgements have a single conclusion. Symmetric categorial grammar goes beyond the intuitionistic restriction. In addition to the tensor operation of context-free Lambek calculus ('merge', fusion) one now has a dual fission operation; structure-preserving linear distributivity principles control the communication between these two. On the level of syntax, the distributivities establish information flow between syntactically detached parts. On a semantic level, grammaticality judgements are given a continuation-passing-style interpretation. Continuation-based semantics makes the context an explicit component of the computational process. As a result, apparent conflicts between semantic construal and syntactic composition are resolved.

In the box some useful entries from the Stanford Encyclopedia of Philosophy to situate the course in a wider context.