Search
next up previous
Next: Joachim Lambek - Bilinear Up: Applied Logic / Logique Previous: Doug Howe - Combining

Francois Lamarche - Spaces for linguistic representations and the semantics of linear logic



FRANCOIS LAMARCHE, INRIA-Lorraine, 54602 Villers-les-Nancy Cedex, France
Spaces for linguistic representations and the semantics of linear logic


There are many areas of computer science that need a ``theory of spaces whose points are little spaces themselves''. For example in formal language theory (both as a discipline by itself and as an aid to linguistics), the individual words/sentences generated by a formal language are sets-with-structure. In this case the structure is very simple, being only a finite total ordering whose elements are marked by atomic symbols. But this structure, in addition to being variable from word to word (the vectors vary in length), is naturally endowed with a strong spatial character (words are definitely one-dimensional spaces). At the same time the set of all such words/sentences generated by a formal language has a strong intuitive, while hard to formalize, notion of ``neighborhood'' attached to it. Two sentences may be related by a simple substitution of words, or an active-passive transformation, which shows they are more closely related than two random samples. For another example replace the space of all sentences by the space of all their parsing trees. Here, the main difference is that the spatial character of the ``little spaces'' is not simply linear anymore, but tree-like.

So we have identified two levels of ``spaceness'', ``big'' and ``small'', the former serving as domain of variation, in the sense of Lawvere, for the latter. It turns out that once it is recognized, this situation appears in many areas of computer science and applied mathematics: concurrency theory (a process is a big space and its little spaces are its states), statistical learning theory, knowledge representation, rewriting theory, population biology...

We will present a general theory of such spaces. It is informed by two paradigms, that have to be adapted to fit together. One is the Grothendieck-Lavwere theory of toposes, with its connection both to geometry and to model theory. The second one is linear logic: The operations that generate and split little spaces will be seen as generalized multiplicative connectors of linear logic, while the structure that unites all the little spaces into a big one proceeds from the additive fragment of linear logic. The natural ``cement'' between these two paradigms will be seen to be a class of theories in linear universal algebra, which can be seen as a ``general theory of little spaces''.


next up previous
Next: Joachim Lambek - Bilinear Up: Applied Logic / Logique Previous: Doug Howe - Combining