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 06 avril 2023 à 10h
Résumé : (Masquer les résumés)
We will prove two completeness results for Kleene algebra with a top element, with respect to languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the case when we consider an additional constant ``top'' for the full element. Indeed, the full relation satisfies more laws than the full language, and we show that those additional laws can all be derived from a single additional axiom. The proofs combine models of closed languages, reductions, a bit of graphs, and a bit of automata.
Le séminaire de l’équipe LIMD est sous la responsabilité de
Sebastien Tavenas.
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, 2017, 2018, 2019, 2020, 2021, 2022,
toutes ensemble.
Année 2023
Jeudi 06 avril 2023 à 10h
Résumé : (Masquer les résumés)
We will prove two completeness results for Kleene algebra with a top element, with respect to languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the case when we consider an additional constant ``top'' for the full element. Indeed, the full relation satisfies more laws than the full language, and we show that those additional laws can all be derived from a single additional axiom. The proofs combine models of closed languages, reductions, a bit of graphs, and a bit of automata.
Jeudi 23 février 2023 à 10h
Résumé : (Masquer les résumés)
TBA
Jeudi 09 février 2023 à 10h
Résumé : (Masquer les résumés)
Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles sont des losanges, et à chaque fois que deux tuiles sont adjacentes elle partagent soit un unique sommet en commun soit une arête entière en commun. Sur ces pavages, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas, pour une même tuile géométrique, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes. Étant donné un sous-shift X de pavages par losanges, le problème du domino sur X prend en entrée un ensemble fini de règles locales F et renvoie Vrai si il existe un pavage de X qui respecte les règles locales F et Faux dans le cas contraire. Ce problème est co-Récursivement-Énumérable-complet et nous allons présenter une réduction many-one depuis le problème du domino classique sur les tuiles de Wang.
Jeudi 19 janvier 2023 à 10h
Résumé : (Masquer les résumés)
This talk has three parts. First, I want to explain how monoid acts can be viewed as models of computation. Second, I will sketch my thesis work on categories of actions of topological monoids. Third, if there is time, I would like to explain how this work would need to be extended in order to capture the monoid acts from the first part, point out some obstacles that need to be overcome, and give some intuition on what building such a topos-theoretic context could provide. Note that while I will give complexity-theoretic motivation, I want to apply this theory to monoid and group acts of all kinds, so feel free to ask questions about your favourite ones.
Jeudi 12 janvier 2023 à 10h
Résumé : (Masquer les résumés)
The notion of hypergraph has been introduced as a generalization of graphs so that each hyperedge is a subset of the set of vertices, without constraints on its cardinality. A widely investigated problem related both to graphs and to hypergraphs concerns the characterization and reconstruction from their degree sequences. Concerning graphs, this problem has been efficiently solved in 1960 by Erdos and Gallai, while no efficient solutions are possible in the case of hypergraphs, even in the simple case of 3-uniform ones, as shown in 2018 by Deza et al. So, to reduce the NP-hard core of the hypergraph reconstruction problem, we consider a class of degree sequences defined by Deza et al. that show interesting geometrical and algebraic properties. We propose some ideas on how use those properties to challenge the related reconstruction problem.
Le séminaire de l’équipe LIMD est sous la responsabilité de
Sebastien Tavenas.
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, 2017, 2018, 2019, 2020, 2021, 2022,
toutes ensemble.