Special Session on Substructural logics, information and interaction

In the last decades, resource allocations problems have been widely investigated also from a computational point of view both in the AI and the logic community. In this presentation, I will show how substructural logics, and linear logic in particular, provide a principled modeling of resources allocation problems, which can be classified according to the types of goods agents trade. I will present a classification of resource allocation problems with the corresponding logical language to encode preferences and we will see how dropping contraction, weakening or exchange affects the type of goods on which agents express their valuations.
It is interesting to stress that, in this framework, the process of allocating goods to agents can be modeled by the notion of proof in some suitable fragments of linear logic.
This presentation is based on two joint works with Ulle Endriss (KR 2010 and ECAI 2010).

Epistemic actions such as acts of deductive reasoning, communication,
and observation, saturate our rational lives. Such actions play the
epistemically crucial roles that they do due to the fact that we lack
certain fantastic epistemic abilities – logical omniscience,
clairvoyance, and omniscience respectively. We will see how it is that
that the limits of such actions correspond to various subsystem
thresholds of the database corresponding to the total universe of
information. The dynamic properties of the actions that facilitate
such convergence are modeled by various substructural logics. In
detail, we will see how it is that the dynamic properties of deductive
information processing are modeled by the operational semantic frames
corresponding to the categorical grammar marked by mobiles;
bracket-sensitive commuting structures.

Keywords: epistemic actions, information, omniscience, operational
semantics, categorical grammar.

The syntactic calculus, as proposed by Lambek in 1961, is a logic

completely without structural rules: rules affecting multiplicity

(contraction, weakening) or structure (commutativity, associativity) of

the grammatical resources are not considered. Originally conceived with

linguistics in mind, Lambek’s calculus (both the ’61 and the

associative ’58 variant or its modern pregroup incarnation) have

found many models outside linguistics: as the logic for composition of

informational actions, for example, and in fields such as mathematical

morphology or quantum physics.

In terms of expressivity, Lambek’s calculi are strictly context-free.

The context-free limitation makes itself felt in situations

where syntactic and semantic composition seem to be out of sync:

long distance dependencies in syntax, or the dynamics of scoping

in semantics. Competing frameworks in the ‘mildly context-sensitive’

family (TAG, MG, MCFG, etc) handle such phenomena gracefully.

In the talk, I discuss the Lambek-Grishin calculus, a symmetric

generalization of the syntactic calculus allowing multiple conclusions.

I focus on two features that help resolve tensions at the syntax-semantics

interface:

-A continuation-passing-style interpretation, making contexts an

explicit part of the composition process. As a result of the richer

view on the mapping between syntax and semantics, the syntactic

source calculus itself can be kept very simple.

-Distributivity principles relating Lambek’s original type-forming

operations and their duals. These principles characterize syntactic

deformations under which interpretations are stable. They allow

a quite natural treatment of patterns beyond CF.

Background reading

Moortgat 2009, Symmetric categorial grammar. J Philosophical Logic

38 (6):681-710.