Les séminaires sont communs avec l'équipe Plume (ENS Lyon) et ont lieu en salle de séminaire, premier étage du bâtiment Le Chablais, sur le site du Bourget du Lac ou à l'ENS Lyon.

Prochain séminaire :

Jeudi 16 mars 2017 à 10h Lionel Nguyen Van Thé (Aix-Marseille Université),
TBA

Résumé : (Masquer les résumés)
TBA

Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provençal.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, toutes ensemble.

Année 2017

Jeudi 16 mars 2017 à 10h Lionel Nguyen Van Thé (Aix-Marseille Université),
TBA

Résumé : (Masquer les résumés)
TBA

Jeudi 16 février 2017 à 10h Jean-Bernard Stefani (INRIA),
TBA

Résumé : (Masquer les résumés)
TBA

Jeudi 02 février 2017 à 14h, Tarentaise 108 Anupam Das (ENS Lyon),
Monotonicity in Logic and Complexity

Résumé : (Masquer les résumés)
Monotonicity is a fundamental notion in mathematics and computation. For usual real-valued functions R → R this simply corresponds to the notion that a function is increasing (or decreasing) in its argument, however this can be parametrised by any partially ordered domain and codomain we wish. In computation we deal with programs that compute Boolean functions, {0,1}* → {0,1}*. Restricting to increasing functions over this structure can be seen as prohibiting the use of negation in a program; for instance monotone Boolean functions are computed by Boolean circuits without NOT gates. The idea of restricting negation scales to other models of computation, and for some important classes of functions the formulation is naturally robust, not depending on the particular model at hand, e.g. for the polynomial-time functions. Monotone computational problems abound in practice, e.g. sorting a string and detecting cliques in graphs, and 'nonuniform' monotone models of computation, such as monotone circuits, have been fundamental objects of study in computational complexity for decades.

In this talk I will propose a project that develops *logical* characterisations of monotone complexity classes, via a proof theoretic approach. Namely, the project will identify theories of arithmetic whose formally representable functions coincide with certain monotone classes, and also develop fundamental recursion-theoretic programming languages in which to extract the monotone functions themselves. In particular the project focusses on the role of structural proof theory, i.e. the duplication and erasure of formulae, in controlling monotonicity.

Jeudi 02 février 2017 à 10h Andrea Frosini (Florence),
Reconstruction of 2-convex polyominoes

Résumé : (Masquer les résumés)
A polyomino P is called 2-convex if for every two cells belonging to P, there exists a monotone path included in P with at most two changes of direction. We present some tomographical properties of 2-convex polyominoes from their horizontal and vertical projections and gives an algorithm that reconstructs them from a given couple of projections. We discuss its complexity.

Jeudi 26 janvier 2017 à 10h Lama Tarsissi (LAMA),
Second order balance property on Christoffel words

Résumé : (Masquer les résumés)
Balanced words have been studied a lot in the last decades. In particular, Christoffel words that are a special case of finite balanced words. In this talk, I introduce the Balance matrix that studies the balancedness of these words and I define some tools to extend this property by defining a second order of balancedness. I recall some properties about the continued fraction development and the Stern-Brocot tree to prove a recursive formula based on the shape of the path from the root of the Stern-Brocot. Finally, I show that among all infinite paths in the Stern-Brocot tree, the one that converges to φ, the golden ratio, minimizes the growth of the second order balance.

Jeudi 19 janvier 2017 à 10h Pawel Sobocinski (Southampton),
Programming recurrence relations

Résumé : (Masquer les résumés)
Recurrence relations have been of interest since ancient times. Perhaps the most famous is the Fibonacci numbers, where each additional term in the sequence is obtained as the sum of the previous two. I will show how we can use a graphical language of string diagrams–a “graphical linear algebra”–to reason about recurrence relations, and as a bonus, obtain efficient implementations. This application comes from a general string diagrammatic theory of signal flow graphs–a model of computation originally studied by Claude Shannon in the 1940s–developed in collaboration with Filippo Bonchi and Fabio Zanasi, and published at CONCUR 2014 and PoPL 2015.

Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provençal.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, toutes ensemble.