Séminaire tutoré

M2 IMD, 2020—2021

Cette page rassemble les informations et ressources relatives au séminaire tutoré du M2 IMD, organisé par Jérémie Chalopin (LIS) et Lionel Vaux Auclair (I2M).

Le programme du séminaire est organisé en deux temps:

Tous les exposés sont donnés en anglais.

Pour les présentations d’articles :

Séances

22 octobre, 14h, en visio: Enrico Porreca (LIS)
The semiring of dynamical systems
support de l’exposé
5 novembre, 14h, en visio: Luigi Santocanale (LIS)
Logic and algebra of discrete paths
support de l’exposé
article
19 novembre, 14h, en visio: Alexandra Bac (LIS)
A la croisée entre géométrie et topologie : théorie de Morse
support de l’exposé
15-16 mars, en visio: présentations des articles.

Articles choisis

Johan Couturier
Finding the longest isometric cycle in a graph de Daniel Lokshtanov.
Hamoydy Dia
On the translation of languages from left to right de D. Knuth.
Mavambu Diankatu
On the robustness of update schedules in Boolean networks de Julio Aracena, Eric Goles Ch., A. Moreira et Luis Salinas.
Nour Karnib
Views in a Graph: To Which Depth Must Equality Be Checked? de Julien M. Hendrickx.
Cédric de Lacroix de Lavalette
Metric spaces, generalized logic and closed categories de F. W. Lawvere.
Giulia Manara
Proof Nets and the Linear Substitution Calculus de B. Accattoli.
Audric Le Cun
A Combinatorial Proof of Kneser’s Conjecture de Jiri Matousek.
Mikhael Carmona
On Protection in Operating Systems de Micahel A. Harrisson, Walter L. Ruzzo et Jeffrey D. Ullman.
Said Couachi
Graph theory and probability de P. Erdös.
Thomas Usimaki
Bipartite complements of circle graphs de Louis Esperet et Matej Stehlík.

Articles proposés

Pour chaque article, on indique la personne qui l’a proposé : cette personne acceptera probablement (mais pas nécessairement) de correspondre et discuter avec vous pour éclairer votre lecture si nécessaire.

Graph theory and probability de P. Erdös.
Proposé par Lionel Nguyen Van Thé (I2M), qui écrit :

Il s'agit de l'article d'Erdös qui a lancé la méthode probabiliste en théorie des graphes (et plus généralement, en combinatoire), donc d'intérêt historique certain.

On the translation of languages from left to right de D. Knuth.
Proposé par Alexey Muranov (I2M).
Metric spaces, generalized logic and closed categories de F. W. Lawvere.
Proposé par Dimitri Ara (I2M).
Algebraic Combinatorics on Words de M. Lothaire.
Proposé par Anna Frid (I2M) qui suggère :

comme sujets indépendants quelques chapitres du livre [...]. Par exemple, le début du chapitre 2 (définitions équivalentes des mots sturmiens) ou du chapitre 8 (théorème de Fine et Wilf) font déjà deux sujets sûrs.

An Introduction to Hyperplane Arrangements de Richard P. Stanley.
(Au moins, les chapitres 1,2,3, mais possiblement aussi 4.)
Proposé par Luigi Santocanale (LIS).
On a Class of Lyndon Words Extending Christoffel Words and Related to a Multidimensional Continued Fraction Algorithm de Guy Mélançon et Christophe Reutenauer. Journal of Integer Sequences, 16:13.9.7 (2013).
Proposé par Luigi Santocanale (LIS).
A Combinatorial Proof of Kneser’s Conjecture de Jiri Matousek. Combinatorica 24(1):163–170 (2004).
Proposé par Luigi Santocanale (LIS).
On the Period of Sequences (An(p)) in Intuitionistic Propositional Calculus de Wim Ruitenburg. Journal of Symbolic Logic 49(3):892-899 (1984).
Proposé par Luigi Santocanale (LIS).
Infinite games played on finite graphs de Robert McNaughton. Annals of Pure and Applied Logic 65(2):149-184 (1993).
Proposé par Karoliina Lehtinen (LIS), qui écrit :

The memoryless determinacy of parity games underpins much of the theory of automata over infinite words as well as the theory of temporal logics such as the modal mu calculus and LTL. This is one of the simpler early proofs of this fundamental result.

On the robustness of update schedules in Boolean networks de Julio Aracena, Eric Goles Ch., A. Moreira et Luis Salinas. Biosystems 97(1): 1-8 (2009).
Proposé par Sylvain Sené (LIS), qui écrit :

Cet article traite de réseaux d'automates booléens. Il étudie la robustesse des modes de mise à jour blocs-séquentiels (définis comme des partitions ordonnées de l'ensemble d'automates) vis à vis de la dynamique d'un réseau donné, en introduisant un nouvel outil pour ce faire : les graphes de mise à jour.

Minimizing subsequential transducers: a survey de Christian Choffrut. Theoretical Computer Science 292(1): 131-143 (2003).
Proposé par Nathan Lhote (LIS), qui écrit :

Comme le nom l'indique cet article est un survey, donc il donne une bonne vision d'ensemble du sujet et il est clair et bien écrit.

Automata theory in nominal sets de Mikołaj Bojańczyk, Bartek Klin et Sławomir Lasota. Logical Methods in Computer Science 10(3) (2014).
Proposé par Nathan Lhote (LIS), qui écrit :

Cet article parle d'automates légérement infinis (c'est à dire infinis mais avec beaucoup de symmétries). Il est long mais la première partie peut-être étudiée seule.

On Protection in Operating Systems de Micahel A. Harrisson, Walter L. Ruzzo et Jeffrey D. Ullman. Communications of the ACM 19(8): 461-471 (1976).
Proposé par Clara Bertolissi (LIS), qui écrit :

Ce papier est un papier historique de 1976. Il s’agit de la définition du modèle historique de contrôle d’accès HRU basé sur une matrice d’accès. L’article s’intéresse en particulier à la question de “safety” qui dit que le système est «sûr» lorsque l'accès aux objets est impossible sans accord du propriétaire. Le théorème principal montre (par reduction au problème de décidabilité de l'arrêt d’une machine de Turing) que l’analyse de cette propriété est indécidable dans le cas général, i.e. on ne peut pas répondre à la question “Un utilisateur peut-il acquérir un droit particulier sur un objet du système ?"

Finding the longest isometric cycle in a graph de Daniel Lokshtanov. Discrete Applied Mathematics 157(12): 2670-2674 (2009)
Proposé par Jérémie Chalopin (LIS), qui écrit :

Un algorithme polynomial pour trouver un plus long cycle isométrique (c'est à dire que les distances entre les sommets du cycle sont les mêmes dans le cycle et dans le graphe). Un résultat un peu surprenant parce que de nombreuses variantes de recherches de plus longs cycles dans un graphe sont NP-difficiles.

Views in a Graph: To Which Depth Must Equality Be Checked? de Julien M. Hendrickx. IEEE Trans. Parallel Distrib. Syst. 25(7): 1907-1912 (2014)
Proposé par Jérémie Chalopin (LIS), qui écrit :

La vue d'un sommet v dans un graphe G est un arbre (infini) dont les sommets correspondent aux chemins issus de v dans G. Si deux sommets ont la même vue, ils ont la même vue de hauteur k (on ne considère que les chemins de longueur au plus k). Dans cet article, l'auteur cherche pour quelles valeurs de k, la réciproque est vraie.

A categorical theory of patches de S. Mimram et C. Di Giusto.
Proposé par Lionel Vaux Auclair (I2M), qui écrit:

une approche catégorique de la conception d’un logiciel de gestion de versions, qui a inspiré une implémentation prometteuse à la fois en termes de fonctionnalités et de performances.

Bipartite complements of circle graphs de Louis Esperet et Matej Stehlík. Discret. Math. 343(6): 111834 (2020).
Proposé par Yann Vaxès (LIS), qui écrit:

C'est très court, mais il faudra bien expliquer le contexte du problème et la preuve complète.

An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time de Feodor F. Dragan. Inf. Process. Lett. 154 (2020).
Proposé par Yann Vaxès (LIS).
Transformation Between Regular Expressions and omega-Automata de C. Löding et A. Tollkötter.
Proposé par Pierre-Alain Reynier (LIS), qui écrit:

Un article qui étudie les transformations entre automates et expressions régulières dans le contexte des mots infinis.

Learning Regular Sets from Queries and Counter-Examples de D. Angluin.
Proposé par Pierre-Alain Reynier (LIS), qui écrit:

Un algorithme majeur d’apprentissage de langages réguliers reposant sur la notion de résiduels.

Tiling the Plane with a Fixed Number of Polyominoes de Nicolas Ollinger.
Proposé par Kevin Perrot (LIS), qui écrit:

It is proven that any set of Wang tiles can be simulated by 5 polyominoes, hence the tiling problem for polyonminoes is undecidable even when restricted to tile sets of only 5 polynominoes.

Cellular Automata and Powers of p/q de J. Kari et J. Kopra.
Proposé par Pierre Guillon (I2M), qui écrit:
  • AC et théorie des nombres,
  • un AC qui fait des multiplications et du coup des orbites parcourent tous les mots finis.
Groups defined by Automata de L. Bartholdi, et P. V. Silva.
Proposé par Pierre Guillon (I2M), qui écrit:

survol sur les groupes automatiques, puis sur les groupes d'automates.

Decidability of the HD0L ultimate periodicity problem de F. Durand.
Proposé par Pierre Guillon (I2M).
Episturmian words: a survey de A. Glen et J. Justin.
Proposé par Pierre Guillon (I2M), qui écrit:

survol sur une généralisation des mots sturmiens à un alphabet infini.

On time-symmetry in cellular automata de A. Gajardo, J. Kari, A. Moreira.
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:
  • quand la dynamique est proche de la dynamique inverse…;
  • facile sauf la fin, nouveau par rapport au cours mais connecté à des notions vues, permet de faire une belle présentation.
Periodicity and Immortality in Reversible Computing de J. Kari et N. Ollinger:
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:
  • indécidabilité de la périodicité des machines de Turing, puis des AC;
  • gros résultat, beau mélange de modèles de calcul et systèmes dynamiques.
On the Undecidability of the Tiling Problem de J. Kari:
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:

une preuve de l'indécidabilité du problème du pavage (y compris dans le plan hyperbolique) en passant par l'indécidabilité de la mortalité des fonctions affines par morceaux.

Proof Nets and the Linear Substitution Calculus de B. Accattoli:
Proposé par Lionel Vaux Auclair (I2M).

Archives

Ici on trouve des exemples d’articles proposés les années précédentes.

Universal coating for programmable matter de Z. Derakhshandeh, R. Gmyr, A. W. Richa, C. Scheideler, et T. Strothmann.
Proposé par Shantanu Das (LIS), qui écrit:

Un des premiers articles sur les algorithmes pour la matière programmable en utilisant le modèle d'Amoebot (nanorobots inspirés par des amibes). Cet article concerne le problème du coating (c.-à-d. couvrir un objet donné).

Paperfolding morphisms, planefilling curves, and fractal tiles de M. Dekking.
Proposé par Pierre Arnoux (I2M).
Logics for context-free languages de Clemens Lautemann, Thomas Schwentick et Denis Thérien.
Proposé par Séverine Fratani (LIS).
Proof nets and boolean circuits de K. Terui.
Proposé par Emmanuel Beffara (I2M), qui écrit:

Une approche originale de la correspondance entre modèles de calcul et preuves formelles: les circuits booléens sont interprétés comme des démonstrations dans un système logique, on en déduit une correspondance entre la complexité des circuits et la complexité logique.

A polygon is determined by its angles de Y. Disser, M. Mihalák et P. Widmayer.
Proposé par Shantanu Das (LIS), qui écrit:

Un robot se promène sur le bord d'un polygone et il peut mesurer les angles à chaque sommet du polygone. Cette information est-elle suffisante pour reconstruire le polygone, par le robot? Un problème assez drôle et intéressant.

Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes de J. Czyzowicz, S. Dobrev, T. Fevens, H. González-Aguilar, E. Kranakis, J. Opatrny et J. Urrutia.
Proposé par Arnaud Labourel (LIS).
Simpler, faster and shorter labels for distances in graphs de S. Alstrup, C. Gavoille, E. B. Halvorsen et H. Petersen.
Proposé par Arnaud Labourel (LIS).
Disjunctive tautologies as synchronisation schemes de V. Danos et J.-L. Krivine.
Proposé par Emmanuel Beffara (I2M), qui écrit:

Une illustration exemplaire de la correspondance preuves-programmes quand elle quitte le domaine purement fonctionnel: les formules propositionnelles de la logique classique apparaissent comme des spécifications pour des structures de contrôle qui rappellent de la synchronisation entre processus.

The Structure of Multiplicatives de V. Danos et L. Regnier.
Proposé par Emmanuel Beffara (I2M), qui écrit:

Un article fondateur sur l'approche géométrique des démonstrations initiée par la logique linéaire, où la correction d'une démonstration est présentée comme une propriété combinatoire de certains graphes.

Solos in concert de C. Laneve et B. Victor.
Proposé par Emmanuel Beffara (I2M), qui écrit:

Une réflexion sur l'expressivité de différents langages abstraits pour représenter les processus parallèles et concurrents, avec un regard plus précisément sur les question d'ordonnancement et de synchronisation.

Two-variable logic on data words de M. Bojańczyk, C. David, A. Muscholl, T. Schwentick et L. Segoufin.
Proposé par Benjamin Monmège (LIS), qui écrit:

Ça parle de logique mais via le prisme des automates. Un peu long, mais on peut se concentrer sur les sections 1 à 6 (ou 7 maximum), le reste étant des extensions moins pertinentes.

New Directions in Cryptography de W. Diffie et M. Hellman.
Proposé par David Kohel (I2M), qui écrit:

Seulement 11 pages, moins de mathématiques, mais un classique historique.

Statistical equilibrium in deterministic cellular automata de S. Taati.
Proposé par Pablo Arrighi (LIS).
Thermodynamically Favorable Computation via Tile Self-assembly de Cameron Chalk, Jacob Hendricks, Matthew J. Patitz, Michael Sharp.
Proposé par Pablo Arrighi (LIS).
On Non-Computable Functions de T. Rado.
Proposé par Kevin Perrot (LIS), qui écrit:

Pour ouvrir la discussion/présentation je conseille la lecture de ce billet de blog par Scott Aaronson..

An algorithm for restricted least squares regression de Richard L. Dykstra.
Proposé par Pascal Prea (LIS).
Transformation Between Regular Expressions and omega-Automata de Christof Löding, Andreas Tollkötter.
Proposé par Pierre-Alain Reynier et Nicolas Baudru (LIS).
A Biological Solution to a Fundamental Distributed Computing Problem de Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai et Ziv Bar-Joseph.
Proposé par Emmanuel Godard (LIS).

Dernière mise à jour
le 18 avril 2021.

XHTML et CSS valides?