Posters et exposés jeunes chercheurs

Lundi :

15:15 - Louis-Marie Dando
15:35 - Elise Vandome
15:55 - Manon Stipulanti

16:30 - Laurent Feuilloley
16:50 - Paul-Elliot Anglès d'Auriac
17:10 - Félix Baschenis

Mercredi :

14:45 - Florian Bridoux
15:05 - Thibault Godin
15:25 - Adeline Massuir

16:00 - Tatiana Rocher
16:20 - Hamza Ben Ammar
16:40 - José Luis Vilchis Medina

Jeudi :

16:15 - Florian Faissole
16:35 - Florian Lietard
16:55 - Marion Hallet

 

 

Paul-Elliot Anglès d’Auriac

Titre : Définissabilité et Calculabilité.

Résumé : En théorie des ensembles, de nombreux efforts sont fait pour formaliser la notion de définissabilité, puis étudier les ensembles définissables et non définissables. Cette notion a des liens fort avec la calculabilité, en particulier avec des modèles de calcul plus fort que les machines de Turing. Après avoir discuté des constructibles de Godel et des machines de Turing à temps ordinal, j'exposerai le lien qui existe entre les deux.



Élise Vandomme

Titre : Arbres pleinement feuillus

Abstract : Dans les 30 dernières années, les polyominos ont été l'objet de nombreuses investigations. Un problème central, qui est pourtant toujours ouvert, est de déterminer le nombre de polyominos à n cellules carrées. Une approche possible de ce problème est d'utiliser une description combinatoire. Derrière chaque polyomino se cache un graphe dont les sommets correspondent aux cellules, tel que deux sommets sont adjacents si les cellules ont un côté en commun. Dans ce contexte, on peut étudier les polyominos dont le graphe est acyclique, appelés polyominos-arbres. En 2016, Blondin-Massé et al. ont déterminé le nombre maximal de feuilles que peut posséder un polyomino-arbre à n cellules. Dans cet exposé, nous généralisons ce problème aux graphes en général et nous montrons que le problème est NP-complet. Cependant, le problème devient polynomial lorsqu'on se restreint aux arbres et aux graphes de largeur arborescente constante.

 

Louis-Marie Dando

Titre : Expressions de Hadamard et automates circulaires

Résumé : On se place dans le cadre de l'étude des séries formelles sur un alphabet fini. Une série associe à un mot donné un poids dans un semi-anneau. On se restreint  à l'étude des séries de Hadamard, c'est à dire la clôture des séries rationnelles par les opérations de Hadamard. Ces séries peuvent être représentées par au moins deux objets : les automates circulaires et les expressions de Hadamard (de la même façon que les langages rationnels peuvent être représentés par les automates finis et les expressions rationnelles). Je présenterais ces deux objets et une façon de passer d'une représentation à une autre.

 

José Luis Vilchis Medina

Titre : Autonomous Aerial Vehicle: Based on Non-Monotonic Logic.

Résumé : The glider is one of the most relevant aircraft in terms of the ratio of the distance traveled and the loss of altitude. Making it one of the most efficient aircraft to fly. This is possible thanks to its long and thin wings, and its aerodynamic fuselage. Offering minimal opposition to air resistance. The challenge of a glider is to remain in flight as long as possible. But external perturbations tend to disturb it. Causing it to deviate from its intended flight path. The task of the pilot is to apply control commands to fly in the desired direction. Decision-making plays an important role under circumstances where the pilot has incomplete and contradictory information about the situation of flight. I present a formulation of a model from the point of view of logical theory, using non-monotonic logic, more specifically default logic, to tackle these problems. Also, results from a simulation for further application in a reduced glider model which will use solar cells for power management in embedded system.

 

Manon Stipulanti

Titre : Des triangles de Pascal généralisés aux coefficients binomiaux de mots

Résumé : Il existe un lien bien connu entre le triangle de Pascal et le triangle de Sierpinski. Il est possible de généraliser la construction du triangle de Pascal en utilisant les coefficients binomiaux de mots finis. Ces coefficients binomiaux de mots sont des généralisations classiques des coefficients binomiaux d'entiers. On a démontré qu'un objet limite, semblable au triangle de Sierpinski, existe également dans le cas où l'on généralise le triangle de Pascal aux représentations binaires des entiers.

 

Hamza Ben Ammar

Titre : Optimization of network resources for efficient distribution of media content in content-centric networks

Résumé : The last few years witnessed a rise in the popularity of content-oriented services, which are expected to increase even more with the growth of data-intensive applications. In fact, applications such as Peer-to-Peer file sharing, Video on Demand and video/audio streaming are, nowadays, massively driving content retrieval and data dissemination in the Internet. In such a context, many research initiatives proposed the Content-Centric Networking paradigm (CCN), which is emerging as one of the most interesting alternatives to the existing network architecture. The CCN paradigm consists in redesigning the future Internet architecture by focusing on named data instead of the end-to-end principle and the host-centric approach. One major feature considered in CCN to achieve service scalability and performance, is the in- network caching. Thus, each node equipped with a content store module has the ability to cache the content that pass by it. Therefore, the end-users’ requests, that are routed toward the Content Providers’ servers, can be satisfied by the cached data at the intermediate nodes. The caching and request routing protocols on which the CCN networks are currently based are lacking efficiency and there is not yet a consensus on the strategies to be used. It is in this context that the present thesis is situated. The major aim of this thesis is to study and analyze the state of the art in order to propose new efficient techniques of in-network caching and request routing and thus optimizing the network resources in Content-Centric Networks.

 

Florian Bridoux

Titre : On the cost of simulating a parallel boolean automata network by a block-sequential one.

Résumé : In this presentation, we study Boolean automata networks (BANs). A given BAN can be associated with several dynamics, depending on the schedule (i.e. the order) we choose to update its automata. In this presentation, we consider all block-sequential update schedules: we group automata into blocks, and we update all automata of a block at once, and iterate the blocks sequentially. For the last 15 years, people have studied the influence of the update schedules on the dynamics of a BAN. Here, we do the opposite. We want to determine the minimum number κ of additional automata that a BAN associated with a given block-sequential update schedule needs to simulate a given BAN with a parallel update schedule. To solve this problem, we introduce a graph that we call confusion graph built from the BAN and the update schedule. We show the relation between κ and the chromatic number of the confusion graph. Thanks to this confusion graph, we bound κ in the worst case between n/2 and 2n/3 + 2 (n being the size of the BAN simulated) and we conjecture that this number equals n/2. We support this conjecture with two results: the clique number of a confusion graph is always less than or equal to n/2 and, for the subclass of bijective BANs, κ is always less than or equal to n/2.



Tatiana Rocher

Titre : Indexation de séquences annotées, Indexing labeled sequences

Résumé : Labelling sequences is a way to add information on sequences or parts of sequences. Labels can be used in many fields, as in bioinformatics to add functional annotations on genes or on regulation sites. For example, we can have a DNA sequence ACGTAA...GTTAT of length 50 with the label L1 from the letters 12 to 31. In such situtations, one would like to index both the text and the labels and to make some queries such as : Which are the sequences that have the label L1 ? Which ones have the pattern AAA and the label L2 ? We introduce here a new index structure which stores labeled sequences and which efficiently answers to sequence-label association queries. Our structure share some ideads with the RL-FMI [3]. It uses a Burrows-Wheeler Transform [1] (BWT) which stores the sequences, a Wavelet Tree [2] which indexes the labels and a bit vector which binds them. This structure, storing a text T of length n, can be made in a O(nHk(T) + nH0(B) + mH0(M)) + o(n) complexity, where B is the bit vector, M is a compacted list of labels generated in the BWT order, and m its length.

The proposed structure was implemented and tested to index 100MB random files with random or fixed labels, and real data. Indexing completely random files does not give any compression. On the contrary, random files with fixed labels a compression of 0% to 90% in 10s to 2000s. Experimental results on 233MB of real data coming from immune DNA recombined sequences labeled with V/D/J gene segments show a compression of 60% in 143s.



Laurent Feuilloley

Titre : Hierarchy of Local Decision

Résumé : An analogue of the theory of complexity has recently been developed for distributed computing on networks. This work describes the analogue of the polynomial hierarchy. In the talk, I will define all these terms, and try to give intuitions on these classes and the computational problems inside.

 

Florian Faissole

Titre : Une preuve formelle du théorème de Lax-Milgram.
Résumé : La méthode des éléments finis est fréquemment utilisée pour résoudre numériquement des équations aux dérivées partielles. Pour assurer un niveau de confiance suffisant dans les programmes qui implémentent, il faut formaliser la substance mathématique permettant d'établir la correction de la méthode. Le théorème de
Lax-Milgram nous paraît être un point de départ incontournable : sous certaines hypothèses de complétude et de coercivité, il garantit l'existence et l'unicité de la solution de certains problèmes mathématiques. Nous présentons une preuve formelle complète du théorème de Lax-Milgram dans l'assistant de preuves Coq, qui repose sur une théorie des types d'ordre supérieur avec types dépendants. Ce travail requiert de nombreux résultats d'algèbre linéaire, géométrie, analyse fonctionnelle et théorie des espaces de Hilbert.

 

Adeline Massuir

Titre : Extension d’un théorème de Cobham pour l’anneau des polynômes à coefficients dans un champ fini

Résumé : Dans cet exposé, nous présenterons notre projet de recherche. En 1969, Alan Cobham démontra le théorème suivant : Théorème 1. Soient p et q deux entiers naturels multiplicativement indépendants et stricte- ment supérieurs à 1. Si N est une partie p-reconnaissable et q-reconnaissable de N, alors N est une union finie de progressions arithmétiques. Notre présentation consistera dans un premier temps en des explications de ce théorème via des définitions et des exemples. Dans la poursuite de la thèse de L. Waxweiler, nous souhaitons démontrer un théorème similaire à celui de Cobham dans le cadre des polynômes à coefficients dans un champ fini. C’est pourquoi nous expliquerons ensuite comment transférer les concepts utilisés pour les naturels vers les polynômes. Enfin, nous présenterons les pistes envisageables pour démontrer un tel théorème, avant de nous focaliser sur l’approche logique, méthode que nous avons choisi d’aborder en premier lieu.

 

Félix Baschenis

Titre : Transducteurs bidirectionnels

Résumé : Certains théorèmes classiques de la théorie des automates ne sont pas valables pour les transducteurs, l'ajout d'un output sur la fonction de transition apportant une problématique d'ordre dans les étapes du calcul. L'année dernière, nous avons présenté ici-même un résultat de calculabilité sur les transducteurs "sweeping". Nous présentons ici le modèle plus général des transducteurs bidirectionnels, et nous balaierons des questions  classiques de déterminisation, de transformation en transducteurs unidirectionnels,  et d'équivalence avec d'autres modèles de calcul des transductions.

 

Thibault Godin

Titre : Machines de Mealy et groupes d'automate

Résumé : Dans cet exposé, je voudrais présenter les machines de Mealy, un genre particulier d'automates, et expliquer comment elles peuvent être utilisées pour engendrer des groupes. Je donnerai ensuite des exemples de problèmes où ces groupes engendrés par des automates de Mealy ont été utiles, ainsi que des problèmes auxquels je m’intéresse dans le cadre de ma thèse et du projet Mealy.

 

Florian Lietard

Titre : Evitabilité des k-puissances additives en combinatoire des mots

Résumé : L'étude de la possibilité d'éviter ou non certaines structures de mots s'est essentiellement développée après le travail de Thue en 1912. Il a montré, entre autres choses, qu'il était possible de construire un mot infiniment long, sur un alphabet ternaire (composé de trois lettres), qui évite les carrés (les mots du type ww où w est un mot). Il travaillait essentiellement avec des morphismes de mots et leurs points fixes. Après un rappel rapide de ces notions, l'exposé s'orientera vers les puissances additives et notamment sur les perspectives offertes par les travaux de J. Cassaigne, J.D. Currie, L. Schaeffer et J. Shallit dans ce domaine.

 

Marion Hallet

Titre : Dynamiques sur le jeux sois formé extensive

Résumé : Les jeux sous forme extensive, joués sur des arbres, sont des jeux où les joueurs jouent à tour de rôle. Nous nous intéresserons uniquement aux jeux finis à information parfaite. Différents concepts d'équilibres sont étudiés dans ces jeux, principalement les équilibres de Nash et les équilibres parfaits en sous jeu. Notre but est d'étudier différentes dynamiques d'amélioration des joueurs qui, à partir d'un profil de stratégie arbitraire, conduit vers un équilibre.

 

Posters

 

Lucas Morlet

Intégration des surfaces de subdivision dans la CAO



Félix Baschenis

Expressivité et minimisation des transducteurs bidirectionnels



Yoann Dufresne

Algorithmique pour les peptides non ribosomiques

 

Laurent Feuilloley

A Hierarchy of Local Decision

 

Agnieszka Słowik

Random projections in Extreme Learning Machines

Personnes connectées : 1