jeudi 21 octobre 2010

Seminaire PPS à 11h !

Chers tous,
le séminaire PPS c'est ce matin à 11h (salle OC2)!
On espère vous y voir nombreux-ses.

Reversing Higher Order Pi

The notion of reversible computation is attracting increasing interest
because of its potential applications in diverse fields. Of particular
interest is the application of reversible computation ideas to the study
of programming abstractions for reliable systems. In this paper, we
continue the study undertaken by Danos and Krivine on reversible CCS by
devising a simple syntax and reduction semantics for a reversible HOpi$
calculus, with a novel way of defining reversible reductions that
preserves the associativity and commutativity of the parallel operator. We
prove that reversibility in our calculus is causally consistent and that
one can encode faithfully reversible HOpi into a variant of HOpi

--
Jean Krivine

Laboratoire PPS
CNRS& Université Paris 7 Case 7014
75205 PARIS Cedex 13 FRANCE
(W) +33 1 44 27 86 79
(M) +33 6 16 25 49 45

mardi 19 octobre 2010

seminaire PPS Jeudi 21/10 11h, en salle 0C02

Chers tous,
le prochaine seminaire PPS est:


Jeudi 21 Octobre, 11h, en salle 0C02

Claudio Mezzina (INRIA Grenoble):

Reversing Higher Order Pi

The notion of reversible computation is attracting increasing interest
because of its potential applications in diverse fields. Of particular
interest is the application of reversible computation ideas to the study
of programming abstractions for reliable systems. In this paper, we
continue the study undertaken by Danos and Krivine on reversible CCS by
devising a simple syntax and reduction semantics for a reversible HOpi$
calculus, with a novel way of defining reversible reductions that
preserves the associativity and commutativity of the parallel operator. We
prove that reversibility in our calculus is causally consistent and that
one can encode faithfully reversible HOpi into a variant of HOpi

dimanche 26 septembre 2010

seminaire PPS: mardi 28/9 et jeudi 30/9

Chers tous,

nous avons deux seminaires cette semaine:


** Jeudi 30 Septembre, 11h, en salle 0C02 **
Jean Krivine (PPS):

Understanding stochastic systems with non local causality analysis
http://www.pps.jussieu.fr/seminaire/sem2010/abstracts/krivine

**Mardi 28 Septembre, 10h, en salle 5C03 **
Marco Gaboardi (Université de Bologne) :

Definability and Full abstraction for a Linear PCF
http://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi


Cordialement,

claudia


> Chers tous,
> a cause de la greve du 23/9, on déplace le séminaire de Marco Gaboardi a
>
> ** mardi 28 Septembre, 10h, en salle 5C03 **
>
> juste avant le GdT Semantique.
>
> Marco Gaboardi (Université de Bologne) :
> Definability and Full abstraction for a Linear PCF
>
> https://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi
>
> A bientot.
>
> Claudia
>
>
>> Chers tous,
>>
>> le séminaire PPS reprend après l'été,
>>
>> le jeudi 23 Septembre, 11h, en salle 0C02
>>
>> avec un séminaire de
>>
>> Marco Gaboardi (Université de Bologne) :
>> Definability and Full abstraction for a Linear PCF
>>
>> https://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi
>>
>> ------------------------------------------------------
>> A suivre:
>>
>> Jeudi 30 Septembre, 11h, en salle 0C02
>> Jean Krivine (PPS):
>> Understanding stochastic systems with non local causality analysis
>>
>>
>>
>>
>>
>>
>
>

mercredi 22 septembre 2010

seminaire PPS du 23/9 - change de date et salle

Chers tous,
a cause de la greve du 23/9, on déplace le séminaire de Marco Gaboardi a

** mardi 28 Septembre, 10h, en salle 5C03 **

juste avant le GdT Semantique.

Marco Gaboardi (Université de Bologne) :
Definability and Full abstraction for a Linear PCF

https://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi

A bientot.

Claudia


> Chers tous,
>
> le séminaire PPS reprend après l'été,
>
> le jeudi 23 Septembre, 11h, en salle 0C02
>
> avec un séminaire de
>
> Marco Gaboardi (Université de Bologne) :
> Definability and Full abstraction for a Linear PCF
>
> https://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi
>
> ------------------------------------------------------
> A suivre:
>
> Jeudi 30 Septembre, 11h, en salle 0C02
> Jean Krivine (PPS):
> Understanding stochastic systems with non local causality analysis
>
>
>
>
>
>

mercredi 15 septembre 2010

seminaire PPS Jeudi 23/9

Chers tous,

le séminaire PPS reprend après l'été,

le jeudi 23 Septembre, 11h, en salle 0C02

avec un séminaire de

Marco Gaboardi (Université de Bologne) :
Definability and Full abstraction for a Linear PCF

https://www.pps.jussieu.fr/seminaire/sem2010/abstracts/gaboardi

------------------------------------------------------
A suivre:

Jeudi 30 Septembre, 11h, en salle 0C02
Jean Krivine (PPS):
Understanding stochastic systems with non local causality analysis

mercredi 21 juillet 2010

seance seminaire PPS demain 22/7, 11h salle 3E91

Chers tous,
on va avoir une seance exceptionnelle du seminaire PPS demain,
Jeudi 22/7, 11h salle 3E91:


Michel P. Schellekens (National University of Ireland, Cork )

Towards predictable software-hardware co-design

In this talk we outline new ideas towards the design of predictable
software-hardware co-design. Predictable computing is required in a variety
of applications, including safety-critical systems and low-power design. For
the case of low-power design, minimizing average power is crucial. We will
show how both software and hardware can be designed in a modular way such
that the average-case cost of computing amounts to a linear combination of
the average-cost of the basic components. As such, for modular
software-hardware co-design based on these principles, the average cost of
computing can be analyzed in a straightforward way, circumventing costly
simulation.

jeudi 3 juin 2010

seminaire PPS Jeudi 3/6, 11h sous-marin!

A cause du demenagement de Paris 6, la salle 3E91 n'existe plus. Rendez
vous au sousmarin.

D.

Claudia.Faggian@pps.jussieu.fr a écrit :
> Chers tous,
> le prochaine seminaire PPS est
>
> le Jeudi 3 Juin, 11h salle 3E91
>
> Silvia Crafa (Padova)
>
> A Logic for True Concurrency
> (joint work with Paolo Baldan)
> We propose a logic for true concurrency whose formulae predicate about
> events in computations and their causal dependencies. The induced logical
> equivalence is hereditary history preserving bisimilarity, and fragments
> of the logic can be identified which correspond to other true concurrent
> behavioural equivalences in the literature: step, pomset and history
> preserving bisimilarity. Standard Hennessy-Milner logic, thus
> (interleaving) bisimilarity, is also recovered as a fragment. We believe
> that this contributes to a rational presentation of the true concurrent
> spectrum and to a deeper understanding of the relations between the
> involved behavioural equivalences.
>
>

lundi 31 mai 2010

seminaire PPS Jeudi 3/6, 11h salle 3E91

Chers tous,
le prochaine seminaire PPS est

le Jeudi 3 Juin, 11h salle 3E91

Silvia Crafa (Padova)

A Logic for True Concurrency
(joint work with Paolo Baldan)
We propose a logic for true concurrency whose formulae predicate about
events in computations and their causal dependencies. The induced logical
equivalence is hereditary history preserving bisimilarity, and fragments
of the logic can be identified which correspond to other true concurrent
behavioural equivalences in the literature: step, pomset and history
preserving bisimilarity. Standard Hennessy-Milner logic, thus
(interleaving) bisimilarity, is also recovered as a fragment. We believe
that this contributes to a rational presentation of the true concurrent
spectrum and to a deeper understanding of the relations between the
involved behavioural equivalences.

dimanche 2 mai 2010

seminaire PPS Jeudi 6/5, 11h salle 3E91

Chers tous,
le prochaine seminaire PPS est

Jeudi 6 Mai, 11h salle 3E91

Michele Abrusci (Roma 3)

Quelques thèmes de la théorie de la démonstration du XXe siècle, vus
d'aujourd'hui

Selon les approches et les résultats plus récents de la recherche logique
(surtout, dans le domaine de la logique linéaire et de la ludique), on
présentera dans une forme nouvelle ces thèmes de la théorie de la
démonstration du XXe siècle:
1. Le programme d'Hilbert et le traitement de la quantification par Hilbert.
2. L'arithmétique et l'omega-règle, les entiers et les ordinaux transfinis.

mardi 13 avril 2010

seminaire PPS Jeudi 15/4

Chers tous,
prochaine seminaire PPS:

Jeudi 15 Avril, 11h salle 3E91

Paolo Di Giamberardino (LIPN, Paris)

Jump from parallel to sequential proofs: exponentials.

In previous works, by importing ideas from game semantics (notably
Faggian-Maurel-Curien's ludics nets), we defined a new class of
multiplicative/additive polarized proof nets, called J-proof nets. The
distinctive feature of J-proof nets with respect to other proof net
syntaxes, is the possibility of representing proof nets which are
partially sequentialized, by using jumps (that is, untyped extra edges) as
sequentiality constraints. Starting from this result, in the present work
we extend J-proof nets to take into account structural rules: more
precisely, we show that in J-proof nets the familiar linear logic notion
of exponential box could be represented by means of jumps. As consequence,
we get a syntax for polarized nets where the usual nesting condition on
exponential boxes is relaxed, allowing a partial superposition of boxes.
Moreover, we prove that, even in case of ''superposed'' boxes, reduction
enjoys confluence and strong normalization, using Gandy's method.

mardi 6 avril 2010

[Fwd: Vendredi 9 avril à l'IRCAM : Espaces de Chu et musique (10h-18h)]



Merci de bien vouloir transmettre l'information à tous ceux qui pourraient être intéressés par cette séance du séminaire MaMuX.
[Avec nos excuses pour les envois multiples]

---


Neuvième saison du Séminaire MaMuX
Mathématiques, musique et relations avec d'autres disciplines 
IRCAM, salle C. Shannon (matinée) et I. Stravinsky (après-midi)
1, place Igor-Stravinsky 75004 Paris
(Entrée libre dans la mesure des places disponibles) 

Vendredi 9 avril 2010

de 10 à 18h
 
Espaces de Chu et musique 

Cette séance exceptionnelle du Séminaire MaMuX est consacrée aux espaces de Chu, un concept dont on essaiera de présenter les aspects théoriques touchant à la fois à de questions de logique, de géométrie et d'informatique et leurs applications en musique. Si d'un point mathématique un espace de Chu n'est qu'une simple matrice de transformations, ses lignes ayant la propriété de transformer « en avant » [forwards] et ses colonnes celle de transformer « en arrière » [backwards], ce concept est très profond car il joue un rôle d'unificateur par rapport à plusieurs structures mathématiques, telles les structures de relations (ensembles, graphes dirigés, ensembles partiellement ordonnés, …), les structures algébriques (groupes, anneaux, modules, espaces vectoriels, …) et les structures topologiques (espaces topologiques, groupes abéliens localement compacts, …! ).

La matinée se déroulera sous la forme d'un cours introductif au cadre théorique général animé par Vaughan Pratt, l'un des spécialistes de ce domaine. Dans l'après-midi on se concentrera sur trois aspects de ce formalisme qui sont susceptibles d'ouvrir des applications nouvelles en musique.


Programme de la journée

Matinée pédagogique (salle C. Shannon, niveau -2) :
  • 10h - 12h Vau! ghan Pratt&nb sp; – A Chu Space Tutorial
Après-midi (salle I. Stravinsky) :
  • 14h30 - 14h45 Moreno Andreatta & Carlos Agon  – Introduction to the session
  • 14h45 – 15h30 Paul-André Melliès - Chu Spaces and the construction of a duality
  • 15h30 – 16h15 Timothy Porter – The Geometry of Observation
  • Break
  • 17h00 - 17h45 Vaughan Pratt – Evolution of music and speech: a Chu perspective
  • Discussion finale
Résumés :

Vaughan Pratt (Stanford University) : A Chu space tutorial
Selected topics from Chapters 1-4 of « Chu Spaces », Notes for the School on Category Theory and Applications University of Coimbra [http://boole.stanford.edu/pub/coimbra.pdf]

Paul-André Melliès (CNRS/PPS-Jussieu) : Chu spaces and the construction of a duality
In this tutorial talk, I will review the elegant description of the Chu construction discovered by Pavlovic in the 1990s. In particular, I will explain how to see a Chu space as a canonical solution to the question of extracting a duality from the mere existence of a point ! (or pole) in a category. I will also relate the Chu construction to ot her important ideas in logic, this including the Dialectica interprétation by Godel (after ideas by Hyland and de Paiva) together with the dynamic and game-theoretic interpretation of the logical interaction.

Timothy Porter (Univer! sity of Wales, Bangor) : The Geometry of Observation
We start with a simple situation: an observer makes observations about 'something'.  The observer has a list of attributes and is observing a set of objects, and notes whether objects have particular attributes or not. (This gives a 2-valued Chu space and is general enough for us -  for the moment.)  The question is how to 'organise' the observations with respect to spatial, logical, .... aspects of the situation. We will look at classical constructions of Cech and Vietoris from the 1920s from this general point of view, and then look at a more recent uses of similar constructions in Physics and more generally in! Topological Data Analysis.  We will also brief look at Formal Co ncept Analysis, a method from A.I. and its relationship with these ideas.

Vaughan Pratt (Stanford University) : Evolution of music and speech: a Chu perspective
1.  Time-tone interference in pitch and rhythm.
2.  Common roots of timbre and harmony.
3.  Compositionality in composition: the sequential soloist, the paralle! l orchestra, etc.

La séance de l'après-midi est accessible en ligne (en directe) à travers le service "Ircam On Air". Instructions pour visionner la conférence à l'adresse :
http://video.ircam.fr/index.html
[English version at : http://video.ircam.fr/index.html.en] 

Le programme complet de la séance, avec références bibliographiques, est disponible en pdf à l'adresse :

Planning du séminaire : 
- Samedi 10 octobre 2009 : Géométrie de l'information et musique 
- Vendredi 13 novembre 2009 : Géométrisation de la logique et de l'informatique musicale. 
- Vendredi 4 décembre 2009 : Approche fonctorielle en informatique musicale 
- Samedi 5 décembre 2009 : école mathématique pour musiciens et autres non-mathématiciens animée par Pierre Cartier (Salle Igor Stravinsky, de 15h à 18h) 
- Vendredi 15 janvier 2010 : Théorie ! des noeuds et musique  
- Vendredi 12 mars 2010 : Représentations pour l'informatique musicale (graphes et S-langages) 
- Samedi 13 mars 2010 : école mathématique pour musiciens et autres non-mathématiciens animée par Pierre Cartier (Salle Igor Stravinsky, de 15h à 18h) 
- Vendredi 9 avril 2010 : Espaces de Chu et musique
- Vendredi 14 mai 2010 : Musique algorithmique 
- Samedi 15 mai 2010 : école mathématique pour musiciens et autres non-mathématiciens animée par Pierre Cartier (Salle Igor Stravinsky, de 15h à 18h) 


Pour tout renseignement, contacts et ! propositions sur le séminaire MaMuX :

Moreno Andreatta (andreatta@ircam.fr)
Carlos Agon Amado (agonc@ircam.fr)


========

Cordialement,

Moreno Andreatta

-----
Moreno Andreatta
Equipe Représentations Musicales
IRCAM-CNRS
1, place I. Stravinsky
F-75004 Paris
Tél: +33 (0)1 44781649
Fax: +33 (0)1 44 78 15 40
-----

---------------------------- Message original ----------------------------
Objet: Vendredi 9 avril à l'IRCAM : Espaces de Chu et musique (10h-18h)
De: "Andreatta Moreno" <Moreno.Andreatta@ircam.fr>
Date: Mar 6 avril 2010 12:22
À: Pourinfos@risc.cnrs.fr
musisorbonne@cines.fr
--------------------------------------------------------------------------

Merci de bien vouloir transmettre l'information à tous ceux qui pourraient
être intéressés par cette séance du séminaire MaMuX. [Avec nos excuses
pour les envois multiples]

---


Neuvième saison du Séminaire MaMuX
Mathématiques, musique et relations avec d'autres disciplines
IRCAM, salle C. Shannon (matinée) et I. Stravinsky (après-midi)
1, place Igor-Stravinsky 75004 Paris
(Entrée libre dans la mesure des places disponibles)

Vendredi 9 avril 2010

de 10 à 18h

Espaces de Chu et musique

Cette séance exceptionnelle du Séminaire MaMuX est consacrée aux espaces
de Chu, un concept dont on essaiera de présenter les aspects théoriques
touchant à la fois à de questions de logique, de géométrie et
d'informatique et leurs applications en musique. Si d'un point
mathématique un espace de Chu n'est qu'une simple matrice de
transformations, ses lignes ayant la propriété de transformer « en avant »
[forwards] et ses colonnes celle de transformer « en arrière »
[backwards], ce concept est très profond car il joue un rôle d'unificateur
par rapport à plusieurs structures mathématiques, telles les structures de
relations (ensembles, graphes dirigés, ensembles partiellement ordonnés,
…), les structures algébriques (groupes, anneaux, modules, espaces
vectoriels, …) et les structures topologiques (espaces topologiques,
groupes abéliens localement compacts, …). La matinée se déroulera sous la
forme d'un cours introductif au cadre théorique général animé par Vaughan
Pratt, l'un des spécialistes de ce domaine. Dans l'après-midi on se
concentrera sur trois aspects de ce formalisme qui sont susceptibles
d'ouvrir des applications nouvelles en musique.


Programme de la journée

Matinée pédagogique (salle C. Shannon, niveau -2) :
10h - 12h Vaughan Pratt – A Chu Space Tutorial
Après-midi (salle I. Stravinsky) :
14h30 - 14h45 Moreno Andreatta & Carlos Agon – Introduction to the
session 14h45 – 15h30 Paul-André Melliès - Chu Spaces and the construction
of a duality 15h30 – 16h15 Timothy Porter – The Geometry of Observation
Break
17h00 - 17h45 Vaughan Pratt – Evolution of music and speech: a Chu
perspective Discussion finale
Résumés :

Vaughan Pratt (Stanford University) : A Chu space tutorial
Selected topics from Chapters 1-4 of « Chu Spaces », Notes for the School
on Category Theory and Applications University of Coimbra
[http://boole.stanford.edu/pub/coimbra.pdf]

Paul-André Melliès (CNRS/PPS-Jussieu) : Chu spaces and the construction of
a duality In this tutorial talk, I will review the elegant description of
the Chu construction discovered by Pavlovic in the 1990s. In particular, I
will explain how to see a Chu space as a canonical solution to the
question of extracting a duality from the mere existence of a point (or
pole) in a category. I will also relate the Chu construction to other
important ideas in logic, this including the Dialectica interprétation by
Godel (after ideas by Hyland and de Paiva) together with the dynamic and
game-theoretic interpretation of the logical interaction.

Timothy Porter (University of Wales, Bangor) : The Geometry of Observation
We start with a simple situation: an observer makes observations about
'something'. The observer has a list of attributes and is observing a set
of objects, and notes whether objects have particular attributes or not.
(This gives a 2-valued Chu space and is general enough for us - for the
moment.) The question is how to 'organise' the observations with respect
to spatial, logical, .... aspects of the situation. We will look at
classical constructions of Cech and Vietoris from the 1920s from this
general point of view, and then look at a more recent uses of similar
constructions in Physics and more generally in Topological Data Analysis.
We will also brief look at Formal Concept Analysis, a method from A.I. and
its relationship with these ideas.

Vaughan Pratt (Stanford University) : Evolution of music and speech: a Chu
perspective 1. Time-tone interference in pitch and rhythm.
2. Common roots of timbre and harmony.
3. Compositionality in composition: the sequential soloist, the parallel
orchestra, etc.

La séance de l'après-midi est accessible en ligne (en directe) à travers
le service "Ircam On Air". Instructions pour visionner la conférence à
l'adresse : http://video.ircam.fr/index.html
[English version at : http://video.ircam.fr/index.html.en]

Le programme complet de la séance, avec références bibliographiques, est
disponible en pdf à l'adresse :
http://recherche.ircam.fr/equipes/repmus/mamux/ProgrAvril2010.pdf

Planning du séminaire :
- Samedi 10 octobre 2009 : Géométrie de l'information et musique
- Vendredi 13 novembre 2009 : Géométrisation de la logique et de
l'informatique musicale. - Vendredi 4 décembre 2009 : Approche
fonctorielle en informatique musicale - Samedi 5 décembre 2009 : école
mathématique pour musiciens et autres non-mathématiciens animée par Pierre
Cartier (Salle Igor Stravinsky, de 15h à 18h) - Vendredi 15 janvier 2010
: Théorie des noeuds et musique
- Vendredi 12 mars 2010 : Représentations pour l'informatique musicale
(graphes et S-langages) - Samedi 13 mars 2010 : école mathématique pour
musiciens et autres non-mathématiciens animée par Pierre Cartier (Salle
Igor Stravinsky, de 15h à 18h) - Vendredi 9 avril 2010 : Espaces de Chu
et musique
- Vendredi 14 mai 2010 : Musique algorithmique
- Samedi 15 mai 2010 : école mathématique pour musiciens et autres
non-mathématiciens animée par Pierre Cartier (Salle Igor Stravinsky, de
15h à 18h)


Pour tout renseignement, contacts et propositions sur le séminaire MaMuX :

Moreno Andreatta (andreatta@ircam.fr)
Carlos Agon Amado (agonc@ircam.fr)

http://recherche.ircam.fr/equipes/repmus/mamux/

======Cordialement,

Moreno Andreatta

-----
Moreno Andreatta
Equipe Représentations Musicales
IRCAM-CNRS
1, place I. Stravinsky
F-75004 Paris
email: Moreno.Andreatta@ircam.fr
http://recherche.ircam.fr/equipes/repmus/moreno/
Tél: +33 (0)1 44781649
Fax: +33 (0)1 44 78 15 40
-----

lundi 5 avril 2010

seminaire PPS Jeudi 8/4

Chers tous,
prochaine seminaire PPS:

Jeudi 8 Avril, 11h salle 3E91

Nino Salibra (Univ. Venezia),

Problem 19

Abstract: The TLCA list of open problems is a list of twenty-two problems
that aims at collecting unresolved questions in the subject areas of the
TLCA (Typed Lambda Calculi and Applications) series of conferences.
Problem 19 in the TLCA list was posed by Fabio Alessi and Mariangiola
Dezani-Ciancaglini in 2002.

A closed lambda term M is easy if, for any other closed term N, the lambda
theory generated by M = N is consistent, while it is simple easy if, given
an arbitrary intersection type t, one can find a suitable pre-order on
types which allows to derive t for M. Simple easiness implies easiness.
The question whether easiness implies simple easiness constitutes Problem
19 in the TLCA list. We negatively answer the question providing a
nonempty co-r.e. (complement of a recursively enumerable) set of easy, but
non simple easy, lambda terms.

lundi 29 mars 2010

seminaire PPS *mardi* 30/3, 14h, salle 0C02

Chers tous,
cette semaine, le seminaire PPS est

le *mardi* 30 Mars, 14h (en salle 0C02):

David Baelde (University of Minnesota, USA)

Finite automata and regular fixed point formulas in muMALL

http://www.pps.jussieu.fr/seminaire/

Abstract:
We present muMALL, an extension of multiplicative additive linear logic
with least and greatest fixed points, and illustrate its expressiveness
through the model-checking problem of non-deterministic finite automata
inclusion.

We consider encoding automata as least fixed points in muMALL, and use its
general induction scheme to reason about them. We provide a coinductive
characterization of inclusion that yields a natural bridge to
proof-theory. This yields a completeness theorem, but can also be
generalized to the fragment of "regular formulas", obtaining new insights
about inductive theorem proving and cyclic proofs in particular.

jeudi 25 mars 2010

seminaire PPS *mardi* 30/3, 14h, salle 0C02

Chers tous,
le prochaine seminaire PPS va etre le
le *mardi* 30 Mars, 14h (en salle 0C02)

David Baelde (University of Minnesota, USA)

Finite automata and regular fixed point formulas in muMALL

http://www.pps.jussieu.fr/seminaire/

Abstract:
We present muMALL, an extension of multiplicative additive linear logic
with least and greatest fixed points, and illustrate its expressiveness
through the model-checking problem of non-deterministic finite automata
inclusion.

We consider encoding automata as least fixed points in muMALL, and use its
general induction scheme to reason about them. We provide a coinductive
characterization of inclusion that yields a natural bridge to
proof-theory. This yields a completeness theorem, but can also be
generalized to the fragment of "regular formulas", obtaining new insights
about inductive theorem proving and cyclic proofs in particular.

lundi 22 mars 2010

GdT Quantum Computing

Chers tous,

on a mis en place un GdT 'Quantum Computing',
en profitant de la presence de Benoit Valiron a pps.


Voici le calendrier des séances (a noter la salle) :

Quantum algorithms:
lundi 29/3 14.30-16.30 salle 0D01
mardi 6/4 14.30-16.30 salle *0C08*
mardi 13/4 14.30-16.30 salle 0D01

Q. programming languages and semantics:
mardi 4/5 14.30-16.30 salle 0D01
mardi 11/5 14.30-16.30 salle 0D01

A lundi,

claudia

mardi 16 mars 2010

correction salle/horaire, seminaire PPS 18/3

Bonjour.

Pour le seminaire du Jeudi 18 Mars,
la seance de l' après-midi sera en commun avec la GDT concurrence.
Remarquez la salle et l'horaire:

14h30 salle 6A92 .


Le programme du 18 Mars est donc:


11h, salle 3E91- Daniel de Carvalho (LIPN),

14h30, salle 6A92 (sous-marin) Sylvain Pradalier (Inria Rocquencourt),


Le résumé des deux exposés sont sur le site

https://www.pps.jussieu.fr/seminaire/

A jeudi!

Claudia

> Chers tous,
> pour le prochaine seminaire PPS,
> Jeudi 18 Mars, on va avoir une double seance:
>
> 11h Daniel de Carvalho (LIPN),
> La sémantique relationnelle de la logique linéaire est-elle
> injective?
>
> 14h Sylvain Pradalier (Inria Rocquencourt),
> Approximation, optimization and synthesis of stochastic processes
>
>
> Le résumé des deux exposés sont sur le site
>
> https://www.pps.jussieu.fr/seminaire/
>
> A jeudi
>
> Claudia
>
>
>
>

dimanche 14 mars 2010

seminaire PPS Jeudi 18/3 -double seance

Chers tous,
pour le prochaine seminaire PPS,
Jeudi 18 Mars, on va avoir une double seance:

11h Daniel de Carvalho (LIPN),
La sémantique relationnelle de la logique linéaire est-elle
injective?

14h Sylvain Pradalier (Inria Rocquencourt),
Approximation, optimization and synthesis of stochastic processes


Le résumé des deux exposés sont sur le site

https://www.pps.jussieu.fr/seminaire/

A jeudi

Claudia

lundi 1 mars 2010

GdT Quantum Computing, mardi 2 Mars 14.30, salle 1C18

Chers tous,

un petit rappel pour ceux qui ont envie de venir:

la premiere seance du notre GdT 'Quantum Computing' est demain,
mardi le 2 Mars, a 14.30,
salle 1C18 ( Chevaleret).


Benoit Valiron va nous introduire les outils mathematiques, et on va
decider ensemble le programme.

claudia

mardi 23 février 2010

GdT Quantum Computing, mardi apre-midi

Chers tous,

vu l'interet exprime par plusieurs de nous, on va mettre en place un GdT
'Quantum Computing',
en profitant de la presence de Benoit Valiron.

La premiere seance va etre mardi prochaine, le 2 Mars, a 14.30,
Chevaleret, salle 1C18


Benoit va nous introduire les outils mathematiques, et on va decider
ensemble le programme.

Les prochaines seances vont etre:
29 Mars
6 Avril
13 Avril

A bientot

Claudia Faggian

mardi 2 février 2010

seminaire PPS Jeudi 4/2

Chers tous,
le prochaine seminaire PPS:

Jeudi 4 Fevrier, 11h salle 3E91

Serge Grigorieff (Liafa)

Operational algorithmic completeness of Lambda Calculus

joint work with Marie Ferbus (Liafa)

We show that lambda calculus is a computation model
which can step-by-step simulate any sequential deterministic
algorithm for any computable function over integers or words
or any datatype.
More formally, given an algorithm above a family of computable
functions (taken as primitive tools, i.e., kind of oracle
functions for the algorithm),
for every constant K big enough,
each computation step of the algorithm can be simulated
by exactly K successive reductions in a natural extension
of lambda calculus with constants for functions in the
above considered family.

The proof is based on a fixed point technique in lambda
calculus and on Gurevich Sequential Thesis which allows
to identify sequential deterministic algorithms with
Abstract State Machines.

This extends to algorithms for partial computable functions
in such a way that finite computations ending with exceptions
are associated to finite reductions leading to terms with a
particular very simple feature.

dimanche 24 janvier 2010

seminaire PPS Jeudi 28/1

Chers tous,
le prochaine seminaire PPS:

Jeudi 28 Janvier, 11h salle 3E91

Jean Goubault-Larrecq (ENS Cachan),

Une introduction au pavé, à géométrie variable

Résumé: Le "pavé" est le nom familier donné au livre sur les modèles de
choix mixte (non-déterministe + probabiliste) dont une version
vieillissante se trouve sur ma page Web. Un des deux modèles que j'y
propose est celui des prévisions. Je propose de parler de ce modèle, et
d'expliquer pourquoi, sous des hypothèses raisonnables, il est isomorphe
au modèle proposé par Tix, Keimel et Plotkin en 2005 (publié à
FoSSaCS'08). Comme j'espère surtout initier une discussion, toute demande
d'explication est bienvenue, et je ne m'interdirai pas de digresser et
d'expliquer quelques questions qui me taraudent ou quelques idées qui me
sont passées par l'esprit mais ne sont pas forcément encore publiées.

lundi 18 janvier 2010

seminaire PPS Jeudi 21/1

Chers tous,
le prochaine seminaire PPS est:

Jeudi 21 Janvier, 11h salle 3E91 –

Guillaume Burel (Max-Planck-Institut, Saarbrücken)

Des démonstrations plus simples via la déduction modulo

Quand on recherche des démonstrations dans une théorie donnée, on peut
soit utiliser une axiomatisation, ce qui s'avère souvent peu efficace,
soit des procédures spécifiques à cette théorie, comme le simplex pour
l'arithmétique linéaire, ce qui n'est pas généralisable. Une troisième
approche consiste à présenter la théorie de manière à retrouver les bonnes
propriétés des systèmes de démonstration sans théorie. Ainsi, la déduction
modulo consiste à présenter une théorie sous forme de règles de
réécriture, puis d'appliquer les règles d'inférence d'un système usuel
(par exemple la déduction naturelle ou le calcul des séquents) modulo la
congruence engendrée par ce système de réécriture.

Nous présentons comment la déduction modulo permet de simplifier la
recherche de démonstration en nous concentrant sur trois critères :
premièrement, nous montrons comment transformer une théorie en système de
réécriture tout en assurant l'élimination des coupures, ce qui se fait en
complétant le système de réécriture à l'aide d'une procédure de type
Knuth-Bendix ; deuxièmement, nous montrons comment obtenir des
démonstrations plus courtes ; troisièmement, nous soulignons
l'expressivité de la déduction modulo en encodant les systèmes de type
purs fonctionnels au premier ordre modulo.

Ce dernier résultat permet d'envisager l'utilisation de la déduction
modulo comme formalisme de base d'un environnement de démonstration
combinant des démonstrations provenant de différents outils, certains
étant directement basés sur la déduction modulo. En particulier, nous
évoquerons également comment intégrer la déduction modulo dans un prouveur
du premier ordre existant.

mardi 12 janvier 2010

seminaire PPS Jeudi 14/1

Chers tous,
le prochaine seminaire PPS est:

Jeudi 14 Janvier, 11h salle 3E91 –

Dimitrios Vytiniotis (Microsoft Research),
Type system support for static program verification

https://www.pps.jussieu.fr/seminaire/sem2009/abstracts/vytiniotis