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:
-
les premières séances sont assurées par des chercheurs et chercheuses des équipes impliquées dans le master;
-
les séances suivantes sont consacrées à des présentations d’articles travaillés par les étudiantes et étudiants.
Tous les exposés sont donnés en anglais.
Pour les présentations d’articles :
-
Chaque étudiant choisit un article de recherche, en anglais, parmi les
propositions ci-dessous.
-
L’exposé donné au séminaire consiste en la présentation de l’article choisi.
Cette présentation doit être focalisée sur les aspects classiques (contexte, objectif, résultats obtenus, perspectives) et détailler un peu la partie technique de l'article.
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é
Articles choisis
-
Mikhael Carmona
-
On Protection in Operating Systems
de Micahel A. Harrisson, Walter L. Ruzzo et Jeffrey D. Ullman.
-
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.
-
Lasse Gaber
-
Transformation Between Regular Expressions and omega-Automata
de C. Löding et A. Tollkötter.
-
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.
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).