Agenda - archives

Seminaire : Séminaire pôle Signal & Image - Emmanuelle SALIN

16/12/2022 à 10h00

Titre :Vision-Language Transformer Models.
Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Vision-Language models combine information from the textual and visual modalities to extract multimodal representations. These models can be used as basis for a large range of multimodal vision-language tasks. The use of large pre-trained models based on the transformer architecture, inspired by recent advances in Natural Language Processing, have enabled great improvement on those tasks. However, their ability to understand complex multimodal concepts remains limited.
In this presentation, I will give an overview of vision-language transformer models: the different models and pre-training methods, how to evaluate them, their strengths and weaknesses and current trends of research.

Seminaire : Séminaire CANA : Jean-Marc Ginoux

13/12/2022 à 14h00

Orateur : Jean-Marc Ginoux (Institut Jules Verne, Université de Toulon)
Lieu : TPR2/04.05 (Luminy)
Titre : Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem
Abstract : Slow–fast dynamical systems, i.e. singularly or nonsingularly perturbed dynamical systems possess slow invariant manifolds on which trajectories evolve slowly. Since the last century various methods have been developed for approximating their equations. This talk aims, on the one hand, to propose a classification of the most important of them into two great categories: singular perturbation-based methods and curvature-based methods, and on the other hand, to prove the equivalence between any methods belonging to the same category and between the two categories. Then, a deep analysis and comparison between each of these methods enable to state the efficiency of the Flow Curvature Method which is exemplified with paradigmatic Van der Pol singularly perturbed dynamical system and Lorenz slow–fast dynamical system.

In his famous book entitled Theory of Oscillations, Nicolas Minorsky wrote: “each time the system absorbs energy the curvature of its trajectory decreases and vice versa”. By using the Flow Curvature Method, we establish that, in the ε-vicinity of the slow invariant manifold of generalized Liénard systems, the curvature of trajectory curve increases while the energy of such systems decreases. Hence, we prove Minorsky’s statement for the generalized Liénard systems. These results are then illustrated with the classical Van der Pol and generalized Liénard singularly perturbed systems.

References

Ginoux J.-M., 2021, “Slow Invariant Manifolds of Slow-Fast Dynamical Systems,” International Journal of Bifurcation and Chaos, Vol. 31(7) 2150112 (17 pages), 2021.

Ginoux J.-M., Lebiedz D., Meucci R. & Llibre J., 2022, “Flow curvature manifold and energy of generalized Liénard systems,” Chaos Solitons & Fractals, 161, 112354 (7 pages), 2022.

Seminaire : Séminaire G-MOD - Contribution à la génération stochastique d'apparences procédurales

02/12/2022 à 10h00

Invité : Guillaume Gilet (Université de Sherbrooke)

Salle : 5.37
Zoom : https://univ-amu-fr.zoom.us/j/84432888361?pwd=NmNFSFRLRnZic2svK3d1SUZlQ1dTZz09

Titre : Contribution à la génération stochastique d'apparences procédurales

Résumé :
Alors qu’existe une demande croissante pour des mondes virtuels visuellement riches et d’une taille tendant vers l’infini, la majeure partie du secteur industriel (notamment vidéo-ludique) repose essentiellement sur la création manuelle, par des infographistes, d’objets tridimensionnels à l’apparence complexe et détaillée. Cela impose de fait une limite sur la taille, la complexité et la richesse visuelle des mondes virtuels qu’il est possible d’observer, car chaque élément d’une scène a été conçu et placé « manuellement », ce qui engendre de nombreux problèmes, tels que le coût (financier et en main d’œuvre), le stockage et transfert de ces informations de grande taille, l’augmentation de la puissance de calcul requise pour manipuler ces scènes…Une alternative naturelle consiste alors à générer des objets virtuels et leurs apparences de manière procédurale, c’est-à-dire de manière automatique à l'aide de définitions et règles reposant sur des outils mathématiques et physiques. Nous nous focaliserons dans cet exposé sur la génération procédurale de l’apparence des objets virtuels, dont la difficulté majeure reste le choix des modèles et paramètres à utiliser : Quels modèles possèdent les « bonnes » propriétés ? Quels sont les paramètres et modèles suffisamment intuitifs pour offrir à la fois un contrôle facile sur le résultat final et une grande qualité visuelle ? Les surfaces visuellement riches exhibent une apparence complexe et variée, résultant, dans le monde réel, d’un ensemble de phénomènes physiques, chimiques, biologiques et d’interactions humaines. Alors que la modélisation et la simulation directe de ces phénomènes ne sont pas envisageables (dans le cadre temps-réel), l'utilisation de l'aléatoire dans les définitions procédurales permet d'accroître la variété des apparences générées. Toutefois, le contrôle de cet aléatoire est un problème difficile : où introduire l’aléatoire ? Qu’est ce qui doit être aléatoire ? Comment s’assurer de la qualité du résultat ? Nous présenterons dans cet exposé un ensemble de travaux et réflexions sur la pertinence de ce modèle aléatoire et tenterons d'apporter des éléments de réponses à la génération procédurale d'apparences complexes en temps réel.
Venez nombreux !

Seminaire : Séminaire I&M (Signal-Image) - Jules Collenne

25/11/2022 à 14h00

Titre :Aide au diagnostic du mélanome: approche par apprentissage de similarités.
Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Le mélanome est un cancer cutané de plus en plus fréquent dans les pays développés qui se distingue par sacapacité à métastaser très rapidement. Pour réduire la mortalité, une étape majeure est son diagnostic.Traditionnellement réalisé par les dermatologues, l’automatisation de cette étape pourrait permettre une meilleureprise en charge des patients, ainsi qu’un plus grand nombre de personnes analysées, notamment dans les zonesoù les dermatologues manquent. L’objectif de la thèse est donc d’imaginer et de réaliser de nouvelles manières dediagnostiquer le mélanome à l’aide de l’intelligence artificielle.
Alors que de nombreux travaux existent déjà dans le domaine du diagnostic du mélanome (comme l’usage deréseaux de neurones convolutifs simples), notre approche se concentre sur le concept du «vilain petit canard»[1],qui pourrait permettre un meilleur diagnostic. Contrairement aux approches précédentes se basant uniquementsur l’aspect visuel des lésions étudiées une à une, ce concept vise à comparer les lésions d’un même patient entreelles, de sorte à ce que les lésions différentes des autres aient une plus grande probabilité d’être des cancers de lapeau. Une telle information pourrait permettre un meilleur diagnostic ainsi qu’une meilleure compréhension, pourles dermatologues, des résultats donnés par les modèles de prédiction.
Plusieurs types de réseaux de neurones sont étudiés, notamment les réseaux de neurones siamois[2-4], ainsi que plusieurs algorithmes de détection d’anomalies et de clustering. Des expériences ont été menées afin d’analyser les performances de chaque modèle utilisé pour le diagnostic du mélanome.
Bibliographie :
[1] Grob JJ, Bonerandi JJ. The 'ugly duckling' sign: identification of the common characteristics of nevi in an individual as a basis for melanoma screening. Arch Dermatol. 1998 Jan;134(1):103-4. doi: 10.1001/archderm.134.1.103-a. PMID: 9449921.
[2] Xinlei Chen and Kaiming He. Exploring Simple Siamese Representation Learning. 2020.
[3] Xiao Wang et al. On the Importance of Asymmetry for Siamese Representation Learning.
[4] Kaiming He et al. Momentum Contrast for Unsupervised Visual Representation Learning. 2019.

Conference : International Conference on Systems and Control - ICSC'22

23/11/2022 à 00h00

L'«International Conference on Systems and Control» a lieu annuellement dans différents pays méditerranéens : Maroc (2012), Algérie (2013), Tunisie (2014), France (2021), etc. En 2022, le laboratoire LIS a pris en charge l’organisation de sa dixième édition qui se déroulera du 23 au 25 novembre. ICSC’22 réunira plus de 150 chercheurs. Elle représente un événement important pour l’échange et pour la communication des travaux scientifiques dans le domaine des sciences industrielles de l’ingénieur, et plus précisément de « l’automatique », connu dans le monde industriel comme le «contrôle/commande des systèmes».

Conference : Séminaire CANA : Victor Lutfalla

22/11/2022 à 14h00

Orateur: Victor Lutfalla (GREYC, Caen)
Lieu : TPR2/04.05 (Luminy)
Titre : Le problème du domino sur les sous-shifts de pavages par losanges
Abstract : 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 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 indécidable et nous allons présenter une réduction du problème du domino sur un sous-shift de pavages par losanges depuis le problème du domino classique sur les tuiles de Wang.

Seminaire : Séminaire CANA : Étienne Miquey

15/11/2022 à 14h00

Orateur : Étienne Miquey (I2M)
Lieu : TPR2/04.05 (Luminy)
Titre : Curry-Howard: unveiling the computational content of proofs
Abstract : This talk is meant to be an introduction talk on the Curry-Howard correspondence between proofs and programs, for people that may not be dreaming about the λ-calculus every night. I will try to give an historical overview on why and how this correspondence was established, travelling back in time to see how the notion of "proof" evolved since the greeks (our historical lower bound in this talk) until becoming a major concept not only for mathematics but also for the development of programming languages (among other things). In between, I may talk about intuitionistic logic, proof assistants, realizability (my favorite topic), model theory, etc. This list is non-exhaustive, and in particular I would be glad to extend it with any related subsequent topic that may interest you (if so, you should send me an email: "Salut, je me suis toujours demandé ce que c'était qu'une théorie des types, tu pourrais en parler ?", and I may try to include a slide or two, with a probability highly related to the date of your mail).

Conference : Journée d'Ouverture Scientifique (JOS), 1ère édition - Informatique

15/11/2022 à 08h30

Les LIS est partenaire de la 1ère Journée d'Ouverture Scientifique consacrée à l'Informatique mardi 15 novembre 2022 sur le site Saint Charles. Destinée aux étudiants en informatique de diverses formations, elle a pour objectifs d’élargir les horizons scientifiques et professionnels, d’alimenter la réflexion sur leur devenir et de favoriser les échanges entre licences/masters/entreprises/chercheurs. Au programme: de la blockchain à la question des femmes en informatique en passant par les différents métiers, profitez des conférences, rencontres et tables rondes destinés aux étudiants, en présence d'entreprises, de jeunes chercheurs doctorants et de chercheurs plus expérimentés.
Programme et inscriptions: https://jos-2022.lis-lab.fr/ .
Cette journée est soutenue par le LIS, l'Institut Archimède/Tiger, l'ED maths-info, le réseau Les Entreprises Pour la Cité, la Licence MPCI et plusieurs formations en informatique (licence et master).

Conference : BDA'2022 - 38èmes journées de la conférence BDA « Gestion de Données – Principes, Technologies et Applications »

24/10/2022 à 00h00

La conférence BDA est un événement annuel incontournable de la communauté gestion de données en France, qui met en exergue les nombreux thèmes de recherche liés à la gestion de données tels que les Entrepôts de données, le Big-Data, la gestion de flux, la qualité, la sécurité, la fouille de données, ou encore le Web sémantique. Site web de la conférence : https://bda2022.sciencesconf.org/

Seminaire : Séminaire de Théorie du Contrôle

20/10/2022 à 14h30

Eugenio Pozzoli (IMB) Contrôlabilité des systèmes quantiques en dimension infinie https://pole-acs.lis-lab.fr/

Seminaire : Séminaire CANA - Ravi Kunjwal

18/10/2022 à 14h00

Orateur : Ravi Kunjwal (Centre for Quantum Information and Communication, Université libre de Bruxelles)
Lieu : TPR2/04.05 (Luminy)
Titre : Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem
Abstract : The Kochen-Specker (KS) theorem is often taken as a notion of nonclassicality that is independent of entanglement since it is provable on a three-dimensional Hilbert space. However, the smallest system on which both the KS theorem and entanglement are meaningful notions of nonclassicality is a two-qubit system. I will present some recent work on the necessity of entanglement in proofs of the KS theorem on multiqubit systems. We show two key results: firstly, that any proof of the KS theorem that uses KS sets necessarily requires entangled measurements, and secondly, that a statistical proof of the KS theorem with unentangled measurements on a multiqubit state exists if and only if this state can witness a Bell inequality violation. We also obtain an overall understanding of the relationship between unentangled Gleason and KS theorems on multiqudit systems in general. Time permitting, I will also discuss some implications of these results for the role of contextuality as a resource for multiqubit quantum computation with state injection. Based on arXiv:2109.13594.

Conference : Séminaire CANA - Aymeric Picard Marchetto

04/10/2022 à 14h00

Orateur : Aymeric Picard Marchetto (PhD I3S)
Lieu : TPR2/04.05 (Luminy) et en visio
Titre : Given an automata network, many results show that some dynamical properties can be deduced from its interaction digraph. These dynamical properties are often invariant by isomorphism: number of fixed points, of images, length of limit cycles and transients... But the interaction digraph is not invariant by isomorphism: tow isomorphic automata networks (with the same alphabet and the same number of automata) can have very different interaction digraphs.
In this talk, we study this phenomena. For that, given an automata network f with n automata, we denote by G[f] the set of interaction digraphs of automata networks isomorphic to f. Hence G[f] is a set of digraphs with n vertices.
In particular, we show that if n>4, and f is neither the identity or constant, then G[f] contains the complete digraph. We also prove that G[f] always contains a digraph with minimum in-degree at most some constant that only depend on the alphabet size. Consequently, G[f] cannot only contain the complete digraph, but we show that there is f such that G[f] only contain digraphs with at least n^2/4 arcs. Finally, we prove that there is f such that G[f] contains all the digraphs with n vertices, excepted the empty one.

Seminaire : Séminaire DYNI - Dan Stowell - Deep embedding methods for high-resolution animal sound recognition

29/09/2022 à 14h30

Automatic detection and classification of sound events is a promising tool for monitoring wildlife. However - since there are hundreds of species and sounds, and complex noisy soundscapes, machine learning needs to be raised to a very high level of fine-grained precision and robustness. I will report on deep embeddings trained with loss functions designed to reflect fine-grained aspects of animal sound discrimination: hierarchical individual recognition, few-shot learning and perceptual discrimination. Biography: Dan Stowell is Associate Professor of AI & Biodiversity, jointly appointed at Tilburg University and Naturalis Biodiversity Center (NL). Since 2012 he has led research on computational bioacoustics using machine learning and signal processing. He is a co-founder of the data challenge "detection and classification of sound scenes and events (DCASE)", now an annual IEEE workshop and challenge. He is cofounder and CTO of Warblr Ltd (UK), a phone app that automatically recognises bird sounds - the app has received awards and copious press coverage, and has tens of thousands of regular users around the UK. In the Netherlands he is involved in many funded projects to bring AI-powered biodiversity monitoring to fruition. Lieu: X133, UTLN, campus de La Garde

Seminaire : Séminaire ACRO

12/09/2022 à 10h00

Séminaire de Jean-Christophe Godin, en salle 4.05 du TPR2 à Luminy. Titre : On List Coloring with Separation of the Complete Graph and Set-System intersections Résumé : We consider the following list coloring with separation problem: Given a graph G and integers a, b, find the largest integer c such that for any list assignment L of G with |L(v)| = a for any vertex v and |L(u) ∩ L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u) ⊂ L(u) and |φ(v)| = b for any vertex u and φ(u) ∩ φ(v) = ∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincaré’s crible, we determine the separation number of the complete graph Kn for some values of a, b and n, and prove bounds for the remaining values. Travail en commun avec Rémi Grisot et Olivier Togni

Seminaire : Séminaire CANA : Kévin Perrot

19/07/2022 à 14h00

Orateur : Kévin Perrot (LIS)
Lieu : TPR2/04.05 (Luminy)
Titre : Trois exemples magiques d’algorithmes randomisés
Abstract : 1) Compter jusqu'à 10^309 sur ses 10 doigts. 2) Obtenir un multiplicateur robuste à partir d'un multiplicateur foireux.
3) Preuves à divulgation nulle de connaissance (zéro-knowledge proofs).
Ces exemples sont tirés de l'article “Randomness + determinism = progresses: Why random processes could be favored by evolution” par Nicolas Schabanel en 2012.

Seminaire : Matinée des Jeunes Scientifiques du LIS

12/07/2022 à 09h30

Une matinée de science dédiée à nos étudiant·e·s de L1 qui participent à la vie du LIS dans le cadre d’un stage « Incubateur de jeunes scientifiques » promu par la Faculté des Sciences AMU.

Cette matinée aura lieu le 12 juillet 2022 à partir de 9h30 dans la salle 04.05 du bâtiment TPR2 sur le site du Luminy et il sera également possible d’y participer par Zoom.

Voici le programme de la matinée :

9h30 Tamazouzt Ait-Eldjoudi et Antonio Mattar : Des alligators au lambda-calcul (encadré·e·s par Benjamin Monmege)
10h10 Redouane Benkhemou : Deep Learning VS. Modélisation et Simulation DEVS : application aux portes logiques (encadré par Amine Hamri)
10h40 Mathieu Cambon, Marc-Antoine Poquet et Rayan Saadessaoud : Questions autour de la philosophie de l'informatique, de l'intelligence artificielle et des sciences cognitives (encadrés par Thomas Schatz)
11h30 Ekaterina Timofeeva : Développement de logiciel pour l’étude de la décomposition de systèmes dynamiques (encadrée par Antonio E. Porreca)
12h00 Alexander Zinoni : Vulnérabilité d'une implémentation de ECDSA dans Java (encadré par Jean-Marc Talbot)

Seminaire : Séminaire CANA : Nathanaël Eon

28/06/2022 à 14h00

Orateur : Nathanaël Eon (PhD CANA, LIS)
Lieu : TPR2/04.05 (Luminy)
Titre : From global (color-blind) symmetry to local (gauge) invariance in cellular automata
Abstract : In this talk, I will first introduce the concept of global (a.k.a. color-blind) and local (a.k.a. gauge) symmetries in cellular automata. The essence of those symmetries is for the cellular automata to be invariant under a change of the configuration, either done globally (applying the same transformation at every position) or locally (applying a different transformation at every position). Hence, a local symmetry is a priori stronger than a global one. In order to enforce the local symmetry, an extension of CA is introduced and an interesting equivalency result follows: globally symmetric CA are exactly those which can be extended into locally invariant ones (through a specific extension). Such result makes formal a folklore perspective in Physics which says that any local symmetry necessarily arise from an already existing global one. I will then provide two constructive proofs of universality for locally invariant cellular automata.
The results provided in this talk can be found on arXiv:2102.06912.

Seminaire : Séminaire CANA : Éric Rémila

21/06/2022 à 14h00

Orateur : Éric Rémila (GATE LSE)
Lieu : TPR2-04.05
Titre : Influence: a partizan scoring game on graphs
Abstract : We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor’s universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

Seminaire : Demi-journée pôle calcul - Intelligence Artificielle

16/06/2022 à 09h30

Orateurs :
- Joao Marques-Silva "Logic-Based Explainability in Machine Learning”
- Stéphane Grandcolas (LIS) "WRM: a metaheuristic algorithm for ship weather routing"
- Matthieu Py (LIS) "Production de certificats pour le problème Max-SAT"
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr

Seminaire : Séminaire CANA : Kevissen Sellapillay

31/05/2022 à 14h00

Orateur : Kevissen Sellapillay (LIS & CPT)
Salle : TPR2-04.05
Titre : Interaction graphs of isomorphic automata networks
Abstract : Entanglement is a quantum property with no classical counterpart. We briefly review entanglement, its definition and quantities to measure it. We then present a perturbation of a quantum cellular automaton based on rule 201 and study its entanglement propagation properties. This quantum cellular automaton breaks the Hilbert space into different ergodic sectors.

Seminaire : Séminaire du Pôle SD : Interprétabilité /Explicabilité des modèles d'apprentissage

09/05/2022 à 10h30

Le prochain séminaire du pôle se déroulera donc lundi prochain le 9 mai de 10h30 à 12h00 à St Charles (Frumam) et dont le thème est "Interprétabilité /Explicabilité des modèles d'apprentissage". Nous aurons le plaisir d'écouter trois présentations : Hanwei Zhang : Présentation générale des méthodes d'interprétabilité Felipe Torres : Méthodes dédiées à l'interprétabilité des images Hamed Benazha : Méthodes dédiées l'interprétabilité des séquences

Seminaire : Demi-journée pôle calcul - Complexité et Modèles de calculs

05/05/2022 à 10h00

Orateurs :
- Édouard Bonnet "Graph decompositions and their algorithms”
- Karoliina Lehtinen (LIS) "Un peu de non-déterminisme peut aller loin: un aperçu des automates déterministes en histoire"
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr

Conference : Conférence par Hervé Glotin, suivie par l'écoute de deux oeuvres sonores composés par Maxence et Léonore Mercier

14/04/2022 à 16h00

Impossible de parler Acoustique à Marseille sans évoquer l'acoustique en milieu marin, qu'elle concerne la propagation des sons à travers les mers et les océans, les chants produits par une faune marine d'une extrême diversité ou encore - préoccupation beaucoup plus récente - de l'impact de l'activité maritime humaine sur cet écosystème si fragile. https://cfa2022.sciencesconf.org/resource/page/id/25 Cinéma Les Variétés 37 Rue Vincent Scotto 13001 Marseille

Seminaire : Séminaire MoVe avec K.S. Thejaswini

07/04/2022 à 10h30

Où ? 4.05 TPR2 Luminy Quoi ? A Symmetric Attractor-Decomposition Lifting Framework for Solving Parity games. Mais encore? In this talk, we will introduce the framework of Symmetric Attractor-Decomposition Lifting. We show how this helps us understand as well as obtain a quadratic improvement to the runtime of several pre-existing algorithm. This is joint work with Marcin Jurdzinski, Remi Morvan and Pierre Ohlmann.

Seminaire : Séminaire CANA : Sara Riva

05/04/2022 à 14h00

Orateur : Sara Riva (Université Côte D'Azur et I3S Sophia Antipolis)
Salle : TPR2-04.05
Titre : A Pipeline for Solving Equations over Discrete Dynamical Systems
Abstract : Finite Discrete Dynamical Systems (DDS) are a formal model to study complex phenomena appearing in many different domains. Hypotheses on the fine structure of the system can be modeled via polynomial equations over DDS. For example, AX=B represents the hypothesis that the dynamics of B is given by the joint action of a known system A and an unknown one X. Finding X would validate the hypothesis; the hypothesis is invalid if no solution exists. In general, solving generic equations over DDS has been proved undecidable. In the hypothesis validation case, a possible approach is to study the solutions through a finite number of different abstractions of the problem. Each abstraction allows studying specific properties and parts of specific dynamics. We focus on hypotheses about the cardinality of the set of states, the cyclic behaviour and the transient behaviour of DDS. We introduce a complete pipeline based on Multi-valued decision diagrams to validate hypotheses on the cardinality of the set of states and on the asymptotic behaviour, contained in the cyclic parts, of a DDS. These results are a step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology. Furthermore, this approach opens up new research challenges in the field of ordered decision diagrams and their operations.

Seminaire : Séminaire DANA - Amélioration de l'apprentissage explicable/interprétable fondé sur FCA

29/03/2022 à 16h10

Orateur : Nida Meddouri
Lien Zoom : https://univ-amu-fr.zoom.us/j/83522684614?pwd=d1FBZmhBZnZ0M1BpUnRlRWJ5ZU5CQT09
Titre : Amélioration de l'apprentissage explicable/interprétable fondé sur FCA
Résumé : Formal Concept Analysis (FCA) est une formalisation de la notion philosophique de concept définie comme étant un couple d’extension et de compréhension du concept. Un des principaux atouts de FCA réside dans ses propriétés de visualisation. En effet, FCA produit des treillis de concepts formels qui peuvent être représentés par un graphe ; et facilitent ainsi la tâche du classifieur dans la découverte de connaissances. La classification par ACF est une approche de fouille de données explicable/interprétable qui permet d’extraire des corrélations, des motifs et des règles, selon les concepts générés à partir des données symboliques. Mes recherches m’ont permis d’améliorer les performances d’un classifieur fondé sur FCA en proposant des méthodes d’apprentissage séquentiel. Ces méthodes sont à la fois itératives et adaptatives. Elles ont pour but de combiner des classifieurs de concepts formels afin d’améliorer la précision et l’efficacité. Leurs performances théoriques sont garanties et approuvées. Une autre contribution permet de booster adaptativement des classifieurs (quel que soit l’algorithme d’apprentissage) en tenant compte de leurs diversités. Cette méta-méthode a la particularité d’éviter le sur-apprentissage. Une autre méthode proposée permet de générer parallèlement un ensemble de classifieurs de concepts formels à partir d’un certain nombre de groupements disjoints et stratifiés de données. Vu son aspect parallèle et sa capacité à s’adapter pour traiter des grandes quantités de données, je me suis intéressé à la mise en cloud de cette méthode. Une nouvelle mesure de pertinence d’attribut a été proposée. Elle s’adapte au mieux avec un classifieur fondé sur FCA.

Seminaire : Séminaire DANA - ATLAS data, physicists' treat to treat

29/03/2022 à 14h00

Orateur : Thomas Calvet
Lien Zoom : https://univ-amu-fr.zoom.us/j/84940669492?pwd=MklWK1pQbHozUjRZUDU1MVhmc2dVdz09
Titre : ATLAS data, physicists' treat to treat
Résumé : Le LHC au CERN est le plus grand générateur mondial de données pour caractériser la matière dans son état connu le plus fondamental. Les collisions proton-proton produites par le LHC sont observées par quatre détecteurs géants. ATLAS est un de ces détecteurs. De la taille d'un petit immeuble (40m de long sur 20m de haut), ce détecteur offre une excellente résolution spatiale (de l'ordre de la centaine de micromètre) et temporelle (collisions toutes les 25ns) sur les produits des collisions. Pour ce faire, il génère des quantités massives de données dont l'exploitation est le cœur d'œuvre des physiciens du CERN. Deux temps se distinguent. Sur les premières microsecondes, des algorithmes automatisés doivent être capable de reconstruire les propriétés physique de bases à partir des données brutes pour décider de la sauvegarde ou du rejet des données de chaque événement. Les données sauvegardées sont ensuite étudiées avec minutie pour des mesures de hautes précisions qui sont confrontés aux modèles théoriques. Cette présentation sert un objectif double : mettre en perspective les défis de gestion des données d'ATLAS à ses différents niveaux et les illustrer par mes travaux notamment dans le domaine des IA.

Seminaire : Séminaire DANA - Extraction de motifs dans des données spatio-temporelles : application au suivi environnemental

29/03/2022 à 09h30

Orateur : Frédéric Flouvat (MCF, HDR, Université de la Nouvelle-Calédonie)
Lien Zoom : https://univ-amu-fr.zoom.us/j/86329875449?pwd=VU95K2R4bVdFMWc4NEpwK295MEhkZz09
Titre : Extraction de motifs dans des données spatio-temporelles : application au suivi environnemental
Résumé : Ces dix dernières années, la quantité de données collectées a explosé. Au-delà des volumes de données engendrés, leur complexité a aussi considérablement augmenté. Même si les avancées ont été nombreuses, les verrous restent encore nombreux avant de réellement pouvoir valoriser toutes ces informations. L'augmentation de la puissance de calcul des ordinateurs, bien que continue, n'est pas suffisante face à des tâches d'analyse de plus en plus complexes. Dans ce contexte, une problématique a été notamment étudiée par la communauté scientifique: l'extraction de motifs intéressants ("pattern mining"). Ces motifs représentent des régularités suivies par une partie des données (on parle aussi de "modèles locaux"). Cette problématique a été introduite dans les années 90 avec pour application l'analyse des paniers d'achats des consommateurs. Une grande variété de types de motifs et d'applications a été étudiée depuis (p.ex. dans les domaines de la sécurité, de la médecine, ou du commerce). Toutefois, les défis restent importants, notamment lorsqu'il s'agit d'analyser des données environnementales. En effet, les phénomènes sous-jacents et les données collectées sont complexes et variées (p.ex. images satellitaires, données collectées sur le terrain, données issues de modèles). L'exploitation de telles données est difficile et nécessite des méthodes d'analyse avancées. Ce séminaire présentera plusieurs travaux visant à extraire des motifs spatio-temporels plus riches et plus pertinents dans ces masses de données complexes.

Seminaire : Séminaire G-MOD - Simulation de rubans et validation physique

28/03/2022 à 16h30

Lien zoom : https://univ-amu-fr.zoom.us/j/83169477124?pwd=Q05rS2lnNzhqNllJODhKK3c2VzMvdz09 Si à l'origine l'informatique graphique concernait surtout l'animation, de nos jours les modèles de la communauté graphique ont tendance à être appliqués au monde réel par exemple dans le domaine de la fabrication. Cependant, ces modèles proposent parfois des énergies ad hoc et la prédiction numérique peut s'éloigner significativement du résultat physique. Faut-il alors utiliser des modèles plus mécaniques ? Dans un premier temps, je présenterai mon travail de thèse sur la modélisation de rubans. On verra par exemple que les tiges ne se comportent pas comme des rubans. Une bonne partie de mon travail consiste à valider le modèle que j'ai établi et à en montrer les limites. Dans un second temps, je parlerai de validation de modèles par protocoles expérimentaux relativement simple à mettre en place. Ce travail collaboratif s'inspire de protocoles mécaniques pour valider des modèles de tiges, rubans, coques. Il serait dommage de rejeter un modèle numérique, sous prétexte qu'il n'a pas assez de fondements mécaniques. On peut l'étudier pour comprendre sous quelles hypothèses son comportement est prédictif. On conclura ainsi que le choix du modèle utilisé doit correspondre à son usage. Il serait judicieux si cela n'a pas déjà été fait de tester le comportement physique de ce modèle.

Seminaire : Séminaire G-MOD - Simulation de rubans et validation physique

28/03/2022 à 16h30

Si à l'origine l'informatique graphique concernait surtout l'animation, de nos jours les modèles de la communauté graphique ont tendance à être appliqués au monde réel par exemple dans le domaine de la fabrication. Cependant, ces modèles proposent parfois des énergies ad hoc et la prédiction numérique peut s'éloigner significativement du résultat physique. Faut-il alors utiliser des modèles plus mécaniques ? Dans un premier temps, je présenterai mon travail de thèse sur la modélisation de rubans. On verra par exemple que les tiges ne se comportent pas comme des rubans. Une bonne partie de mon travail consiste à valider le modèle que j'ai établi et à en montrer les limites. Dans un second temps, je parlerai de validation de modèles par protocoles expérimentaux relativement simple à mettre en place. Ce travail collaboratif s'inspire de protocoles mécaniques pour valider des modèles de tiges, rubans, coques. Il serait dommage de rejeter un modèle numérique, sous prétexte qu'il n'a pas assez de fondements mécaniques. On peut l'étudier pour comprendre sous quelles hypothèses son comportement est prédictif. On conclura ainsi que le choix du modèle utilisé doit correspondre à son usage. Il serait judicieux si cela n'a pas déjà été fait de tester le comportement physique de ce modèle.

Seminaire : Séminaire GMOD - Towards a standardized system that transforms textured 3D geometry into knitted textiles

11/03/2022 à 14h00

Invité (visio) : Georges Nader Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Towards a standardized system that transforms textured 3D geometry into knitted textiles. Résumé : We introduce a flexible and customizable system for the computational design and production of functional, multi-material, and three-dimensional knitted textiles. Our system simplifies the knitting of 3D objects with complex, varying patterns that use multiple yarns and stitch patterns by separating the high-level design specification in terms of geometry, stitch patterns, materials or colors from the low-level, machine-specific knitting instruction generation. Starting from a triangular 3D mesh and a 2D texture that specifies knitting patterns on top of the geometry, our system generates the required machine instructions in three major steps. First, the input is processed and the KnitNet data structure is generated. This graph structure serves as an abstract interface between the high-level geometric and knitting configuration and the low-level, machine-specific knitting instructions. Second, a graph rewriting procedure is applied on the KnitNet that produces a sequence of abstract machine actions. Finally, the low-level machine instructions are generated by adapting those abstract actions to a specific machine context. We showcase the potential of this computational approach by designing and fabricating a variety of objects with complex geometries, multiple yarns and multiple stitch patterns. Venez nombreux !

Seminaire : Séminaire CANA : Kévin Perrot

08/03/2022 à 14h00

Orateur : Kévin Perrot (CANA, LIS)
Salle : TPR2-04.05
Titre : Théorème du point fixe de Kleene en calculabilité
Abstract : Pour toute transformation de programme h calculable, il existe un programme n tel que n et h(n) font la même chose. Ce théorème est génial, et sa preuve d'une simplicité déconcertante. De plus ses corollaires sont nombreux, comme l'indécidabilité de l'arrêt, et l'existence de quine (programme qui affiche en sortie son propre code) dans tout langage de programmation acceptable. On programmera un quine ensemble :-) Cet exposé est tiré d'une séance de l'UE Calculabilité Avancée en M1 Info, pas de résultat nouveau, juste un peu de culture.

Seminaire : Séminaire GMOD - Progressivité et Analyse Topologique de Données Scalaires

04/03/2022 à 10h00

Invité : Jules Vidal (LIP6) Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Progressivité et Analyse Topologique de Données Scalaires Résumé : L’analyse topologique de données forme une famille d’outils qui permettent l’extraction générique et efficace de caractéristiques structurelles dans les données. Cependant, bien que ces techniques aient des complexités asymptotiques connues et raisonnables, elles sont rarement interactives en pratique sur des jeux de données réels, ce qui limite leur utilisation pour l’analyse et la visualisation interactives de données. Dans cette présentation je décrirai les travaux réalisés pendant ma thèse, durant laquelle j'ai cherché à développer des approches progressives pour l’analyse topologique de données scalaires. Dans ce contexte, une méthode progressive est une technique qui peut être interrompue pour fournir rapidement un résultat approché exploitable, et est capable de le raffiner graduellement. Dans un premier temps, nous présentons une représentation hiérarchique des données d’entrée, qui permet de définir des algorithmes topologiques coarse-to-fine efficaces. En conséquence, nous introduisons deux algorithmes progressifs pour le calcul des points critiques et du diagramme de persistance d’un champ scalaire. Ces méthodes fournissent des sorties interprétables en cas d’interruption, offrent un retour visuel continu tout au long du calcul et sont plus rapides en pratique que leurs homologues non progressifs. Ensuite, nous revisitons ce cadre progressif pour introduire un algorithme pour le calcul approché du diagramme de persistance d’un champ scalaire, avec des garanties sur l’erreur d’approximation associée. Enfin, afin d’effectuer une analyse visuelle de données d’ensemble, nous présentons un nouvel algorithme progressif pour le calcul du barycentre de Wasserstein d’un ensemble de diagrammes de persistance, une tâche notoirement coûteuse. Nous étendons cette méthode à un algorithme de classification topologique de données d’ensemble, qui est progressif et capable de respecter une contrainte de temps. Venez nombreux !

Seminaire : Séminaire GMOD - Rendu basé physique de matériaux scintillants

21/02/2022 à 10h00

Invité : Xavier Chermain Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Rendu basé physique de matériaux scintillants Résumé : Le rendu basé physique est un processus important en informatique graphique, qui prend en entrée une scène 3D composée d'une caméra, de lumières et de formes géométriques ayant toutes un matériau. La propagation de la lumière est simulée en se basant sur des équations physiques, permettant d'obtenir une photo réaliste de la scène 3D virtuelle. La modélisation d'apparence est indispensable pour représenter la grande diversité d'apparences du monde réel. Dans cet exposé, je parlerai de la modélisation d'apparence des matériaux scintillants. Ce type d'apparence est difficile à modéliser à cause des fortes variations de réflexions lumineuses lors d'un petit changement de position ou de direction d'observation. Je parlerai de mes principales contributions dans ce domaine. Venez nombreux !

Conference : Séminaire CaNa -- Ilya Galanov

08/02/2022 à 14h00

Orateur: Ilya Galanov
Salle: TPR2-04.05
Titre : Purely local self-assembly algorithm for a quasiperiodic octagonal tiling
Abstract: Self-assembly is the process in which the components of a system, whether molecules, polymers, or macroscopic particles, are organized into ordered structures as a result of local interactions between the components themselves, without exterior guidance. This talk is devoted to the self-assembly of aperiodic tilings. Aperiodic tilings serve as a mathematical model for quasicrystals - crystals that do not have any translational symmetry. Because of the specific atomic arrangement of these crystals, the question of how they grow remains open. Simulations strongly support the evidence that the algorithm we developed grows aperiodic tilings up to an unavoidable but neglectable proportion of missing tiles. In this talk, we state the first theorem regarding the Golden-Octagonal tilings and formulate conjectures for future results.

Rencontre : Demi-journée pôle calcul - Algorithmique et Structures Discrètes

20/01/2022 à 09h30

Orateurs :
- Janna Burman (LRI) "Time-Optimal Self-Stabilizing Leader Election in Population Protocols”
- Alessia Milani (LIS)
- Eloi Perdereau (LIS)

Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr

Seminaire : Séminaire G-MOD - L’apprentissage profond des nuages de points 3D : Application aux données LiDAR

14/01/2022 à 14h00

Dans le cadre des séminaires G-MOD, nous avons le plaisir d'accueillir Jules Morel. Résumé : La capacité de la technologie LiDAR à capturer des informations détaillées sur la structure des forêts a attiré une attention croissante de la part de la communauté des écologues et des forestiers. Le LiDAR terrestre, notamment, apparaît comme un outil prometteur pour recueillir les caractéristiques géométriques des arbres à une précision millimétrique. Puisque cette technologie produit des quantités de données élevées, la recherche actuelle se concentre sur la mise au point de chaîne de traitement automatique. Cette présentation exposera comment l'utilisation du deep learning répond à une des étapes clés de cette chaîne de traitement: la classification des points 3D.

Seminaire : Séminaire MoVe avec Marie Fortin

09/12/2021 à 10h30

Title : How undecidable are HyperLTL and HyperCTL*? Abstract: Temporal logics for the specification of information-flow properties are able to express relations between multiple executions of a system. Two of the most important such logics are HyperLTL and HyperCTL*, which generalise LTL and CTL* by trace quantification. It is known that this expressiveness comes at a price, i.e., satisfiability is undecidable for both logics. We settle the exact complexity of these problems, showing that both are in fact highly undecidable: we prove that HyperLTL satisfiability is \Sigma^1_1-complete and HyperCTL* satisfiability is \Sigma^2_1-complete. To prove \Sigma^2_1 membership for HyperCTL*, we prove that every satisfiable HyperCTL* formula has a model that is equinumerous to the continuum, the first upper bound of this kind. We prove this bound to be tight. This is joint work with Louwe B. Kuijer, Patrick Totzke and Martin Zimmermann. Salle 4.05 TPR2 (Luminy)

Seminaire : Séminaire CaNa -- Théo Grente

07/12/2021 à 14h00

Orateur: Théo Grente
Salle: TPR2-04.05
Titre : Conjunctive grammars, cellular automata and logic
Abstract: Conjunctive grammars are an extension of context free grammars with a conjunction operation. Their expressive power (even on a unary alphabet) is largely unknown.
When restricting time, space or even communication, cellular automata (CA) can act as languages recognizer defining complexity classes.
The goal of this talk is to prove the inclusion of conjunctive languages in one of CA complexity classes.
The proof uses a programming method which relies on exact characterizations of interesting CA complexity classes by sub-logics of ESO (existential second-order logic) with Horn formulas as their first-order part. By using this method, we just have to define conjunctive grammars in our logic to obtain an inclusion result.

Seminaire : Séminaire MoVe avec Antonio Casares

02/12/2021 à 10h30

Lieu: Salle 4.05 du bâtiment TPR2 (Luminy)
Title: On a correspondence between memory structures for Muller games and Rabin automata
Abstract: In the study of infinite duration games over graphs, an important parameter is the amount of memory required by the players to play optimally. Two different kinds of memory structures can be distinguished: those that may depend in the particular structure of each specific game (unconstrained memories), and those that can only depend on the sequence of colors that has been produced (chromatic memories). In this talk, I will discuss these two kinds of memories in the case of Muller games. We show that chromatic memories exactly correspond to deterministic Rabin automata, while unconstrained memories correspond to Good-For-Games automata. Moreover, we prove that the difference on the size between the two them can be exponential in the number of colors defining the winning condition. This is a joint work with Thomas Colcombet and Karoliina Lehtinen.

Seminaire : Séminaire du pôle SD - Demi-Journée des nouveaux entrants

29/11/2021 à 09h00

Nous organisons la journée des nouveaux entrants le 29 novembre de 9h à 13h. Les docs, post-doc, et permanents ayant intégrés le pôle dans les deux dernières années viendront présenter leur travaux. Et un traditionnel buffet suivra.

Seminaire : Journée Thématique Quantique

26/11/2021 à 10h00

La journée du 26 novembre au CIRM a l'objectif principal de faire rencontrer dans une seule salle, pour la première fois, tous les chercheurs AMU sur le domaine "Quantique" interessés à s'inscrire dans la récente stratégie nationale sur les technologies quantiques, notamment d’un point de vue informatique/mathématique/physique théorique.

Seminaire : Séminaire MoVe - Filip Mazowiecki

25/11/2021 à 13h00

Lieu: Luminy, batiment TPR2, salle 5.37
Titre: The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Abstract: We consider weighted automata over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems boundedness and zero isolation ask whether there is a sequence of words that converge to infinity and zero, respectively. In the general model both problems are undecidable so we focus on the copyless linear restriction. There, we show that the boundedness problem is decidable, exploiting the Simon’s factorization forest theorem. As for the zero isolation problem we need to further restrict the class. We obtain a model, where zero isolation becomes equivalent to coverability of orthant vector addition systems (OVAS), a new model in the VAS family interesting on its own. Assuming Schanuel’s conjecture is true, we prove decidability of coverability for three-dimensional OVAS, which gives decidability of zero isolation in a model with at most three registers.

Seminaire : IA-SANTE : colloque Sciences Numériques et IA pour la santé à AMU

25/11/2021 à 09h00

Aix-Marseille Université organise les 25 et 26 Novembre 2021 un colloque en « Sciences Numériques et Intelligence Artificielle pour la Santé ». L’objectif principal sera de réunir pour la première fois l’ensemble des acteurs d’Aix-Marseille Université et du Centre Hospitalier Universitaire impliqués dans la création de l’institut Laënnec, institut d'établissement AMU en "sciences numériques et intelligence artificielle pour la santé" en partenariat avec l’APHM et l’IPC.

Seminaire : Séminaire CaNa -- Silvère Gangloff

23/11/2021 à 14h00

Orateur: Silvère Gangloff
Titre : Classes de transitivité pour les sous-décalage de type fini multi-dimensionnels.
Abstract: Ce travail est en commun avec B.Hellouin et P.Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le mélange. Dans des travaux récents, nous avons montré, avec B.Hellouin et M.Sablik, qu'en quantifiant ces propriétés, il est possible de caractériser la complexité de ces systèmes dynamique en fonction de la quantité de transitivité/mélange (en particulier du point de vue calculabilité). Cependant les différentes classes de transitivité (relatives à cette quantification) sont mal comprises dans le cas général. Avec B.Hellouin et P.Oprocha, nous travaillons à caractériser ces classes dans le cadre restreint des Hom shifts, c'est à dire les sous-décalages définis par des ensembles de motifs interdits consistant en des dominos dont les symboles ne sont pas voisins dans un graphe fini non-orienté. Dans cet exposé, je présenterai le problème, ainsi que des résultats obtenus et attendus dans cette direction, qui laissent espérer une caractérisation complète des classes de transitivité dans le cas des Hom shifts.

Rencontre : Demi-journée pôle calcul - Géométrie et Topologie du Calcul

18/11/2021 à 00h00

Orateurs :
- Dmitry Sokolov (LORIA) "How to compute locally invertible maps"
- Corentin Travers (LABRI) "Synchronous t-Resilient Consensus in Arbitrary Graphs"
- Victor Chepoi (LIS) "1-safe Petri nets and special cube complexes"

Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr

Conference : Séminaire CaNa -- Leonardo Novo

16/11/2021 à 14h00

Speaker: Leonardo Novo
Title: Spatial search by continuous-time quantum walk
Abstract: I will present two recent contributions about the performance of quantum search algorithms based on continuous-time quantum walks [1,2]. First, I will present some general results about the performance of the algorithm introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], which uses a continuous-time quantum walk to find a marked node on a graph of n nodes. This algorithm is said to be optimal if it can find any of the nodes in the graph in O(sqrt(n)) time. I will present conditions, based on the spectrum of the Hamiltonian driving the quantum walk, that can be used to predict whether the algorithm is optimal on a given graph. In the second part of the talk, I will present a new algorithm based on Hamiltonian evolution that finds marked nodes on any ergodic reversible Markov chain P quadratically faster than its classical hitting time. This algorithm can be seen as a quantum walk on the edges of a Markov chain and its performance matches that of discrete-time quantum walk search algorithms based on the Szegedy formalism. This work improves upon the recent work of [Phys. Rev. A 102, 022227 (2020) ] and finally closes a theoretical gap between the performance of continuous-time and discrete-time quantum walk approaches for search.
References:
- On the optimality of spatial search by continuous-time quantum walk, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 032214 (2020)
- Finding a marked node on any graph by continuous-time quantum walk , Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 022227 (2020)

Seminaire : Séminaire CaNa -- Shyan Shaer Akmal

04/11/2021 à 15h00

Orateur: Shyan Shaer Akmal
Title: Majority-3SAT (and Related Problems) in Polynomial Time
lien zoom
Abstract: Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^{n-1} satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k.
It recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ∈(0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^{n} satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time).
In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.

Seminaire : Séminaire CaNa -- Titouan Carette

02/11/2021 à 14h00

Orateur : Titouan Carette
Salle : TPR2-04.05
Title: ZX-calculus, a Swiss army katana for quantum computing.
Abstract: It usually requires months to master the concepts of quantum mechanics necessary to quantum computing. This time can be reduced drastically by using conveniently designed notations. The ZX-calculus, a graphical language to denote tensor, have been claimed to be such a powerful tool allowing to learn and then reason efficiently on quantum processes. I will support this claim by providing several examples of applications through three extensions of the ZX-calculus that have been introduced in the recent years, namely: mixed states, scalable, and stream ZX-calculus.

Rencontre : Demi-journée pôle calcul - Logique et méthodes formelles

14/10/2021 à 09h30

Lieu : FRUMAM

Orateurs :
- Ugo Dal Lago (UniBo) "On Higher-Order Cryptography"
- Pierre Clairambault (LIS) "Games with no Winner: an Introduction to Game Semantics"
- Raphaelle Crubillé (LORIA) “Sémantique dénotationelle pour les languages de programmation probabilistes”

Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr

Seminaire : Séminaire CaNa -- Giovanni De Felice

05/10/2021 à 14h00

Salle : TPR2 - 04.05
Titre : Quantum Natural Language Processing
Résumé : I will talk about string diagrams, how they are used to capture different models of quantum computation (e.g. circuit-based, measurement-based and linear optical quantum computing), as well as different models of natural language syntax (e.g. context-free grammars, pregroup grammars). I will show how to use this to perform natural language processing on currently available quantum hardware.

Conference : Séminaire DYNI - Luca Tassara - Akvaplan-Niva

29/09/2021 à 14h00

1. Akvaplan-niva: a small Arctic company looking to a bright innovative future. This presentation will focus on the investments and potential of akvaplan-niva on the use and development of unmanned autonomous vehicles. An overview of past,current and future projects involving our glider fleet will be presented 2. Ecological founding from passive acoustic data collected from a sea glider in the norwegian sea. This presentation will focus on the published and preliminary results of acoustic data collected in 2018 by a sea glider off the Lofoten-Vesterålen archipelago. Species presence, occurrence and vocal behaviour will be presented along with a study on the anthropogenic noise recorded in the area.

Seminaire : Séminaire de rentrée du pôle SD

23/09/2021 à 10h00

Lieu : St Charles - Salle du séminaire, 2ème étage à la FRUMAM Thème : détection d’anomalies & sciences des données. Présenté par Fidel Cacheda Titre : Early Detection of Anomalies: Presenting a new problem Abstract: In this talk we introduce the Early Detection of Anomalies problem, an area where the Telematics Research group from the University of A Coruña (Spain) has been focusing his work ultimately. Firstly, the research background is introduced and then we present two specific cases of early detection on social networks: early detection of depression and of cyberbullying. From this point, we introduce the generic problem of early detection of anomalies and the ongoing work the research group is developing and the open lines and questions.

Conference : Conférence Internationale Francophone sur la Science des Données (CIFSD)

09/06/2021 à 08h00

La Conférence Internationale Francophone sur la Science des Données (CIFSD) est un événement scientifique permettant de réunir à la fois des universitaires et des industriels travaillant en science des données. L'édition 2021 aura lieu du 9 au 11 juin à Marseille (France). En raison de la situation sanitaire actuelle, elle aura lieu intégralement à distance. L’inscription est gratuite mais obligatoire. Cette conférence permet aux chercheurs francophones de présenter leurs travaux et d'échanger leurs idées ; elle donne aussi aux doctorants l'occasion d'appréhender un large panorama sur leur domaine de recherche et de bénéficier d'un premier contact à la fois rigoureux et bienveillant avec l'ensemble des activités liées à la communication scientifique. C’est également l’occasion de nouer des contacts avec d'autres équipes de recherche et des partenaires industriels. Nous encourageons les soumissions d’articles (date limite : 2 avril), qu’il s’agisse de travaux théoriques ou appliqués, sur tous les aspects du cycle de vie de la science des données (le nettoyage et la préparation des données ; la transformation ; l'extraction, l'inférence, l'apprentissage ; la visualisation ; l'explicabilité ; la confidentialité ; etc.). Pour cette édition, les travaux portant sur la science de données pour la santé seront particulièrement appréciés. Plus d'informations sur le site web de la conférence : https://cifsd-2021.sciencesconf.org

Conference : Colloque international interdisciplinaire Droit & Sciences : Le bruit en mer : du développement des activités maritimes à la protection de la faune marine

04/06/2021 à 09h00

Vendredi 4 juin 2021

Encore peu saisi par les juristes, le bruit en mer lié au développement des activités maritimes versus la protection de la faune marine constitue, depuis plusieurs années, un sujet de recherche à part entière dans le domaine des sciences, notamment au Canada et aux États-Unis. Ce colloque, inédit en France, vise à promouvoir des interactions interdisciplinaires sur fond d’un dialogue constructif entre chercheurs, acteurs économiques, membres de la société civile et autorités administratives en vue de dégager des solutions pour concilier développement des activités maritimes et protection de la faune marine. Un état de la recherche sur le bruit en mer et les effets du trafic maritime sur la faune marine sera tout d’abord dressé pour tenter de mesurer les efforts devant être déployés afin de réduire le bruit anthropique et limiter les impacts sur le milieu marin.

Organisée par des enseignants-chercheurs de l’Université de Toulon membres des laboratoires CDPC, CERC et LIS, avec les soutiens de la Préfecture maritime de la Méditerranée et des pôles INPS et MEDD, cette manifestation se tiendra en présentiel à l’amphithéâtre 300 de la Faculté de droit de Toulon (pour les intervenants uniquement) et en visioconférence (pour les autres participants compte tenu des contraintes sanitaires liées à la Covid-19)

En présentiel pour les intervenants : Amphithéâtre 300 - Faculté de droit de Toulon En ligne pour les autres participants sur inscription (gratuite & obligatoire) : fac.droit@univ-tln.fr

Seminaire : Séminaire - Yuki Mitsufuji: localisation, classification and separation of acoustic sources

26/05/2021 à 16h00

Yuki Mitsufuji (Member, IEEE) received the B.S. and M.S. degrees in information science from Keio University, Tokyo, Japan, in 2002 and 2004, respectively. He is currently working toward the Ph.D. degree with the University of Tokyo. He is a Deputy General Manager with Speech and Music Group, Sony Corporation, Tokyo, Japan. He has been leading teams that developed the sound design for the PlayStation game title called “Gran Turismo Sport,” and spatial audio solution called “Sonic Surf VR.” In 2004, he joined Audio Technology Development Group, Sony Corporation. From 2011 to 2012, he was a Visiting Researcher with Analysis/Synthesis Team, Institut de Rechereche et Coordination Acoustique/Musique (IRCAM), Paris, France. He was involved in the 3DTV content search project sponsored by European Project FP7, in research collaboration with IRCAM. He is a Reviewer with ICASSP, INTERSPEECH, etc. He currently became a General Chair of Signal Separation Evaluation Campaign where his team had scored the best results for three consecutive years. He has numerous granted patents for audio signal processin Abstract: 1) ACCDOA: Activity-Coupled Cartesian Direction of Arrival Representation for Sound Event Localization and Detection https://arxiv.org/abs/2010.15306 Neural-network (NN)-based methods show high performance in sound event localization and detection (SELD). Conventional NN-based methods use two branches for a sound event detection (SED) target and a direction-of-arrival (DOA) target. The two-branch representation with a single network has to decide how to balance the two objectives during optimization. Using two networks dedicated to each task increases system complexity and network size. To address these problems, we propose an activity-coupled Cartesian DOA (ACCDOA) representation, which assigns a sound event activity to the length of a corresponding Cartesian DOA vector. The ACCDOA representation enables us to solve a SELD task with a single target and has two advantages: avoiding the necessity of balancing the objectives and model size increase. In experimental evaluations with the DCASE 2020 Task 3 dataset, the ACCDOA representation outperformed the two-branch representation in SELD metrics with a smaller network size. The ACCDOA-based SELD system also performed better than state-of-the-art SELD systems in terms of localization and location-dependent detection. 2) D3Net: Densely connected multidilated DenseNet for music source separation https://arxiv.org/abs/2010.01733 Music source separation involves a large input field to model a long-term dependence of an audio signal. Previous convolutional neural network (CNN)-based approaches address the large input field modeling using sequentially down- and up-sampling feature maps or dilated convolution. In this paper, we claim the importance of a rapid growth of a receptive field and a simultaneous modeling of multi-resolution data in a single convolution layer, and propose a novel CNN architecture called densely connected dilated DenseNet (D3Net). D3Net involves a novel multi-dilated convolution that has different dilation factors in a single layer to model different resolutions simultaneously. By combining the multi-dilated convolution with DenseNet architecture, D3Net avoids the aliasing problem that exists when we naively incorporate the dilated convolution in DenseNet. Experimental results on MUSDB18 dataset show that D3Net achieves state-of-the-art performance with an average signal to distortion ratio (SDR) of 6.01 dB.

Seminaire : Séminaire Pôle Calcul -- Zoltan Szabo

20/05/2021 à 10h00

Titre : Vector-valued Prediction with RKHSs and Hard Shape Constraints
Abstract : Shape constraints (such as non-negativity, monotonicity, convexity, or supermodularity) provide a principled way to encode prior information in predictive models with numerous successful applications in econometrics, finance, biology, reinforcement learning, and game theory. Incorporating this side information in a hard way (for instance at all points of an interval) however is an extremely challenging problem. We propose a unified and modular convex optimization framework to encode hard affine SDP constraints on function derivatives into the flexible class of vector-valued reproducing kernel Hilbert spaces (RKHS). The efficiency of the technique is illustrated in the context of joint quantile regression (analysis of aircraft departures), convoy localization, safety-critical control (piloting an underwater vehicle while avoiding obstacles), and econometrics (learning of production functions). This is joint work with Pierre-Cyril Aubin-Frankowski. Preprint: http://arxiv.org/abs/2101.01519

Seminaire : Séminaire I&M - Raphaël Abelé

30/04/2021 à 14h00

Titre : Traitement d'images pour l'automatisation de caractérisation sécuritaire de circuits intégrés.
Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
L’automatisation est un enjeu stratégique dans l’industrie. En général, certaines technologies ne peuvent évoluer qu’à condition que la technologie précédente soit parfaitement maîtrisée. Cette maîtrise peut aboutir à lamise en place de procédures automatiques pour des tâches répétitives optimisables.
Dans le contexte très particulier de la caractérisation sécuritaire de circuits intégrés, nous proposons d’automatiser le déplacement du système optique d’un banc d’injection laser. Ce banc est en effet muni d’une caméra infrarouge qui, couplée à un microscope optique, permet d’explorer les entrailles d’une puce électronique. Ce système optique est utilisé à des fins d’analyses, pour étudier le comportement d’un circuit intégré à la suite de perturbations provoquées par des tirs laser localisés sur des points de ses pistes conductrices. Ces tirs sont principalement calibrés et ciblés grâce au système optique.
À travers ce travail, notre objectif est de rendre possible l’automatisation de processus qui requièrent initialement l’intervention humaine. Nous proposons pour cela deux outils dédiés au domaine de la vision infrarouge de circuits intégrés. Des processus tels que le ciblage de structures électroniques d’intérêt pourront être automatisés grâce à ces outils. Dans un premier temps, un processus de mise au point automatique du système optique est présenté, permettant de focaliser les pistes conductrices du circuit intégré, selon des critères propres au contexte. Deux approches sont mises en place, fondées sur l’analyse des images dans le domaine temps-fréquence : une approche passe par une transformée en ondelettes des images, l’autre passe par une transformée polynomiale. Si elles sont toutes deux optimisées pour l’analyse d’images infrarouges, les autofocus qui en découlent ont chacun leur avantage : temps d’exécution pour l’un, précision pour l’autre. Dans un second temps, nous présentons un système de localisation de structures électroniques. Ce système met en œuvre des appariements de graphes et fait intervenir des descripteurs décisifs pour notre application. Dans notre contexte, outre sa robustesse, notre approche tire profit des graphes dans la reconnaissance de formes à partir de simples schématisations.
Le déploiement de ces outils offre des perspectives majeures pour l’amélioration des caractérisations sécuritaires : scans de composants, optimisation et reproductibilité de caractérisation, reconnaissance de composants et de structures ou encore aide à l’interprétation de fautes. De nombreuses pistes sont ouvertes, pour lesquelles la vision par ordinateur est l’élément clé.

Conference : LES LIMITES DE L'INTELLIGENCE ARTIFICIELLE - GRAND SÉMINAIRE - Lundi 26 avril avec YANN LE CUN Prix Turing, Facebook AI Research New York University

26/04/2021 à 16h30

Les laboratoires IMSIC et LIS seront heureux d'accueillir le séminaire du groupe de recherche _ AI Studies_ le lundi 26 avril de 16h30 à 18h00 en visioconférence. Pour interroger les limites de l'intelligence artificielle, tous les participants peuvent contribuer en posant une question lors de l'inscription. Ce lundi 26 avril, nous discuterons avec Yann Le Cun, Prix Turing. https://fr.wikipedia.org/wiki/Yann_Le_Cun Pour accéder à la salle de visioconférence, validez votre inscription pour cette visioconférence exceptionnelle !
David Galli, Franck Renucci et Benoît Le Blanc

Seminaire : Séminaire d'équipe LIRICA

26/04/2021 à 14h00

Orateur : Wessley Fussner Titre : Ortholattices résiduels comme nouvelle approche de la logique quantique Résumé : Cet exposé passe en revue nos récentes tentatives d'étudier le raisonnement quantique à l'aide des outils des logiques sous-structurelles. Nous introduisons les ortholattices résiduels comme des modèles algébriques généralisant les modèles habituels de la logique quantique, et illustrons qu'ils donnent une version `intuitioniste' de la logique quantique dans laquelle la logique quantique classique peut être interprétée par une traduction à double négation. Nous discutons également des applications aux problèmes de décidabilité. Lien zoom : Time: Apr 26, 2021 02:00 PM Paris Join Zoom Meeting https://univ-amu-fr.zoom.us/j/8390049740 Meeting ID: 839 004 9740

WorkShop : 10th International Workshop Weighted Automata: Theory and Applications

19/04/2021 à 00h00

10th International Workshop Weighted Automata: Theory and Applications WATA 2020/2021 (reported because of the Covid-19) April 19–23, 2021, CIRM@Marseille, France The workshop covers all aspects of weighted automata, ranging from the theory of weighted automata and quantitative logics to applications for real-time systems and natural language processing. The aim is to present tutorials and survey lectures by outstanding scientists in this area. We invite everybody to participate in this workshop without fee and to present their own technical contributions in this area.

Rencontre : Saison indécidabilité et impossibilité

08/04/2021 à 14h00

Dans le cadre du séminaire MoVe, une série d'exposés est prévue au cours des années 2019/2020 et 2020/2021 sur les thèmes de l'indécidabilité et de l'impossibilité. Ces exposés font intervenir des orateurs des équipes MoVe, DALGO et ACRO du LIS et des équipes GDAC et LDP de l'I2M.

Le programme est disponible sur la page des séminaires de l'équipe MoVe : ICI. Les dernières échéances sont les 11 et 25 février 2021 puis 11 mars 2021 et 8 et 29 avril 2021.

Cette série d'exposés s'inscrit dans le cadre des activités communes du Pôle Calcul du LIS.

Elle est évidemment ouverte aux collègues d'autres équipes/pôles intéressés par ces thèmes.

Seminaire : Séminaire Pôle Calcul -- Olivier Bournez

25/03/2021 à 00h00

Titre : Computations with ordinary differential equations
Abstract : Computability, complexity, programming, continuous time computations, old and recent analog models of computations: Why ordinary differential equations are fun and a pleasant way to do computer science in 2020. Olivier et ses co-auteurs François Fages, Guillaume Le Guludec et Amaury Pouly, ont reçu le prix 2019 du journal La Recherche pour leurs travaux sur les modèles de calcul analogiques et en particulier l’article Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs. https://www.lemonde.fr/blog/binaire/2019/02/15/la-revanche-du-calcul-analogique/

Seminaire : Séminaire I&M - Marc-Adrien Hostin

26/02/2021 à 14h00

Titre : Méthodes d’apprentissage profond pour la segmentation d’images IRM multiparamétriques musculaires : Suivi et évaluation de stratégies thérapeutiques de pathologies neuromusculaires.
Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Dans le cadre des maladies neuromusculaires, le tissu musculaire est le siège d’un certain nombre d’altérations s’accompagnant de phénomènes inflammatoires, fibrotiques, nécrotiques conduisant à un remplacement progressif du tissu musculaire par des adipocytes et entraînant une perte fonctionnelle. L’imagerie par Résonance Magnétique (IRM) s’est imposée comme un outil de choix pour l’exploration des maladies neuromusculaires [1]. Récemment, des séquences IRM ont permis l’obtention de cartes paramétriques susceptibles de fournir des métriques reliées à l’infiltration graisseuse et à l’inflammation, identifiées comme des biomarqueurs potentiels des maladies neuromusculaires [2]. L’acquisition de ces cartes paramétriques autorise l’étude des neuropathies au travers de scores quantitatifs. Dans ce champ disciplinaire, le défi actuel est de pouvoir fournir des indices quantitatifs fiables et suffisamment sensibles pour pouvoir suivre l’évolution lente de ces pathologies et à terme de déterminer l’efficacité de stratégies thérapeutiques qui sont en cours de développement. Ce challenge nécessite d’une part l’optimisation des méthodes d’acquisition IRM et d’autre part le développement de techniques robustes de segmentation d’images permettant d’associer ces métriques à chaque muscle pris de façon individuelle. En effet, l’utilisation appropriée de cartes paramétriques IRM nécessite de sélectionner l’information sur les zones d’intérêt, les muscles, en ignorant les zones comme la graisse sous-cutanée et l’os. Le défi est d’autant plus relevé que le contraste entre les différents muscles est inexistant et que le contraste de l’infiltrat graisseux pathologique est identique au contraste de la graisse sous-cutanée non pathologique. Les méthodes de segmentation manuelle sont fastidieuses, inapplicables dans un contexte clinique et peuvent être opérateurs-dépendantes [3]. Les méthodes automatiques existantes ne sont pas suffisantes pour prendre en compte la complexité de la tâche de segmentation, particulièrement pour les sujets atteints d’infiltration graisseuse, rendant difficile l’identification des muscles. L’apprentissage profond montre cependant des résultats prometteurs pour les cas les plus atteints, avec l’utilisation de réseaux de convolutions [4].
L’objectif de ce projet est de développer des techniques d’apprentissage profond permettant de segmenter de façon fiable les muscles individuels au niveau d’images IRM de patients atteints de pathologies neuromusculaires. Les résultats de segmentation, donc d’identification des muscles, pourront compléter les différentes cartes paramétriques afin d’extraire pour chaque muscle des indices quantitatifs liés aux maladies neuromusculaires.
Bibliographie :
1. Mercuri E, Pichiecchio A, Allsop J, Messina S, Pane M, Muntoni F. Muscle MRI in inherited neuromuscular disorders: Past, present, and future. Journal of Magnetic Resonance Imaging. 2007;25(2):433-440.
2. Morrow JM, Sinclair CDJ, Fischmann A, et al. MRI biomarker assessment of neuromuscular disease progression: a prospective observational cohort study. The Lancet Neurology. 2016;15(1):65-77.
3. Barnouin Y, Butler-Browne G, Voit T, et al. Manual segmentation of individual muscles of the quadriceps femoris using MRI: a reappraisal. J Magn Reson Imaging. 2014;40(1):239-247. doi:10.1002/jmri.24370.
4. Gadermayr M, Disch C, Müller M, Merhof D, and Gess B. A comprehensive study on automated muscle segmentation for assessing fat infiltration in neuromuscular diseases. Magnetic resonance imaging 2018 ;48:20–26.

Seminaire : Séminaire Pôle Calcul -- Vincent Nozick

18/02/2021 à 10h00

Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.fr

Titre : Introduction aux Algèbres Géométriques et leur aspects calculatoires
Abstract : Les Algèbres Géométriques constituent un ensemble d'outils intuitifs permettant de créer et de manipuler des objets géométriques. Longtemps entre les mains des mathématiciens, les informaticiens commencent à se les approprier et à entrevoir leur potentiel. Cet exposé s'inscrit dans cette démarche d'explication simple et commencera par une introduction sur les fondements de ces algèbres, à savoir les vecteurs, les multivecteurs ainsi que quelques produits sur ces multivecteurs. Nous verrons ensuite comment les utiliser pour résoudre efficacement et très simplement des problèmes de géométrie, en portant une attention particulière sur l'aspect calculatoire.

Seminaire : Séminaire CaNa - Amélia Durbec

16/02/2021 à 14h00

Oratrice : Amélia Durbec
Titre : Classical and quantum causal graph dynamics
Abstract : Causal graph dynamics are a twofold extension of cellular automata : the underlying grid is extended to an arbitrary bounded-degree graph and the graph itself is allowed to evolve over time. Such dynamics are insightful toy models for theoritical physics in both the reversible and the quantum regime. In this talk, we are going to see how a graph dynamics can be reversible and yet create/destroy vertices, and that vertex names are necessary in order to prevent faster-than-light signalling. We will finish this talk with outlooks towards graph self-assembly and graph subshifts.

Seminaire : Séminaire Pôle Calcul -- François Le Gall

28/01/2021 à 10h00

Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.fr

Titre : Quantum Distributed Computing
Abstract : The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of both classical distributed computing and quantum computing, I will explain a result obtained with Frédéric Magniez (PODC 2018) on quantum distributed algorithms computing the diameter of the network. I will then briefly present more recent results (STACS 2019, PODC 2019) that show a separation between the computational powers of quantum and classical distributed algorithms in other models as well. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.

Seminaire : Séminaire MOVE : Karoliina Lehtinen (LIS), Between determinism and nondeterminism, what are good-for-games automata good for?

22/01/2021 à 14h00

Luminy, Salle de réunion 5.37 TPR2 Titre : Between determinism and nondeterminism, what are good-for-games automata good for? Résumé : Nondeterminism probably makes your favourite automata model more expressive, or at least more succinct, than determinism. However, nondeterminism comes with higher algorithmic complexity. Good-for-games automata, also known as history deterministic automata, lie in between deterministic and nondeterministic models, trying to salvage some of the expressivity and succinctness of nondeterminism, without giving up on the nice algorithmic properties of deterministic automata. In this talk, I will give an overview of good-for-games automata, survey recent developments in the area for regular, pushdown and timed automata, and point to some of the hard questions that remain unanswered and some areas that remain unexplored.

Seminaire : Séminaire CaNa - répétition ouverte de la soutenance de thèse de Pacôme Perrotin

05/01/2021 à 14h00

Orateur : Pacôme Perrotin
Titre : Simulation entre modèles de calcul naturel et modularité des réseaux d'automates
Lieu : contacter par mail Nathanaël Eon pour obtenir le lien de la visioconférence.
Résumé : Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d'elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d'automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d'approcher les questions de la dynamique des réseaux d'interactions sous un nouvel angle : nous explorons son utilité en tant qu'outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l'expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d'automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d'un processus d'optimisation de réseaux d'automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.

Seminaire : Séminaire MOVE : Ismaël Jecker (IST Austria)

17/12/2020 à 10h30

Prime languages A regular language L of finite words is composite if there are regular languages L1, L2, . . . , Lt such that L is equal to the intersection of the Li, and the index (number of states in a minimal DFA) of every language Li is strictly smaller than the index of L. Otherwise, L is prime. This notion of primality was introduced by Orna Kupferman and Jonathan Mosheiff in 2015, and the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. In this talk, I will present some recent results concerning primality in some subclasses of regular languages. First, we will consider unary regular languages, namely regular languages with a singleton alphabet. A unary language can be interpreted as a set of positive integers, making the study of prime unary languages close to that of primality in number theory. We will see that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for checking primality of unary DFAs. Second, I will present our (ongoing) work on regular languages definable by permutation DFAs, namely DFAs whose transition monoid is a group. We will see that, while we cannot apply the exact same techniques used in the unary setting, they can be adapted to obtain an NP algorithm checking primality of permutation DFAs, improving the previously known PSpace algorithm.

Seminaire : Séminaire MOVE : Marie Fortin (University of Liverpool)

15/12/2020 à 10h30

Expressivity of first-order logic, star-free propositional dynamic logic and communicating automata This talk is concerned with the expressive power of first-order logic and other formalisms over different classes of ordered structures, among which MSCs (Message Sequence Charts), a standard model for executions of message-passing systems. This study is motivated by two classic problems: the k-variable property, that is, the equivalence of first-order logic and its k-variable fragment over certain classes of structures, and the study of logic-automata connections, in the spirit of Bütchi-Elgot-Trakhtenbrot theorem. Our approach relies on star-free propositional dynamic logic (star-free PDL), a variant of PDL with the same expressive power as the 3-variable fragment of first-order logic. We start by studying the expressive power of star-free PDL over linearly ordered structures with unary and binary predicates. We show that under certain monotonicity conditions, star-free PDL becomes as expressive as first-order logic. This implies that any first-order formula can then be rewritten into an equivalent formula with at most 3 variables. This result applies to various natural classes of structures, generalizing several known results and answering some open questions. We then focus on MSCs, to which this first result also applies. We use star-free PDL to address another important problem: the synthesis of communicating finite-state machines (CFMs) from first-order specifications. CFMs are a model of concurrent systems in which a fixed number of finite-state automata communicate through unbounded FIFO channels. They accept languages of MSCs. While logical characterizations of the expressive power of CFMs have been established under different restrictions (bounding the size of the communication channels, or removing the "happened-before" relation from the logic), the following question had remained open in the general case: can every first-order formula over MSCs be translated into an equivalent CFM? We prove that this is the case, using star-free PDL as an intermediate language.

Seminaire : Séminaire MOVE : Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken), On the Monniaux Problem in abstract interpretation

08/12/2020 à 14h00

On the Monniaux Problem in abstract interpretation The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program P, a safety (e.g., non-reachability) specification φ, and an abstract domain of invariants D, does there exist an inductive invariant in D guaranteeing that program P meets its specification φ. The Monniaux Problem is of course parameterised by the classes of programs and invariant domains that one considers. In this talk, I’ll present a select overview and survey of work on this problem, and discuss some recent results for semilinear invariants for unguarded affine programs. Séminaire en visio

Seminaire : Séminaire MOVE : Léo Exibard (LIS), Computability and Continuity of Data Word Functions Defined by Transducers

30/11/2020 à 14h00

Computability and Continuity of Data Word Functions Defined by Transducers Last year, Dave, Filiot, Krishna and Lhote established an equivalence between the notions of continuity and computability for functions over infinite (aka omega-) words[*]. In this talk, we extend the study to the case of an infinite alphabet, i.e. to the problem of synthesizing computable functions over data omega-words. The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic transducers equipped with registers, an extension of register automata with outputs, to specify functions. Such transducers may not define functions but more generally relations of data omega-words, and we show that it is PSpace-complete to test whether a given transducer defines a function. Then, given a function defined by some register transducer, we show that it is decidable (and again, PSpace-complete) whether such function is computable. As for the finite alphabet case, we show that computability and continuity coincide for functions defined by register transducers, and show how to decide continuity. [*] Nathan presented those results at the MoVe seminar last september, but this talk will be self-contained. Séminaire en visio zoom

Seminaire : Séminaire du pôle calcul par Catuscia Palamidessi

26/11/2020 à 10h00

Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.fr

Titre : A new mechanism for distributed Differential Privacy
Abstract : Differential Privacy (DP) is one of the most successful proposal to protect the privacy of the sensitive data while preserving their utility. In this talk, we will briefly introduce the DP framework, and then present a new proposal for a mechanism to implement DP in the distributed case, namely in a scenario in which the data collections are distributed across different organizations, which do not wish to disclose the original data but only their sanitized version, and still benefit from the advantages of combining the information coming from different sources. The mechanism we propose is particularly suitable for the application of a variant of the statistical Expectation-Maximization method, thanks to which the utility of the original data can be retrieved to an arbitrary degree of approximation, without affecting the privacy of the original data owners.

Seminaire : Séminaire MOVE : Guillaume Maurras (LIS), Caractérisation logique de langages d'ordre supérieur - introduction

23/11/2020 à 14h00

Caractérisation logique de langages d'ordre supérieur - introduction 1/ Büchi : la déterminisabilité des automates finis est l'élément clé de la réciproque 2/ Les langages algébriques : i/ les automates à Pile ne sont pas déterminisables, par contre Alur introduit les NWA (déterminisables) qui permettent un argument "à la Büchi" pour montrer que les modèles de ExistMatchMSO sont exactement les langages algébriques. ii/ conclusion : en enrichissant la structure des mots (d'un couplage) et en construisant une classe d'automates déterminisable (les NWA) on a caractériser logiquement une classe de langage (les algébriques) 3/ Les langages indexés : on voudrait appliquer (ii) on enrichit la structure de mot de 2 couplages (se répondant l'un l'autre d'une certaine façon qu'on appelle "haricot"), on a définit des automates sur ces mots enrichis et prouvés qu'ils sont déterminisables on voudrait catégoriser logiquement la partie (?) des indexés à laquelle ils correspondent. exemple : le langage uu où u est de longueur paire est un langage de "haricot" / un langage indexé Séminaire par visio zoom

Seminaire : Séminaire CaNa, Guilhem Gamard (LIS), Rice-like theorems for automata networks

10/11/2020 à 14h00

An automata network (AN for short) is a finite digraph where each node holds a state, choosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the "grid" is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of "Rice theorems", i.e., results along the lines of: "any nontrivial property of the function computed by an automata network is computationally hard to test". In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.

Seminaire : Séminaire MOVE : Louis-Marie Dando (LIS), Les automates circulaires sur les rationnels

05/11/2020 à 10h30

Les automates circulaires sur les rationnels Dans cet exposé, je vous présenterai quelques résultats obtenus durant ma thèse. Le premier est que sur les semi-anneaux rationnellement additifs (et on peut étendre aux rationnels), les automates circulaires et les expressions de Hadamard réalisent les mêmes séries. Ce résultat est constructif. Le second résultat est que l'on peut transformer un automate two-way en un automate circulaire sur Q. Lieu : salle de réunion LIS, Luminy

Seminaire : Séminaire MOVE : Charles Paperman (Université de Lille), Stackless processing of streamed trees

21/10/2020 à 14h00

Stackless processing of streamed trees In this talk I will first present the state of the art of efficiency implementation of streaming-text algorithms on modern architecture. Then some recent results on the extraction of information on streamed of structured documents without stack overhead. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy

Seminaire : Séminaire du pôle calcul par Adrien Varet

15/10/2020 à 10h00

Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.fr

Les benzénoïdes sont une sous-famille des hydrocarbures (molécules uniquement constituées d'atomes de carbone et d'hydrogène) dont les atomes de carbones forment des hexagones. Ces molécules sont beaucoup étudiées en chimie théorique. En effet, il existe un certain nombre de problèmes relatifs aux benzénoides dans différents domaines. Dans cette présentation, on se propose de se pencher sur deux problématiques en particulier, qui sont être capable de générer des structures de benzénoïdes ou calculer l'aromaticité locale d'un benzénoïde donné. Calculer l'aromaticité locale d'un benzénoïde revient à attribuer une énergie à chacun de ses hexagones qui est induite par les déplacements de ses électrons. A l'heure actuelle, la méthode la plus utilisée pour faire ce calcul (appellée NICS) requiert des calculs de chimie quantique et est extrêmenent coûteuse. Dans cette présentation, j'aborderais dans un premier temps une méthode utilisant la programmation par contraintes capable de générer l'ensemble de structures de benzénoïdes répondant à un certain nombre de de propriétés (qui peuvent être chimiques ou structurelles). Dans un second temps, je présenterais un algorithme utilisant la programmation par contraintes capable de calculer l'aromaticité locale d'un benzénoïde donné.

Seminaire : Séminaire MOVE : Benjamin Monmege (LIS), Dynamics on Games (2): Simulation-Based Techniques and Applications to Routing

08/10/2020 à 10h30

We consider multi-player games played on graphs, in which the players aim at fulfilling their own (not necessarily antagonistic) objectives. In the spirit of evolutionary game theory, we suppose that the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome w.r.t. the current strategy profile). This generates a dynamics in the game which may eventually stabilise to an equilibrium. The talk will start with a short presentation of evolutionay game theory. Then, I will present our twofold contribution. First, we aim at drawing a general framework to reason about the termination of such dynamics. In particular, we identify preorders on games (inspired from the classical notion of simulation between transitions systems, and from the notion of graph minor) which preserve termination of dynamics. Second, we show the applicability of the previously developed framework to interdomain routing problems. This is a joint work with Thomas Brihaye, Gilles Geeraerts, Marion Hallet and Bruno Quoitin. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy

Seminaire : Séminaire CaNa, Antonio E. Porreca (LIS), The semiring of dynamical systems

06/10/2020 à 14h00

We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems in terms of the category-theoretical operations of sum (disjoint union) and (tensor) product, which correspond to alternative and synchronous execution. This defines a semiring structure over the set of dynamical systems (modulo isomorphism), which allows us to express decomposition problems in terms of factorisation and polynomial equations. We analyse the algebraic properties of the semiring and prove that most dynamical systems are irreducible, and that the reducible ones sometimes admit multiple factorisation into irreducibles. We also prove that polynomial equations over this semiring are, in general, algorithmically unsolvable, and that many solvable subclasses of equations, including linear ones, are intractable even if the explicit dynamics of the systems is given as input (while in applications, where the dynamical systems are described more succinctly, these problems are conjecturally even harder). Finally, we also analyse dynamical systems in terms of their “topographic profiles”, a more abstract view in terms of the number of states at a given distance from the limit cycles of the system, which turns out to share many of the same algebraic properties.

Lien pour visionner ce séminaire : https://amupod.univ-amu.fr/video/7228-seminaire-cana-antonio-e-porreca-the-semiring-of-dynamical-systems/
Lien vers les slides : https://aeporreca.org/talks/semiring-of-dynamical-systems.pdf

Seminaire : Séminaire MOVE : Benjamin Monmege (LIS), Dynamics on Games (1): Matrix game theory vs evolutionary game theory

01/10/2020 à 10h30

Seminaire : Séminaire MOVE : Julie Parreaux (LIS), Reaching Your Goal Optimally by Playing at Random with no Memory

24/09/2020 à 10h30

Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest settings where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless ε-optimal strategy when it exists, where probabilities are parametrised by ε. We also show that for some games, no optimal randomised strategies exist. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy. This is a joint work with Benjamin Monmege and Pierre-Alain Reynier. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy

Seminaire : Séminaire MOVE : Nathan Lhote (LIS), Continuity and computability of regular functions

10/09/2020 à 10h30

Regular functions from infinite words to infinite words can be equivalently specified by MSO-transducers, streaming omega-string transducers as well as deterministic two-way transducers with look-ahead. In their one-way restriction, the latter transducers define the class of rational functions. Even though regular functions are robustly characterised by several finite-state devices, even the subclass of rational functions may contain functions which are not computable ((by a Turing machine with infinite input). This paper proposes a decision procedure for the following synthesis problem: given a regular function f (equivalently specified by one of the aforementioned transducer model), is f computable and if it is, synthesize a Turing machine computing it. For regular functions, we show that computability is equivalent to continuity, and therefore the problem boils down to deciding continuity. We establish a generic characterisation of continuity for functions preserving regular languages under inverse image (such as regular functions). We exploit this characterisation to show the decidability of continuity (and hence computability) of rational and regular functions. For rational functions, we show that this can be done in NLogSpace (it was already known to be in PTime by Prieur). In a similar fashion, we also effectively characterise uniform continuity of regular functions, and relate it to the notion of uniform computability, which offers stronger efficiency guarantees. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy

Seminaire : Séminaire du pôle calcul par Adrian Vladu "Graph Algorithms Through the Lens of Continuous Optimization"

03/07/2020 à 14h00

Recent years have witnessed a surge in the development of fast graph algorithms based on continuous optimization primitives. Classically, graph algorithms have relied on purely combinatorial techniques. However, new ideas stemming from Scientific Computing and Machine Learning set forth an emerging theme of algorithm design via continuous optimization.

I will provide a tour through some of the techniques that underlie this theme, and show how they can be used to obtain fast algorithms for solving a range of fundamental problems such as: maximum flow, minimum cost flow, or optimal transport with entropic regularization.

This talk is based on arXiv:1902.06391, arXiv:2003.04863, and arXiv:1704.02310, but will be kept self-contained, and will assume no prior background in optimization.

Seminaire : Séminaire CaNa -- Molecular computers in artificial chemistry, Marius Buliga

14/04/2020 à 14h00

Conference : Conférence MachineLearning@LIS

02/04/2020 à 09h00

À l'occasion de la conférence ML@LIS qui aura lieu le 2 Avril à St Jérôme, les chercheurs du Laboratoire d'Informatique et Systèmes feront des présentations scientifiques sur leur travaux de recherche ayant attrait aux aspects théoriques, techniques ou applicatifs du Machine Learning. L'objectif de cette conférence est double: d'abord animer la vie interne du laboratoire, faire en sorte que nous découvrions ce qui se fait dans les différentes équipes, nouer des liens et peut-être même ouvrir la porte à des collaborations si les discussions vont bon train; ensuite, donner un aperçu de ce qui se fait en Machine Learning au LIS pour les spectateurs extérieurs. Cette conférence est gratuite et ouverte sur inscription à toute personne du LIS ou de l'extérieur intéressée par le Machine Learning. Retrouvez toutes les informations sur le site de la conférence: https://mlatlis.lis-lab.fr/.

Seminaire : Séminaire MOVE : Adrien Le Coënt (ENSTA Paris, U2IS)

23/03/2020 à 10h30

Adrien Le Coënt (ENSTA Paris, U2IS) Lundi 23 mars, 10h30 Salle de réunion BU1, Luminy Guaranteed simulation and control synthesis for switched systems Switched systems constitute a sub-class of hybrid systems, and the synthesis problem for such systems is still an important issue, particularly when considering safety critical systems. Control synthesis for switched systems has been extensively studied in the past years. One of the current major approaches is symbolic methods, which basically aim at representing the continuous and infinite state-space of the system with a finite number of symbols, e.g. discrete points, sets of states, etc. This type of approaches is particularly adapted for safety critical systems, since it exhaustively ensures that an interest set is safe. However, their computational complexity is usually exponential with the dimension of the system and the fineness of the discretisation. We present some recent results and ongoing work allowing to overcome some of the flaws of the current symbolic methods, relying on guaranteed numerical schemes, abstraction methods and compositional approaches.

Seminaire : Séminaire MOVE : Matthieu Rosenfeld (LIS)

19/03/2020 à 10h30

Matthieu Rosenfeld (LIS) Jeudi 19 mars, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre: Calculer le taux de croissance dans les arbres des ensembles définissables en logique monadique du second ordre Un résultat récent de Rote montre que le nombre d'ensembles dominants minimaux dans les arbres d'ordre $n$ est au plus $95^{\frac{n}{13}}$ et que cette borne est optimale. En généralisant les idées qu'il a utilisé on peut montrer qu'on peut calculer algorithmiquement de telles bornes pour tout type d'ensemble définissable en logique monadique du second ordre. En toute généralité, l'algorithme qu'on obtient nous permet d'approximer par le haut la borne optimale. La question de savoir si on peut aussi l'approximer par le bas et donc si ce nombre est calculable reste ouverte. Cependant, en pratique, dans un certain nombre de cas intéressants on arrive a obtenir la valeur exacte (exprimée sous forme de racine d'un polynôme). La méthode utilisée consiste à calculer "le taux de croissance" du langage d'un automate d'arbre. Je commencerai dans mon exposé par m’intéresser à la même question, mais en remplaçant "arbres d'ordre n" par "chemin d'ordre n" pour illustrer certaines idées. Je m'attaquerai ensuite aux difficultés supplémentaires liés aux arbres avant de mentionner plusieurs généralisations.

Seminaire : Séminaire MOVE : Vadim Malvone (Université d'Évry)

16/03/2020 à 10h30

Vadim Malvone (Université d'Évry) Lundi 16 mars, 10h30 Salle de réunion BU1, Luminy Raisonnement stratégique en théorie des jeux La théorie des jeux en intelligence artificielle est un puissant cadre mathématique largement appliqué au cours des trois dernières décennies pour le raisonnement stratégique dans les systèmes multi-agents. Les travaux fondateurs sur cette ligne de recherche ont commencé avec des jeux à deux joueurs au tour par tour (sous des informations parfaites et imparfaites) pour vérifier l'exactitude d'un système par rapport à un environnement imprévisible. Ensuite, de gros efforts ont été consacrés à étendre ces travaux au cadre multi-agents et, en particulier, au raisonnement efficace sur les concepts de solution importants tels que l'équilibre de Nash et similaires. Des contributions révolutionnaires dans ce sens concernent l'introduction des logiques pour le raisonnement stratégique telles que la logique temporelle à temps alterné (ATL), la logique stratégique (SL) et leurs extensions. Les jeux à deux joueurs et les logiques pour le raisonnement stratégique sont aujourd'hui des domaines de recherche très actifs. Dans cet exposé, nous présenterons nos contributions dans ces deux axes de recherche.

Seminaire : Séminaire MOVE : Célia Borlido (Université de Coimbra)

05/03/2020 à 10h30

Célia Borlido (Université de Coimbra) Jeudi 5 mars, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Stone Duality and the Substitution Principle Fragments of first-order logic defining regular languages of words can be studied inductively via the so-called “Substitution Principle”. Through this principle, one is able to study logic fragments by successively adding a layer of quantifiers, which is in turn algebraically modeled by the semidirect product of suitable monoids. In this talk we will see that, by interpreting the “Substitution Principle” from the standpoint of Stone duality, one is able to extend it beyond regularity and obtain topo-algebraic counterparts for classes of languages defined by arbitrary first-order logic fragments. As in the regular setting, applying a layer of quantifiers is modeled by a semidirect product construction for suitable recognizers. Such recognizers were proposed by Gehrke, Grigorieff and Pin in 2010 as the topo-algebraic objects to handle not-necessarily regular languages, and they generalize the classical finite and profinite monoids. This is based on joint work with Czarnetzki, Gehrke and Krebs. All concepts related to Stone duality will be introduced during the talk.

Seminaire : Séminaire CaNa --Preuve du paradoxe de Banach-Tarski, Kévin Perrot

18/02/2020 à 13h30

Seminaire : Séminaire MOVE : Mathias Ramparison (Université de Luxembourg)

13/02/2020 à 10h30

Mathias Ramparison (Université de Luxembourg) Jeudi 13 février, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Updatable Parametric Timed Automata: Decidability, Algorithms, and Application to Security As cyber-physical systems become more and more complex, human debugging is not sufficient anymore to cover the huge range of possible behaviours. For costly critical systems where human lives can be endangered, formally proving the safety of a system is even more crucial. This is done by defining a formal specification for the system, and then performing the algorithmic verification that the system satisfies some formally specified properties. With this precise and exhaustive description of a system, the usual vagueness of human language is eliminated. We focus on the verification of timed concurrent systems. Timed-dependent systems are very hard to verify, especially when the exact value of timing constants remains unknown. These unknown timing constants are called parameters. We study several subclasses of a parametric extension of the well-known formalism called Timed Automata. We mainly focus on the reachability decision problem, that asks whether there exists concrete values for these parameters such that a bug state can be reached in the system. We further address for these subclasses a computation problem that is to synthesise the set of parameter values for which a state is reachable. Finally, we apply our work to the security and safety of cyber-physical systems and infrastructure: we extend with parameters a classic formalism to model attack and failure scenarios called attack-fault trees, and propose an implementation of the translation of parametric attack-fault trees to parametric timed automata. This allows us to leverage the verification techniques and tools available for the latter for the analysis of (parametric).

Seminaire : Séminaire MOVE : Maria Emilia Descotte (LaBRI, Université de Bordeaux)

16/01/2020 à 10h30

Synchronized word relations A natural approach to defining binary word relations over a finite alphabet A is through two-tape finite state automata, which can be seen as regular languages L over {1,2}xA, where (i,a) is interpreted as reading letter a from tape i. Thus, a word w of the language L denotes the pair (u_1,u_2) in A*xA* in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of Rational relations (a.k.a. non-deterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, that we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language onto {1,2}. In this way, for each regular language C over the alphabet {1,2}, one obtains a class Rel(C) of relations, such as the classes of Regular, Recognizable, or length-preserving relations, as well as (infinitely) many other classes. During the talk, we will introduce the formalism of synchronized relations along with its basic properties without assuming any previous knowledge about it. Then we will give the main ideas for the proof of several recent results on the subject. To begin, we will discuss the problem of containment for synchronized classes of relations: given C,D regular languages over the alphabet {1,2}, is Rel(C) a subset of Rel(D)? We will show a characterization in terms of C and D which gives a decidability procedure to test for class inclusion. Then we will move to the problem of deciding whether a given class of synchronized relations is closed under paradigmatic operations such as intersection, complement, etc. We will prove the decidability of these problems by giving a characterization of the classes that are indeed closed under those operations. We will finally make a link between these closure properties and classical problems within the theory of transducers. Only basic knowledge about automata theory will be required. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy

Seminaire : Séminaire CaNa -- Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model, Nicolas Schabanel

07/01/2020 à 14h00

Seminaire : Séminaire du Pôle ACS : Patrick Siarry

19/12/2019 à 14h00

salle des commissions, St. Jérôme

Seminaire : Séminaire du Pôle ACS : Michel Zasadzinski

18/12/2019 à 14h00

Salle des commissions, St. Jérôme

Seminaire : Séminaire CaNa -- Algebra, Tilings and Nivat, Etienne Moutot

04/12/2019 à 10h30

Seminaire : Séminaire MOVE : Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken)

28/11/2019 à 10h30

Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken) Jeudi 28 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Opacity of a Stochastic System : Maximisation versus Minimisation This talk explores opacity questions where an observation function provides to an external attacker a view of the states along executions and secret executions are those visiting some state from a fixed subset. Disclosure occurs when the observer can deduce from a finite observation that the execution is secret. In a probabilistic and non deterministic setting, where an internal agent can choose between actions, there are two points of view, depending on the status of this agent: the successive choices can either help the attacker trying to disclose the secret, if the system has been corrupted, or they can prevent disclosure as much as possible if these choices are part of the system design. In the former situation, corresponding to a worst case, the disclosure value is the supremum over the strategies of the probability to disclose the secret (maximisation), whereas in the latter case, the disclosure is the infimum (minimisation). I will consider both quantitative problems (comparing the optimal value with a threshold) and qualitative ones (when the threshold is zero or one) for a fixed or a finite horizon and discuss the strange asymmetry existing between maximisation and minimisation problems.

Seminaire : DALGO: Jérémie Chalopin (LIS), vendredi 22 novembre à 10h30. Schémas de compression pour les classes maximums et amples.

22/11/2019 à 10h30

Titre : Schémas de compression pour les classes maximums et amples.

Orateur: Jérémie Chalopin

Lieu : salle de réunion du LIS, Luminy (Préfabriqué)

Résumé:
Dans cet exposé, je parlerai des connections qui existent entre des questions venant de la théorie de l'apprentissage et des concepts étudiés en géométrie et en théorie métrique des graphes. Après avoir expliqué tous les mots du titre de l'exposé, je présenterai un contre-exemple issu de la géométrie qui montre que les constructions existantes de schémas de compressions pour les classes maximums sont erronées. Je présenterai ensuite une preuve de l'existence de ces schémas de compression pour les classes maximums ainsi que des pistes pour pouvoir généraliser ce résultat aux classes amples.

Travail réalisé avec V. Chepoi, S. Moran et M. K. Warmuth. https://arxiv.org/abs/1812.02099

Seminaire : Séminaire Pole ACS - Yacine Chitour: "Finite time stabilization for chains of integrators" - 21/11/2019 - 14h - St Jérôme

21/11/2019 à 14h00

Yacine Chitour: "Finite time stabilization for chains of integrators"

21 novembre 2019, 14h, St. Jérôme, Salles des commissions
Yacine Chitour, L2S-CentraleSupélec

Titre: Finite time stabilization for chains of integrators
Abstract: In this talk, I will present various technics of stabilization in finite time for perturbed and unperturbed chains of integrators. These issues arise in sliding mode control. Joint work with M Harmouche and S Laghrouche

Le séminaire pourra être suivi en visioconférence depuis la salle X133 du bâtiment X à Toulon.
https://pole-acs.lis-lab.fr/

Conference : 4ème Demi-journée Pole Calcul - Intelligence Artificielle - 21 novembre

21/11/2019 à 09h30

Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Intelligence Artificielle”, organisée le jour 21 novembre 9h30 à 12h30 dans la salle des séminaires au 2ème étage du FRUMAM de Saint Charles. Les trois intervenants confirmés sont Hans van Ditmarsch, Loria, Vincent Risch (LIS) et notre thésard Tiziano Dalmonte (LIS).

Quatrième demi-journée (“Intelligence Artificielle”) 21 Novembre

(45min each + 10 mins questions + 15 min coffe break)

9h30 -> 10h15 —Tiziano Dalmonte, LIS

Titre: Non-normal modal logics: from models to proofs

Abstract: Modal logics are applied in many different contexts, such as epistemic, deontic or temporal reasoning, and many others. In some of these contexts, the minimal normal modal logic K leads to counter-intuitive conclusions, such as the problem of logical omniscience or the problem of conflicting obligations, and gives rise to several paradoxes (Ross paradox, the paradox of gentle murder, …). For this reason, weaker modal logics -- called non-normal – are considered. Non-normal modal logics are traditionally characterised by a possible world semantics with a neighbourhood function. In this talk I present an alternative semantics which is more natural for systems lacking monotonicity. I also present some new proof systems which have 'good' properties, moreover they provide a decision procedure of optimal complexity and allow one to construct countermodels for non-valid formulas. In the final part I present some open problems.

10h25 -> 11h10 — Vincent Risch (LIS)

Titre: Consistency Measures, Inconsistency Measures, and Mix Measures (Preliminary Report)

En collaboration avec Philippe Besnard Abstract: We give some insight into a preliminary attempt at investigating a notion of consistency measures. These would provide a consistency degree for any finite collection of logical formulas, on a par with the well-known notion of inconsistency measures, that aim at assigning degrees of inconsistency to finite sets of logical formulas. We first propose a basic set of postulates for consistency measures. We look at a couple of relationships with inconsistency measures. We even lay grounds for a formal duality between these two domains. Lastly, we have a look at what would be a mix measure, that is, a measure that gives a degree, on the same scale, for consistency (positive values) and inconsistency (negative values). We also mention supermodels, as defined by Ginsberg et al., as well as a theory that can be regarded as a generalization of super-models, namely morpho-logics.

11h20 -> 11h35 Coffee break

11h35 -> 12h20 — Hans van Ditmarsch (LORIA)

Titre:Dynamic epistemic logic for distributed computing - asynchrony and concurrency

We will present some recent work on asynchrony and concurrency in dynamic epistemic logics (DEL), building on foundations in distributed computing and temporal epistemic logics. Asynchrony can be modelled by reasoning over histories of actions of different length. How to do this in DEL was proposed by [Dégremont, Löwe, Witzel: TARK 2011]. By equivalence relations on protocol-generated forests along different depths of trees, they can identify action histories of different length. More or less strongly related to DEL this was also considered for: gossip protocols [Apt, Grossi, vd Hoek, TARK 2015], logic puzzles [vD, van Eijck, Wu: KR 2010], and for the immediate snapshot algorithm in distributed computing [Goubault, Ledent, Rajsbaum: GandALF 2018]. We will present the last in some detail: Kripke models and action models can be represented as simplicial complexes. Dynamic epistemic logic can then be interpreted on such complexes. From the perspective of dynamic epistemic logic, a further departure towards distributed computing and asynchrony is to distinguish the sending and receiving of messages, such as the making versus hearing of announcements. Recent proposals are [Knight, Maubert, Schwarzentruber; MSCS 2019] and [Balbiani, vD, Fernandez Gonzalez; ArXiV 2019] (SR 2017). From the latter we will present asynchronous announcement logic. Its axiomatization resembles that of public announcement logic, and the dynamic modalities can also be eliminated. Further research is on (what is known as) concurrent common knowledge. Finally, how do we model concurrency in DEL? Both true concurrency and intersection concurrency are conceivable. We recall some older work in the area: [vD, vd Hoek, Kooi: AAMAS 2003] and [van Eijck, Sietsma, Wang: JANCL 2011]. The Muddy Children Problem is a joy forever: the action of three muddy children not stepping forward because none of them know whether they are muddy, is always modelled as the public announcement of a conjunction with three conjuncts. Should this not be a concurrent action with three components?

End: 12h30

Conference : soutenance HDR Benoit FAVRE : St Charles

15/11/2019 à 15h00

J'ai le plaisir de vous inviter à ma soutenance d'HDR, intitulée "Contextual natural language understanding", qui aura lieu à la salle des voutes à St-Charles le mardi 12 novembre à 15h.

Le jury est composé de :
- Martine Adda-Decker, DR CNRS/LIMSI, Sorbonne Nouvelle Paris 3, rapporteure
- Thierry Artières PR, Aix-Marseille Université, examinateur
- Frédéric Béchet, PR, Aix-Marseille Université, examinateur
- Guillaume Gravier, CR CNRS/IRISA Rennes, rapporteur
- Patrick Gallinari, PR LIP6 Sorbonne Université, rapporteur
- Dilek Hakkani-Tür, Amazon San Francisco, examinatrice

Seminaire : Séminaire de l'équipe I&M : "Bridging the gap between in-vivo and ex-vivo brain dissection"

15/11/2019 à 10h00

Séminaire de l'équipe I&M qui aura lieu vendredi 15/11 au TPR1 salle G 02.12 entre 10h et 12h (campus Luminy) : Paolo Avesani, University of Trento.

Titre "Bridging the gap between in-vivo and ex-vivo brain dissection"

Résumé:

The anatomy of neuroanatomical brain connections can be characterized in-vivo at the individual level from recordings of diffusion MRI. After a first a step of diffusivity model reconstruction, and a subsequent step of fiber tracking we may obtain a representation of structural brain connectivity, namely a tractogram, as a collection of millions of streamlines, where each streamline is encoded as a polyline. The task of tract dissection from a tractogram, referred also as virtual dissection in contrast to ex-vivo dissection, is concerned with the identification of those streamlines that have a specific neuroanatomical meaning. On the other hand we may investigate the brain connectivity by dissecting ex-vivo human brain using the Klinger techniques. By sculpturing the brain tissue we may expose those fibers that characterize a specific neuroanatomical bundle. Taking advantage of photogrammetric techniques it is possible to reconstruct a 3D model and to enable a comparison with the 3D model acquired using magnetic resonance. Up to now the joint analysis of ex-vivo and in-vivo brain dissection is carried out by qualitative descriptions. In this presentation we present the preliminary results in the direction of combining brain data acquired ex-vivo with photogrammetric techniques, and those acquired in-vivo with magnetic resonance.

Biographie du conférencier :

Paolo Avesani received the PhD degree from the University of Milan, Italy. He is a researcher at Bruno Kessler Foundation (FBK ) in Trento (Italy) , where he is leading the Neuroinformatics Laboratory (NILab) — a joint initiative of FBK and the Center for Mind/Brain Sciences (CIMeC), University of Trento. His current research interests include machine learning, functional neuroimaging analysis, computational methods for brain decoding and brain mapping.

Seminaire : Séminaire MOVE : Nathan Lhote (University of Warsaw)

14/11/2019 à 10h30

Séminaire MOVE : Nathan Lhote (University of Warsaw) Jeudi 14 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre : Some recent results on polyregular functions Résumé : Regular word functions are well-studied and correspond to several different formalisms: MSO-transductions, two-way transducers, one-way transducers with registers (SST), as well as several formalisms of regular expressions for transducitons. Polyregular functions were introduced last year in an article of Bojańczyk, where they are shown to be characterized by 4 different models of computation. The first one, which comes from [Milo, Suciu, Vianu '03], is an extension of two-way transducers with a bounded number of pebbles. Polyregular functions have polynomial size increase, which means in particular that they strictly subsume regular functions; however, they still retain some of the nice properties of regular functions, such as preserving regular languages by inverse image, and being closed under composition. In this talk we present polyregular functions, and two results that were obtained this year.

Conference : G-MOD : journées du GRD IG-RV (Informatique Graphique et Réalité Virtuelle)

12/11/2019 à 09h00

L’équipe G-Mod organise en partenariat avec l’Institut des Sciences du Mouvement les journées du GRD IG-RV (Informatique Graphique et Réalité Virtuelle). Ces journées JFIGRV2019 se décomposent en : - une journée jeunes chercheurs le 12 novembre à Luminy (Polytech)
- 3 jours de conférence les 13, 14 et 15 novembre au Palais des Congrès du Parc Chanot

Toutes les informations sont disponibles sur le site de la conférence : https://jfigrv2019.sciencesconf.org

Si tu penses que cette info doit être diffusée par mail, n’hésite pas

Seminaire : Séminaire MOVE : Denis Kuperberg (CNRS, LIP, ENS Lyon)

07/11/2019 à 10h30

Séminaire MOVE : Denis Kuperberg (CNRS, LIP, ENS Lyon) Jeudi 7 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre : Circular proof systems for regular expressions Résumé : Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite branches. We investigate the computational content of a cyclic proof system for Kleene algebra. If e,f are regular expressions, the sequent e -> f can be proved in the cyclic proof system if and only if L(e) is contained in L(f). Different proofs of the same sequent can be interpreted as different programs mapping each word of e to a witness that it is in f. We show that depending on the particular rules allowed in the system, the computational content of proofs matches different complexity classes. In particular, if the contraction rule is added, we obtain a rich class of languages, for which we exhibit an equivalent automaton model: Jumping Multihead automata. In presence of the cut rule, corresponding to composition of programs, we can define primitive recursive functions (without contraction) or functions from System T (with contraction). This is joint work with Laureline Pinault and Damien Pous

Rencontre : LIS PhDay 2019, St Jérôme

31/10/2019 à 09h30

Le LIS PhDay 2019, rassemblement annuel des jeunes chercheurs du LIS (doctorants, ATER, postdocs), aura lieu jeudi 31 octobre 2019, salle de conférence du bâtiment Polytech/LIS sur le site St Jérôme à Marseille. Programme prévisionnel: 9h15: accueil 9h30 : 3-4 interventions scientifiques (20-25'/pers) 11h : pause 11h15 : 3-4 interventions scientifiques (20-25'/pers) 12h30 : buffet 14h : rencontre avec anciens 15h30 : activité détente, team-building 18h: apéro en ville Inscription en 30s (aidez-nous à ajuster les quantités!) : https://forms.gle/g8uU4SknutQJh2hD7

Seminaire : Séminaire CaNa -- Quasériodes des mots biinfinis, Guilhem Gamard

29/10/2019 à 14h00

Un mot fini q est une quasipériode d’un mot infini w si et seulement si w est recouvert de copies de q, éventuellement chevauchantes. Si w admet au moins une quasipériode, on dit qu’il est quasipériodique. Cette notion est apparue dans les années 1990 dans un contexte d’algorithmique du texte, puis fut employée en combinatoire des mots, ainsi que dans l’étude des subshifts.
Un article récent (2016) donne une technique générale permettant de déterminer l’ensemble des quasipériodes d’un mot infini donné. Cette technique permet par exemple de caractériser les quasipériodes des mots sturmiens. En outre, elle permet de démontrer que les mots sturmiens standard sont les mots apériodiques possédant “le plus de quasipériodes possibles”. La première partie de cet exposé présentera ces résultats.
Malheureusement, tous ces résultats ne portent que sur les mots infinis à droite ; dans le cas des mots biinfinis, la combinatoire du problème est considérablement plus compliquée. Le cas biinfini est cependant plus naturel pour la dynamique symbolique, car le shift d’un mot biinfini quasipériodique est encore quasipériodique (ce qui n’est pas vrai sur les mots infinis à droite). Dans la deuxième partie de cet exposé, nous verrons comment généraliser les résultats précédents au cas biinfini.

Seminaire : DALGO: Arnaud Labourel (LIS), vendredi 25 octobre à 10h30. Livraison collaborative avec des agents mobiles contraints en énergie.

25/10/2019 à 10h30

Titre : Livraison collaborative avec des agents mobiles contraints en énergie.

Orateur: Arnaud Labourel

Lieu : salle de réunion du LIS, Luminy (Préfabriqué)

Résumé:
Dans cet exposé je vous parlerai du problème de livraison collaborative avec des agents mobiles. On considère un graphe pondéré (orienté ou non) dans lequel se trouve des agents mobiles initialement dispersés. L’objectif des agents est de transporter un colis d’un sommet source à un sommet destination. Chaque agent a un montant d'énergie limité lui permettant de parcourir une trajectoire de longueur au plus B. Les agents doivent donc collaborer car aucun n’a assez d’énergie pour transporter seul le colis de la source à la destination. Ce problème avait déjà été étudié mais nous ajoutons une contrainte supplémentaire qui est que les agents doivent utiliser uniquement un chemin prédéfini pour transporter le colis. Cette contrainte peut se justifier par des raisons de sécurité, en considérant qu'un seul chemin est sûr dans le réseau pour transporter le colis. Bien que cette contrainte réduise l’espace de recherche des solutions réalisables, le problème reste difficile à résoudre tout comme l’est le problème initial. Je vous montrerai des algorithmes d’approximation (pour le montant d’énergie B des agents) en temps polynomial pour les graphes orientés et non orientés, et vous donnerai une preuve de NP-dureté pour l’approximation dans le cas orienté.

Travail en collaboration avec Jérémie Chalopin, Shantanu Das, Yann Disser et Matúš Mihalák

Seminaire : Séminaire MoVe/LIRICA : Karoliina Lehtinen (Univ. Liverpool) - 24 octobre - Quasi-polynomial techniques for parity games and and other problems

24/10/2019 à 11h00

Parity games are central to the verification and synthesis of reactive systems: various model-checking, realisability and synthesis problems reduce to solving these games. Solving parity games -- that is, deciding which player has a winning strategy -- is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years. In 2017 a major breakthrough occurred: parity games are solvable in quasi-polynomial time. Since then, several seemingly very distinct quasi-polynomial algorithms have been published, and some of these ideas have been used to solve other automata-theoretic problems. In this talk, I will give an overview of these developments and the state-of-the art, with a slight automata-theoretic bias.

Lieu : Amphithéâtre Herbrand (I2M, TPR2, 1er étage), Luminy
Séminaire joint MoVe/LIRICA/LDP (I2M)
Plus d'infos sur la page du séminaire MoVe : lien

Seminaire : Séminaire ACS : Gabriel Wainer (Carleton University)

21/10/2019 à 14h00

Lieu : Sy. Jérôme, salle des commissions. Titre: Discrete Event Modeling and Simulation Methodologies : Past, Present and Future. Resumé : Modeling and Simulation methods have been used to better analyze the behavior of complex physical systems and it is now common to use simulation as a part of the scientific and technological discovery process. M&S advanced thanks to the improvements in computer technology, which, in many cases, resulted in the development of simulation software using ad-hoc techniques. Formal M&S appeared in order to try to improve the development task of very complex simulation systems. Some of these techniques proved to be successful in providing a sound base for the development of discrete-event simulation models, improving the ease of model definition and enhancing the application development tasks; reducing costs and favoring reuse. The DEVS formalism is one of these techniques, which proved to be successful in providing means for modeling while reducing development complexity and costs. DEVS model development is based on a sound theoretical framework. The independence of M&S tasks made possible to run DEVS models on different environments (personal computers, parallel computers, real-time equipment, and distributed simulators) and middleware. We will present a historical perspective of discrete-event M&S methodologies, showing different modeling techniques. We will introduce DEVS origins and general ideas, and compare it with some of these techniques. We will then show the current status of DEVS M&S, and we will discuss a technological perspective to solve current M&S problems (including real-time simulation, interoperability and model-centered development techniques). We will show some examples of the current use of DEVS, including applications in different fields. We will finally show current open topics in the area, which include advanced methods for centralized, parallel or distributed simulation, the need of real-time modeling techniques, and our view in these fields.

Seminaire : DALGO: Peter Niebert et Cédric Berenger (LIS), vendredi 27 septembre à 10h30. Ce que vos parents ont dit de ne pas faire dans un protocole sans fil

27/09/2019 à 10h30

Titre : Ce que vos parents ont dit de ne pas faire dans un protocole sans fil
Orateurs: Cédric Berenger et Peter Niebert
Lieu : salle de réunion du LIS, Luminy (Préfabriqué)
Résumé: Nous présentons deux travaux en cours dans le domaine des protocoles sans fil qui ont en commun d’exploiter des transgressions de l’usage habituel de la couche physique. Pour comprendre ces travaux, nous introduisons d’abord le côté physique de la couche MAC de Bluetooth Low Energy, puis nous montrons, démonstration à l’appui, comment certains détournements de cette couche physique ouvrent des possibilités inattendues dans la conception de protocoles sans fil.

Seminaire : 3ème Demi-journée Pole Calcul - Algorithmique et Structure Discrete - 26 septembre

26/09/2019 à 09h30

Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Algorithmique et Structure Discrete”, organisée le jour 26 Septembre 9h30 à 12h30 dans la salle des séminaires au 3ème étage du FRUMAM de Saint Charles. Les deux intervenants confirmés sont Guilherme Dias da Fonseca (MCF, LIS) et Yan Gerard (MCF, UCA).

Troisième demi-journée (“Algorithmique et Structure Discrete”) 26 Septembre

(45min each + 10 mins questions + 15 min coffe break)

9h30 -> 10h15 —PhD Student (TBC), LIS

Titre: --

10h25 -> 11h10 — Guilherme Dias da Fonseca (MCF, LIS)

Titre: Fast Algorithms for Unit Disk Graphs

Unit-disk graphs are graphs whose $n$ vertices correspond to unit disks in the plane and whose $m$ edges correspond to pairs of intersecting disks. \emph{Graph-based} algorithms receive as input solely the adjacency representation of the graph while geometric algorithms receive the coordinates of the disks. In this talk, we consider approximation algorithms to two classic hard optimization problems: maximum independent set and minimum dominating set. We are particularly interested in algorithms whose running times are close to linear in the input size, i.e. close to $O(n+m)$ for graph-based algorithms and close to $O(n)$ for geometric algorithms. We will discuss four different approaches to obtain such algorithms: greedy, local search, strip decomposition, and shifting coresets, comparing their performance for different problems and graph classes. This work is based on multiple papers co-written by the author with Celina M. H. de Figueiredo, Vinicius G. Pereira de Sá, Raphael Machado, Gautam K. Das, and Ramesh K. Jallu.

11h20 -> 11h35 Coffee break

11h35 -> 12h20 — Yan Gerard (PR, UCA)

Titre: two open problems of Digital Geometry with convex lattice sets-

A lattice set of $Z^d$ is digital convex if its real convex hull does not contain any other integer point than the ones of S. Problem 1: recognition of digital polyhedra. A n-digital polyhedron is the intersection of the lattice $Z^d$ with a polyhedron of $R^d$ with at most $n$ faces. Given $n$ and a convex lattice set $S$, we want to determine whether $S$ is a $n$-digital polyhedron. In dimension $d=2$, with $n=3$, the question is to determine whether there exists a triangle $T$ whose intersection with the lattice is $S$. Whatever the value of $n$, it is a very natural question related to polyhedral separability but it is still undetermined whether it is decidable in the cases where $d>3$ and $S$ is hollow (hollow means that the interior of its convex hull does not contain any integer point). Problem 2: Discrete Tomography We consider the problem of reconstruction of convex lattice sets (or HV-convex polyominoes) from their horizontal and vertical X-rays or projections. In other words, we know the number of points of a convex lattice set $S$ on each row and column, and we want to reconver $S$. It's not known whether it can be done in polynomial time. The usual approach to tackle the problem is based on some combinatorial objects called the switching components. We present some recent results abour their structures.

End: 12h30

Conference : Pierre Zweigenbaum - Extraction d'information dans le domaine biomédical à base de corpus et de connaissances

23/09/2019 à 14h00

Nous avons le plaisir d'accueillir Pierre Zweigenbaum (LIMSI - https://perso.limsi.fr/pz/), un des plus grands experts du TAL biomédical en France, pour un séminaire conjoint QARMA+TALEP le lundi 23/09/2019 à 14h à StCharles, dans la salle de séminaires de la FRUMAM, 2eme étage. Le titre et le résumé sont ci-dessous. Extraction d'information dans le domaine biomédical à base de corpus et de connaissances Résumé: Le séminaire sera composé de deux parties. Dans la première partie, je ferai un survol de plusieurs de nos travaux récents en TAL biomédical : extraction de symptômes et traitements dans des forums de santé, normalisation d'informations dans les certificats de décès, TAL pour la formation des médecins. Dans la deuxième partie, je me concentrerai sur un travail récent (thèse d'A Ferré) autour du plongement d'ontologie pour le liage référentiel. La tâche de normalisation d'entité consiste en la mise en correspondance automatique de mentions d'entités dans des textes avec les concepts d'un référentiel, typiquement une ontologie. Pour réaliser cette tâche en alliant corpus et connaissances a priori, nous proposons une nouvelle approche par alignement de deux types de représentations vectorielles d'entités capturant une partie de leur sens : les plongements lexicaux pour les mentions textuelles et des « plongements ontologiques » pour les concepts, conçus spécifiquement pour ce travail. L'alignement entre les deux se fait par apprentissage supervisé. Les méthodes développées ont été évaluées avec un jeu de données de référence du domaine biologique et elles représentent aujourd'hui l'état de l'art pour ce jeu de données.

Seminaire : DALGO: Fabien Dufoulon (LRI), vendredi 13 septembre à 10h30

13/09/2019 à 10h30

Titre: Overcoming Interference in the Beeping Model: Deterministic Optimal Leader Election Orateur: Fabien Dufoulon (LRI, Paris) Lieu : salle de réunion du LIS, Luminy (Préfabriqué) Résumé: Small inexpensive inter-communicating electronic devices have become widely available. Although the individual device has severely limited capabilities (e.g., basic communication, constant-size memory or limited mobility), multitudes of such weak devices communicating together are able to form low-cost, easily deployable, yet highly performant networks. Such distributed systems present significant challenges however when it comes to the design of efficient, scalable and simple algorithms. In this presentation, we will focus on such systems, composed of devices with severely limited communication capabilities - using only simple bursts of energy. These distributed systems may be modeled using the beeping model, in which nodes communicate by beeping or listening to their neighbors (according to some undirected communication graph). This model was recently introduced (Cornejo and Kuhn, 2010), raising several question about the impact of beeping communication on fundamental problems, such as leader election, vertex coloring or multi-broadcast. Focusing on the leader election problem, we present the first deterministic optimal leader election beeping algorithm, which requires nodes to have unique identifiers. We also present a randomized version of this solution, working with anonymous nodes. This randomized solution is the first optimal randomized leader election beeping algorithm.

Seminaire : Séminaire de Théorie du Contrôle de Toulon. Thibault Maillot : Utilisation d'un modèle agronomique et d'algorithme d'optimisation afin de trouver des systèmes de cultures qui permettent d'avoir des compromis entre des indicateurs de biodiversité et de

18/07/2019 à 15h00

Seminaire : Séminaire CaNa : Jeudi 11 Juillet : Nathanaël Eon : Invariance de jauge dans les automates cellulaires

11/07/2019 à 14h00

L'invariance de jauge est une symétrie fondamentale en physique, permettant la dérivation des quatre interactions fondamentales (électromagnétique, faible, forte, gravitationnelle). D'autre part, les automates cellulaires sont largement reconnus comme un modèle de calcul naturel utile à la modélisation de phénomènes physiques. Cet exposé à pour but de montrer comment ces deux théories peuvent être réunies et les perspectives que l'on peut en tirer. L'exposé présentera les résultats obtenus pendant mon alternance ainsi que mon stage de M2. Gauge-invariance is an essential symmetry in Physics as it allows for the derivation of the four fundamental interactions (namely electromagnetic, weak, strong and gravitation). From a different perspective, cellular automata are a model of natural calculus largely known for its capacity to model physical phenomena. This talks aims at uniting those two theories and see what perspectives comes from such unification. The results presented comes from a research project which encapsulate my M2 internship.

Seminaire : Séminaire CaNa : Mardi 9 Juillet : Enrico Formenti : Computational complexity of finite asynchronous cellular automata

09/07/2019 à 14h00

Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or PI^P_2-complete (universal version) for higher dimension. (article/pii/S0304397515011421)

Seminaire : Séminaire CaNa : Alan Gardin : Etude d'un exemple de dynamique causale de graphe quantique

02/07/2019 à 14h00

Titre: Etude d'un exemple de dynamique causale de graphe quantique Abstract: La présentation concerne l'étude d'une dynamique causale de graphe quantique. Il existe des résultats théoriques sur le sujet, que j'espère éclairer en présentant un exemple d'une telle dynamique. J'expliquerai notamment comment ce modèle a été construit, et quels ont été les problèmes rencontrés. Une fois cet exemple défini, je m'intéresserai aux applications potentielles de ce modèle, et plus particulièrement aux capacités de calcul. Enfin, j'aborde l'étude théorique de ce modèle d'un point de vue mathématique. Cette approche permettra éventuellement à terme de déduire certaines propriétés utiles à l'étude des capacités de calculs du modèle. Lieu : salle de réunion de bâtiment modulaire, à Luminy

Seminaire : Séminaire de Théorie du Contrôle de Toulon. Lucas Brivadis : Observateurs de Luenberger pour les systèmes linéaires en dimension infinie

26/06/2019 à 14h00

Dans cette présentation, nous nous intéressons aux observateurs de type Luenberger dans le contexte des systèmes linéaires en dimension infinie. Dans [1], les auteurs montrent, sous une hypothèse d’observabilité du sytème, que l’erreur entre l’état du système et son observateur converge faiblement vers zéro. Nous cherchons à généraliser ce résultat, puis à l’adapter au contexte des observateurs itératifs à horizon fini. Toutefois, [2] propose dans ce même contexte un cadre dans lequel la convergence forte de l’erreur est satisfaite. Nous montrons comment étendre ce résultat aux observateurs asymptotiques usuels et le comparons aux résultats de [1]. Enfin, nous illustrons nos propos par une application au design d’un observateur pour un procédé de cristallisation en batch basé sur la technologie FBRM. [1] F. Celle et al. “Synthesis of nonlinear observers: A harmonic-analysis approach”. In: Mathematical systems theory 22.1 (Dec. 1989), pp. 291–322. [2] G. Haine, “Recovering the observable part of the initial data of an infinite-dimensional linear system with skew-adjoint generator” In: Math. Control Signals Syst. (2014) 26: 435.

WorkShop : Workshop on Machine Learning and Quantum Computation

26/06/2019 à 14h00

Université d'Aix-Marseille, LIS, Marseille, France http://pageperso.lif.univ-mrs.fr/~hachem.kadri/workshopMLQC/index.html

Workshop Date: June 26, 2019

Venue: The workshop will be hosted in Marseille at FRUMAM.

Registration: free

The goal of this workshop is to bring together researchers interested in all aspects of quantum computation models and their use in machine learning. It promotes the cross-fertilizing exchange of ideas and experiences among researchers from the communities of machine learning and quantum computing interested in the foundations and applications of quantum computation models and machine learning.

Confirmed Invited Speakers

Stéphane Ayache, LIS, TBC
Luc Giffon, LIS, Deep Networks with Adaptive Nyström Approximation
Benoît Grémaud, CPT, Quantum tensor networks: from condensed matter to machine learning
Anupam Prakash, IRIF, Quantum Support Vector Machines

Organizers

Giuseppe Di Molfetta - LIS, Aix-Marseille University
Hachem Kadri - LIS, Aix-Marseille University

Seminaire : Séminaire : ligne de force "Gestion et fouille de données pour l’extraction de connaissances" du pôle SD.

17/06/2019 à 09h30

Lundi 17 juin, nous aurons le plaisir d'accueillir Adbelkader Hameurlain, professeur à l'IRIT (Toulouse) et responsable de l'équipe Pyramid (http://www.irit.fr/-Equipe-PYRAMIDE-). Ce séminaire s'inscrit dans la ligne de force Gestion et fouille de données pour l’extraction de connaissances du pôle SD. Le séminaire se déroulera dans les locaux de la FRUMAM, deuxième étage, salle des séminaires de 9h30 à 12h00. 09h30 : Accueil avec café gourmand 10h00 : Séminaire suivi de questions et de discussions Title: Data Management in the Cloud: Evolution or Crossroad? Abstract: In the landscape of database management systems, data analysis systems (OLAP) and transaction processing systems (OLTP) are separately managed. The reasons for this dichotomy are that both systems have very different functionalities, characteristics and requirements. My talk will focus on the first class of OLAP systems. The purpose of this talk is twofold: (i) to provide a synthetic state of the art concerning (large-scale) data management systems, and (ii) how can the evolution of these systems help for big data applications. In this perspective, data management based on parallel and cloud systems are overviewed and compared by relying on fundamental criterion such as Software Requirements (Data Independence, Software Reuse), High Performance, Data Availability, Fault Tolerance, Scalability and Elasticity. With respect to the state of the art, proposed systems, and qualitative and quantitative comparative studies between Parallel DBMS (PDBMS) and Big Data Management Systems (BDMS), we try to learn some lessons and point out some open issues that should be tackled to ensure the viability of the next generation of large-scale data management systems for big data applications. Key Words: Big Data Management, Data Partitioning, Data Integration, Parallel Database Systems, Cloud Data Management Systems, Query Processing and Optimization, High Performance, Scalability, Elasticity, Hadoop MapReduce, Spark, Multistore Systems.

Seminaire : 2ème Demi-journée Pole Calcul - Topologie et Géométrie du Calcul - 6 juin

06/06/2019 à 09h30

Dans le cadre du deuxième cycle des demi-journées (le détail ici) du Pole Calcul du LIS, la prochaine sera autour du thème “Géométrie et topologie du calcul”, organisée le jour 6 Juin 9h30 à 12h30 dans l’Amphi Massiani de Saint Charles. Les trois intervenants confirmés sont Alexandra Bac (LIS), Emmanuel Godard (LIS) et Clement Maria (INRIA, http://www-sop.inria.fr/members/Clement.Maria/)

Deuxième demi-journée (Géométrie et topologie du calcul) 6 Juin

(45min each + 10 mins questions + 15 min coffe break)

9h30 -> 10h15 —Emmanuel Godard, LIS

Titre: Back to the Coordinated Attack Problem

We consider the well known Coordinated Attack Problem, where two gener- als have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way mes- sages can be lost, i.e. we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simulta- neous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary con- dition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.
Joint work with Eloi Perdereau

10h25 -> 11h10 — Alexandra Bac (MCF), LIS

Titre : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques

Avec la généralisation de l’outil informatique dans tous les domaines de la société civile, la modélisaton géométrique est devenue une plaque tournante incontournable. Pour expliquer son essor, commençons peut-être par une tentative de définition :

"La modélisation géométrique, à la croisée des Mathématiques et de l’Informatique Graphique, a pour but de construire et analyser des modèles virtuels d’objets réels ou virtuels."

Différents facteurs ont contribué à élargir le statut de la modélisation géométrique pour le faire passer de discipline relativement académique à celui d’outil applicatif indispensable :

- d’une part, l’essor des modèles virtuels comme outils (la conception assistée par ordinateur est devenue un passage obligé dans tous les domaines de l’industrie et du design),

- d’autre part, celui des méthodes de télédétection (que ce soit dans le médical, physique, chimie, génétique urbanisme, archéologie, géologie, aéronautique, étude de l’univers, de la terre, du sous-sol, des environnements naturels ou marins ...),

- enfin avec la confirmation de la loi de Moore, les capacités de traitement des ordinateurs ont atteint une développement suffisant pour permettre l’application d’algorithmes jusque-là inaccessibles sur les masses de données générées par les moyens de télédétection modernes.

La topologie, quant à elle, étudiant “les propriétés invariantes sous l’effet de transformations biunivoques continues” (Riemann), est longtemps restée un domaine de recherche purement mathématique. Cependant, avec le développement de l’informatique et de la recherche informatique, cette frontière a rapidement fissuré, ouvrant le pas à l’étude algorithmique de la topologie des objets discrets. La topologie algébrique, branche de la topologie générale, vit ainsi naître son pendant numérique : la topologie algébrique algorithmique.

La présentation abordera deux grandes pôles contiguës et complémentaires :

1. la géométrie (principalement la géométrie des surfaces)

2. la topologie algorithmique (et plus particulièrement l’homologie algorithmique)

11h20 -> 11h35 Coffee break

11h35 -> 12h20 — Clement Maria, INRIA, http://www-sop.inria.fr/members/Clement.Maria/

Titre: Faster computation on simple topologies-

Resumé: The complexity of solving topological problems on surfaces often depends on the topology of the input surface. For example, deciding whether a graph can be embedded on a surface is NP-hard in general, but becomes only linear time on the size of the graph if the genus of the surface is considered constant. In this talk, we focus on a powerful topological invariant of 3-manifolds satisfying a similar property. Specifically, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariant at the fourth root of unity, using the dimension of the first homology group of the manifold as parameter. This invariant is #P-hard to compute in general. This is joint work with Jonathan Spreer.

End: 12h30

Seminaire : Séminaire CaNa : Sabrina Ouazzani : Machines de Turing à temps infini: des fondements aux applications

04/06/2019 à 14h00

Titre: Machines de Turing à temps infini: des fondements aux applications Résumé: Dans cet exposé je vous présenterai les fondements des machines de Turing à temps infini, en particulier comment calculer avec et quelques unes de leurs particularités issues de mes travaux de recherche, mais j’en présenterai aussi de nouvelles applications, notamment en analyse, sur lesquelles je travaille actuellement avec Olivier Bournez. En particulier, quels liens ces machines entretiennent-elles avec les équations différentielles ? Je conclurai en introduisant quelques questions d’ouverture.

Seminaire : Séminaire du pôle SD autour de la ligne de force "Multimodalité et Interaction"

03/06/2019 à 10h00

Le prochain séminaire du pôle SD autour de la ligne de force "Multimodalité et Interaction" aura lieu le lundi 3 juin à St Charles à l'espace Pouillon (à côté de la bibliothèque sur le campus de St Charles), de 10h à 13h00. Nous vous proposons une présentation invitée de Julia Peyre intitulée "Learning to detect visual relations in images" puis une série de présentations des travaux des équipes sur cette ligne de force. Au plaisir de vous voir le 3 juin matin, Magalie et Alexis.

Conference : Séminaire DALGO: Dariusz Dereniowski (Gdansk University of Technology, Pologne)

29/05/2019 à 10h30

Titre : A Framework for Searching in Graphs in the Presence of Errors Lieu: salle de réunion du LIS (préfabriqué) Résumé: We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh- Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p < 1/2 and a correct one with probability 1 − p). We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log n)/(1-H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r < 1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edge-queries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991]. (Joint work with S. Tiegel, P. Uznanski and D. Wolleb-Graf)

Seminaire : Séminaire Unsupervised speech representation learning using WaveNet autoencoders : Jan Chorowski

28/05/2019 à 14h00

Jan Chorowski (University of Wrocław) Title: Unsupervised speech representation learning using WaveNet autoencoders Abstract: Learning representations of data in an unsupervised way is still an open problem of machine learning. We consider representations of speech learned using autoencoders equiped with WaveNet decoders. In this way, the encoder only needs to provide the little information needed to supplement all that can be inferred by the autoregressive decoder. This allows learning a representation able to capture high level semantic content from the signal, e.g. phoneme identities, while being invariant to confounding low level details in the signal such as the underlying pitch contour or background noise. I will show how the design choices of the autoencoder, such as the bottleneck kind its hyperparameters impact the induced latent representation. I will also show applications to unsupervised acoustic unit discovery on the ZeroSpeech task. Bio: Jan Chorowski is an Associate Professor at Faculty of Mathematics and Computer Science at the University of Wrocław. He received his M.Sc. degree in electrical engineering from the Wrocław University of Technology, Poland and EE PhD from the University of Louisville, Kentucky in 2012. He has worked with several research teams, including Google Brain, Microsoft Researchand Yoshua Bengio's lab at the University of Montreal. His research interests are applications of neural networks to problems which are intuitive and easy for humans and difficult for machines, such as speech and natural language processing.

Seminaire : Séminaire Analyse et Contrôle des Systèmes : Gabriel Abba

23/05/2019 à 14h00

Titre: De la commande des robots bipèdes à celle des humanoïdes Résumé: Le but de ce séminaire est de présenter la conception et la commande de robots bipèdes. De l'analyse des modèles de ces robots et de celle de la marche, on peut déduire une commande hybride non linéaire stabilisant la marche. A partir du cas le plus simple d'un robot plan au cas des bipèdes 3D, on arrive progressivement à déterminer les conditions nécessaires pour élaborer la commande d'un robot humanoïde ainsi que de résumer les principales caractéristiques de ces robots.

Seminaire : Séminaire CaNa : 23 Mai, Sara Riva

23/05/2019 à 14h00

Title: Solving Equations on Discrete Dynamical Systems Abstract: Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of biological modeling by discrete dynamical systems (DDS). A major issue in modeling is the verification of the model against the experimental data or inducing the model under uncertainties in the data. Equipping finite discrete dynamical systems with an algebraic structure of semiring provides a suitable context for hypothesis verification on the dynamics of DDS. Indeed, hypothesis on the systems can be translated into polynomial equations over DDS. Solutions to these equations provide the validation to the initial hypothesis. Unfortunately, finding solutions to general equations over DDS is undecidable. However, many tractable cases have been highlighted. In this article, we want to push the envelop further by proposing a practical approach for such cases. We demonstrate that for many tractable equations all goes down to a "simpler'' equation. However for us, the problem is not to decide if the simple equation has a solution, but to enumerate all the solutions in order to provide an insight on the set of solutions of the original, undecidable, equations. We evaluate experimentally our approach and show that it has good scalability property.

Conference : Journée LIS-LPL-ILCB - "Corpus et Systèmes de dialogues" - 22 mai - LPL, Aix

22/05/2019 à 10h00

Le LPL, le LIS et l'ILCB organisent une journée sur la question du dialogue et des systèmes de dialogues. Cette rencontre bénéficie de la présence parmi nous de Pierre Lison (Norwegian Computing Center) dans le cadre d'un PHC Aurora ainsi que de la visite de Lina Maria Rojas Barahona (Orange Labs). Programme - 10:00 - 11:00 : Modélisation du dialogue: contrôle du dialogue et corpus multilingues (Pierre Lison) -- Pause Café -- - 11:30 - 12:30 : A glance through Conversational agents (Lina Maria Rojas Barahona) -- Repas -- - 14:00 - 15:00 : Réunion de travail autour des systèmes de dialogues et des corpus conversationnels La journée se déroulera au LPL à Aix en Provence.

Seminaire : Séminaire CaNa : 21 Mai, Filippo Miatto

21/05/2019 à 14h00

Title : Designing devices with Variational Quantum Circuits Abstract : The design of realistic quantum devices can be extremely challenging, due to the complexity of quantum interactions or to the scarcity of analytical methods in certain areas, such as non-gaussian optical interactions. My approach is to start from a network of random quantum interactions and then optimize their parameters until we obtain the desired device. This is possible with a Variational Quantum Circuit (VQC), which allows for gradient descent methods as the optimization workhorse. The advantage of this method is that the raw VQC can be composed of realistic devices and designed for full generality, which means that a) a solution consists in the explicit blueprint with all the correct parts, their connectivity and their parameters all sorted out and b) it can be applied to a variety of domains, not just quantum optical devices. I apply this method to the design of a realistic one-way quantum repeater, which includes non-gaussian quantum optical interactions and is therefore a very difficult problem to solve without clever numerical methods. A preliminary result shows that it is in principle possible to have a repeater interaction with at most a few hundred elementary optical elements, which is an extremely promising result. Our current goal is to combine our method with Reinforcement Learning techniques to design better and better raw VQCs that can achieve the same performance with fewer elements and ultimately lead to the simplest and cheapest versions of the devices that we look for.

Seminaire : Séminaire CaNa : 14 Mai, 14h : Dominic Horsman

14/05/2019 à 14h00

Title: A new logic for quantum computing Abstract: In this talk I will give an introduction to the use of the ZX calculus of observables as a new language in which to frame quantum computing. In particular, I will focus on how it acts as a high-level design and compilation language for surface codes with lattice surgery. ZX calculus diagrams allow purely diagrammatic equational reasoning, and I will show how they are especially suited to representing the structures of surface codes. Looking particularly at the operations of lattice surgery, I show how the generators of the calculus form a direct model for splitting and merging operations. This has important implications for how we think about quantum information processing, and I will discuss a few such issues here.

Seminaire : Séminaire CaNa : 6 Mai, 14h : Eurico Ruivo

06/05/2019 à 13h30

Title: Inference and of elementary cellular automata limit-graphs Abstract: Cellular automata are locally defined dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a infinite time evolution. For finite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by finite automata. Also, there are growth patterns in the evolution of such finite automata for some cellular automata rules. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classified according to the existence of a growth pattern in their finite automata and a method to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in finite-time is presented.

Seminaire : Séminaire CaNa : Silvère Gangloff: The search for a complexity notion for organised dynamical systems

30/04/2019 à 14h00

Le séminaire aura lieu à Luminy, dans la salle de réunion du bâtiment modulaire. Résumé : The neuroscientists G. Tononi, O.Sporns and G.M. Edelman proposed in 1994 a notion of complexity, that they called neural complexity, which aims at measuring the balance in a system between independance or specialisation of its parts and their integration into the whole that have organised systems such as the brain. This work has attracted recently the attention of mathematicians: in 2009, J. Buzzi and L. Zambotti defined a class of functionals called intricacies, which includes the particular case of neural complexity, and studied the maximisers of these functionals. This notion of intricacy was studied by K. Petersen and B. Wilson (2016) in the frame of symbolic dynamics, and computed a formula for some intricacy for very elementary one-dimensional subshifts of finite type. In this talk, I will expose the basic material to understand this problem and make an overview of the literature. In the end, I will try to expose some directions for research on this subject.

Seminaire : DALGO: Shantanu Das (LIS), vendredi 26 avril à 10h30

26/04/2019 à 10h30

Title: Patrolling on Dynamic Ring Networks Abstract: We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs. (Note: Joint work with Giuseppe. A. Diluna and Leszek A. Gasieniec.) Salle de réunion du LIF, Luminy (Préfabriqué)

Seminaire : Séminaire Analyse et Contrôle des Systèmes

25/04/2019 à 14h00

Séminaire de Angelo Alessandri (DIME, Università di Genova) (Toulon)

Seminaire : Séminaire CaNa : 02/04, 15h : Pedro Balbi de Oliveira

02/04/2019 à 15h00

Le séminaire de Pedro Balbi de Oliveira se déroulera le 2 avril 2019 en salle de réunion du BP5 à luminy.

Titre : "Could density determination be solved with one-dimensional binary cellular automata with asynchronous update?"

Abstract: This title reflects the question that will start to be addressed during my visit to LIS. In the talk I will discuss the background about it, and give some idea about how the problem can be tackled. In its original formulation, density determination refers to the problem of deciding, by means of a one-dimensional cellular automaton rule, which is the most frequent bit in a cyclic binary configuration. This is one of the most widely studied benchmark decision problems in the cellular automata literature. In spite of various positive and negative results already known on the problem, in its various formulations, the possibility of solving it with a rule being updated in a deterministic asynchronous fashion is still open.

Seminaire : Séminaire Analyse et Contrôle des Systèmes

28/03/2019 à 14h00

Séminaire de Hassan Hammouri (LAGEP, Lyon) St. Jérôme

Seminaire : Séminaire Analyse et Contrôle des Systèmes

21/03/2019 à 14h00

Séminaire de Frédéric Mazenc (L2S)

Seminaire : [1ère demi-journée Pole Calcul LIS] “Logique et Méthodes formels”

21/03/2019 à 09h30

Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Logique et Méthodes formels”, organisée le jour *21 Mars 9h30 à 12h30 (Luminy) dans l’Amphi 12 de Luminy.

Les demi-journées seront aussi enregistrés et on les rendra publique les vidéos sur une page dédiée ou sur une chaine youtube (lien à venir).

Les trois intervenants confirmés sont Damien Busatto-Gaston (LIS), Belaid Benhamou (LIS), Jean-Francois Raskin (ULB)

Première demi-journée (Logique et Méthodes formelles) 21 Mars

(45min each + 10 mins questions + 15 min coffe break)

9h30 -> 10h15 — Damien Busatto-Gaston (PhD) , LIS

Titre : Synthesizing robust controllers for Büchi conditions in timed systems.

Abstract :

We solve the robust controller synthesis problem in timed automata with Büchi acceptance conditions. The goal of the controller is to play according to an accepting lasso of the automaton, while resisting to timing perturbations chosen by a competing environment. The talk will introduce classical notions for studying timed automata (regions, zones, constraint graphs) and explain how these can be extended to compute strategies that are resilient to arbitrarily small perturbations. We will also introduce a way to compute the largest perturbation allowed by a given controller. Our techniques are illustrated by the regulation of a train network.

10h25 -> 11h10 — Belaid Benhamou (MCF), LIS

Titre : Programmation logique au sens ASP (Answer Set Programming) : une nouvelle sémantique capturant et étendant celle des modèles stables.

Abstract :

Plusieurs travaux ont été faits pour définir des sémantiques pour les programmes logiques normaux. La plupart de ces sémantiques sont en fait des sémantiques de points fixes. L’idée principale est le calcul de modèles canoniques du programme logique considéré, appelés modèles stables (Gelfond et al. 1988). Dans cette exposé, nous décrivons une nouvelle sémantique pour les programmes logiques normaux. Cette dernière est basée sur une notion d’extensions de formules propositionnelles classiques. Un programme logique est alors codé par un ensemble de clauses de Horn propositionnelles. On prouve que chaque formule consistante (ou programme logique) admet au moins une extension et que, pour chaque modèle stable d’un programme logique, il existe une extension de son codage logique qui l’implique. Certaines extensions (extra-extensions) ne correspondent pas à des modèles stables du programme logique, mais sont intéressantes car elles représentent ici, une extension pour la sémantique des modèles stables. Nous donnons une condition discriminante simple qui permet de reconnaître les extensions « normales » et les distinguer des extra-extensions. Basé sur cette sémantique, nous proposons une nouvelle méthode de recherche de modèles stables pour les programmes logiques. Elle a l'avantage d'utiliser un ensemble de clauses de Horn et travaille à espace constant. Elle évite ainsi, la lourdeur induite par la gestion des boucles, dont souffrent la plupart des solveurs ASP utilisant la complétion de Clark et qui ont des complexités spatiales exponentielles dans le pire des cas. De plus, l'énumération est effectuée sur un ensemble restreint de variables du programme logique. Ce qui réduit en général, la complexité temporelle de l'algorithme. En plus de la recherche de modèles stables, cette méthode pourrait générer une sorte d'extra-modèles stables exprimant ainsi l'extension portée à la sémantique des modèles stables.

11h20 -> 11h35 Coffee break

11h35 -> 12h20 — Raskin Jean-Francois, ULB

Titre : Assume Admissible Synthesis.

Abstract :

In this talk, I will show how the notion of admissibility can be used to provide an elegant solution to the synthesis problem for reactive system where the environment is not completely adversarial or when the system is composed of several components. In particular, I will introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. Contrary to previous proposals in the literature, the rule « assume admissible » defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each component.

End: 12h30

Conference : Big Data à la Russe

07/03/2019 à 00h00

Dear all, Dyni / PSD / LIS invite you to the 4th Russo-French Big Data Congress at Toulon, 7th & 8th of march 2019 : https://tinyurl.com/y64jjzkb Free entrance, welcome ! Easy access from TGV station Sincerely, Adeline Paiement & Hervé Glotin

Seminaire : CaNa : Nicolas Behr : An introduction to rule algebras and stochastic mechanics for theories of rewriting

19/02/2019 à 14h00

Reference: https://arxiv.org/abs/1807.00785 Abstract: In this talk, without assuming any particular familiarity of the audience with the relevant theory of (M-) adhesive categories, I will provide an introduction to the so-called Double-Pushout (DPO) rewriting framework. Particular emphasis will be given to a novel series of results that concerns a certain form of associativity of the notion of sequential compositions of rewriting rules. In fact, it is this associativity that (via the mathematical framework of rule algebras) permits to make contact between classical notions of manipulations of graphs in combinatorics and statistical physics on the one hand, and the category-theoretical formulation of rewriting theories on the other hand. Some explicit application examples in the field of continuous-time Markov chains based on stochastic DPO-rewriting systems will be presented, including models of dynamical random graph ensembles (such as e.g. a birth-death process on edges of finite graphs).

Seminaire : MOVE : Bruno Guillon (CRIStAL, Université de Lille)

07/02/2019 à 10h30

Titre : Finding paths in large graphs Lieu : Salle de réunion du bâtiment modulaire BP5 (en bas de la BU), Luminy Résumé : When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid this cost, while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph. I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications of DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average. This is joint work with Charles Paperman.

Seminaire : CaNa : 22 janvier 2019 à 14h : Sur les délais de communication entre systèmes numériques (microcontrôleurs), BERENGER Cédric

22/01/2019 à 14h00

Résumé : Lors de mon stage de recherche, j’avais développé un algorithme de synchronisation pour de grands réseaux sur la base d’un modèle probabiliste de délais de transmission d’un noeud à l'autre. Lors d’essais avec des systèmes réels, nous sommes tombés sur des observations inattendues qui nous obligent de repenser les modèles, mais qui ouvrent aussi des perspectives d'applications très surprenantes en transformant un défaut en un atout. Salle de réunion du bâtiment modulaire, Luminy

Seminaire : CaNa : SAT est NP-complet, la preuve !

20/12/2018 à 14h00

Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-) Salle du réunion du bâtiment modulaire, Luminy

Seminaire : DALGO: Thomas Nowak (LRI), vendredi 14 à 10h30

14/12/2018 à 10h30

Title: Approximate Agreement in Dynamic Networks Abstract: Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents' initial values. For many problems (distributed control, clock synchronization, load balancing, ...) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes. The talk is based on joint work with Bernadette Charron-Bost, Matthias Függer, and Manfred Schwarz. Nouvelle salle du conseil, RDC de l'ancienne BU (en entrant à gauche)

Seminaire : 5ème demi-journée Pole Calcul

29/11/2018 à 09h30

Dans le cadre du cycle des demi-journées du Pole Calcul du LIS et exceptionnellement aussi du mois de l’IA*, la prochaine et dernière matinée sera autour du thème “Intelligence artificiel et calcul". Les trois intervenants confirmés sont , Gilles Audemard (CRIL) et Cyril Terrioux (LIS) e Leila Amgoud (IRIT).

Seminaire : CaNa : Adiabatic methods in quantum control, CHITTARO Francesca

15/11/2018 à 10h00

Résumé : Quantum control is the branch of control theory concerned with quantum systems, that is, dynamical systems at atomic scales, that evolve according to the laws of quantum mechanics.

One fundamental issue in quantum control theory is the controllability of quantum systems, that is, whether is it possible to drive a quantum system to a desired state, by means of suitably designed control fields. To cover most theoretical and practical situations, several notion of controllability have been proposed, as, for instance, controllability in the evolution operator, pure state controllability, controllability in population and eigenstate controllability. After a brief introduction on the topic, I will expose some results on the approximate spread controllability of (closed) quantum systems, obtained by means of adiabatic techniques, and taking advantage of the presence of conical intersections between the energy eigenstates. These results have been published in [1],[2].

Adiabatic techniques can be successfully used also to study the dynamics of open quantum systems. In particular, in [3] they have been applied to find an effective description of the evolution of open, weakly coupled quantum systems, where the sub-system of interest dissipate with much slower time scales than the rest of the system.

[1] U. Boscain, F. C. Chittaro, P. Mason, M. Sigalotti Quantum Control via Adiabatic Theory and intersection of eigenvalues IEEE-TAC, (2012) 57, No. 8, 1970--1983
[2] F. C. Chittaro, P. Mason Approximate controllability via adiabatic techniques for the three-inputs controlled Schrödinger equation, SIAM J. Control Optim., (2017), 55(6), 4202–4226.

Salle du réunion du bâtiment modulaire, Luminy

Seminaire : CaNa : Exploring attractor invariance in elementary cellular automata : complexité algorithmique, Stéphanie MacLean

13/11/2018 à 14h00

We are interested in the study of the set of attractors of all 256 Elementary Cellular Automata (ECA) , i.e., one-dimensional, binary 3-neighbourhood cellular automata, dened on an n-cell lattice (n is the length of the automaton).

Recent works have studied the invariance of their attractors against dierent update schemes, and how these aect their dynamics. Specically, in [1] was introduced the notion of k-invariance: an ECA rule r is k-invariant if its set of attractors, denoted by Fr(s), remains invariant for all update schemes s having blocks of length at most k (notice that k=1 stands for sequential update schemes, while k = n is the parallel, or synchronous one). In this context, the 1-invariance was studied in [2], where 104 ECA rules showed to have this kind of invariance. In [1] and [3] the authors studied the k-invariance, for 2 < k ≤ n, for all 104 ECA rules above mentioned.

In this work, we explore another notion of attractor invariance "in between ECA rules", we say that two ECA rules u and v are attractor equivalent over a set of update schemes S, if given any s in S, Fu(s) = Fv(s). We begin our study with the 1-invariant rules, searching for equivalences between their sets of attractors, for all 4 ≤ n ≤ 14, so as to have a set of rules that are "candidates" to be attractor equivalent, since we know that if u and v are both 1-invariant ECA rules, then their sets of attractors remain invariant, but not necessarily the same, for all sequential update schemes s. Attractor equivalence gives us new insights of the dynamical behaviour of a rule (and its equivalent rules) under dierent update schemes.

Salle de réunion du bâtiment modulaire, Luminy