WoLLIC'2004
11th Workshop on Logic, Language, Information and Computation
July 19th to 22nd, 2004

Fontainebleau Campus of Université Paris 12, France

Scientific Sponsorship
Interest Group in Pure and Applied Logics (IGPL)
European Association for Logic, Language and Information (FoLLI)
Association for Symbolic Logic (ASL)
European Association for Theoretical Computer Science (EATCS)
Sociedade Brasileira de Computação (SBC)
Sociedade Brasileira de Lógica (SBL)

Funding (expected)
 ??

Organisation
Centro de Informática, Universidade Federal de Pernambuco (CIn-UFPE) 
Laboratoire d'Algorithmique, Complexité et Logique, Université Paris XII (LACL-Paris12)

Title and Abstract of Tutorial Lectures

Web-based models of linear logic
by Thomas Ehrhard (Institut de Mathématiques de Luminy, Université de la Mediterranée Aix-Marseille II, France)

The prototype of web-based models of linear logic (LL) is Girard's category of coherence spaces and linear maps discovered in the mid eighties, which is at the origin of LL itself by revealing logical symmetries which were hidden in intutionistic logic.

Since then many other similar models have been discovered.In these models, objects are sets (called webs) equipped with additional "coherence" structures. Formulae are interpreted by such objects, and proofs as subsets of the webs which satisfy certain properties defined in terms of these coherence structures.

In this large class of models, we shall present in particular:

  • Hypercoherences, which are related to sequentiality and games;
  • Models based on phase spaces, which can be described in terms of "indexed linear logic";
  • Vector spaces models, where the webs are considered as "bases" of certain topological vector spaces and where morphisms are linear and continuous maps.

    Mathematical Reasoning -- Machines vs Humans
    by Manfred Kerber (School of Computer Science, The University of Birmingham, UK)

    It can be and has been argued that low-level object logic is not sufficient to model mathematical reasoning. New approaches to formalizing human mathematical reasoning have been developed, which concentrate on mechanizing some of the more human-oriented features of reasoning. In this tutorial strengths and weaknesses as well as open problems of machine-oriented and human-oriented reasoning will be presented.

    Real number computations and descriptive complexity
    by Klaus Meer (University of Southern Denmark, Odense, Denmark) (slides)

    In this tutorial we give an introduction into real number models of computation and descriptive complexity theory for such models. We consider the model introduced by Blum, Shub and Smale over the reals together with basic complexity classes in that model. Descriptive complexity theory for the BSS model is based on meta-finite model theory as introduced by Gr\"adel and Gurevich in general, and applied to real number computations by Gr\"adel and the author.

    We plan to discuss the following aspects:

  • Fagin like theorems for the BSS model
  • design of efficient algorithms for subclasses of hard problems that are formalizable in certain logics
  • counting and maximization problems in that framework. The talk is based on joint work with F. Cucker, E. Grädel and J. Makowsky.

    Natural Computing
    by Gheorghe Paun (University of Sevilla, Spain, and Institute of Mathematics of the Romanian Academy, Romania)

    (abstract soon to be announced)

    Expressive Power of Temporal Logics (slides)
    by Alexander Rabinovich (School of Computer Science, Tel Aviv University, Israel)

    The objectives of this talk are to survey classical and recent expressive completeness results and to provide some external yardsticks by which the expressive power of temporal logics can be measured.

    Last modified: August 4, 2004, 08:37:20 GMT-0300.