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.

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.

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

01/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 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.

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:

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.

Soutenance de Thèse : Thesis defense of Qi WANG on 14 February 14 h in St Charles

14/02/2020 à 14h00

Title: Multivariate group analyses for functional neuroimaging: conceptual and experimental advances


  • ACHARD Sophie (Directeur de Recherche, Grenoble, LJK) Rapporteur
  • HABRARD Amaury (Professeur, Université de St Etienne, LHC) Rapporteur
  • BONASTRE Jean-François (Professeur, Université d’Avignon, LIA) Examinateur
  • KADRI Hachem Associate (Professeur, Aix-Marseille Université, LIS) Examinateur
  • ARTIÈRES Thierry (Professeur, Ecole Centrale de Marseille, LIS) Directeur de thèse
  • TAKERKART Sylvain (Ingénieur de Recherche, CNRS, INT) Co-directeur de thèse


In functional neuroimaging experiments, participants perform a set of tasks while their brain activity is recorded, e.g. with electroencephalography (EEG), magnetoencephalography (MEG) or functional magnetic resonance imaging (fMRI). Analysing data from a group of participants, which is often denoted as group-level analysis, aims at identifying traits in the data that relate with the tasks performed by the participant and that are invariant within the population. This allows understanding the functional organization of the brain in healthy subjects and its dysfunctions in pathological populations. While group-level analyses for classical univariate statistical inference schemes, such as the general linear model, have been heavily studied, there are still many open questions for group-level strategies based on multivariate machine learning methods. This thesis therefore focuses on multivariate group-level analysis of functional neuroimaging. We proposed a classifier-based multivariate group-level framework which we denote as inter-subject pattern analysis, We first performed a comparison of the results provided by inter-subject pattern analysis and the standard multivariate group-level strategy. Inter-subject analysis both offers a greater ability to detect regions of small effect size and facilitates the interpretation of the obtained results at a comparable computational cost. In this context, our second contribution is introducing an unifying formalization of inter-subject pattern analysis, that we cast as a multi-source transductive transfer learning problem, and then providing a survey of the methods where inter-subject pattern analysis was used in task-based functional neuroimaging experiments. Then we performed an experimental study that examines the well-foundedness of our multi-source transductive transfer formalization of intersubject pattern analysis. The fourth contribution of this thesis is a new multivariate group-level analysis method for functional neuroimaging datasets. Our method is based on optimal transport, which leverages the geometrical properties of multivariate brain patterns to overcome inter-individual differences impacting the traditional group-level analyses.

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 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

Soutenance de Thèse : Soutenance thèse Damien Busatto-Gaston

03/12/2019 à 14h00

Titre : Synthèse symbolique de contrôleurs pour systèmes temporisés: robustesse et optimalité Amphithéâtre Sciences Naturelles du site St Charles

Soutenance de Thèse : Soutenance de thèse Agus Budi Raharjo

02/12/2019 à 14h00

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.

Soutenance de Thèse : Soutenance de thèse de Didier Villevalois

26/11/2019 à 14h00

  • Date et heure: Mardi 26 Novembre 2019 à 14h00
  • Lieu: Amphi Massiani, St Charles
  • Titre: Simplification de transducteurs en utilisant la séquentialité
  • Encadrant: Pierre-Alain Reynier
  • Résumé

    La synthèse est un domaine de l'informatique consistant à générer des programmes à partir de spécifications abstraites. Les spécifications sont souvent décrites à l'aide d'un formalisme logique et les programmes sont obtenus sous la forme de modèles de transformation. Alors qu'il est utile de pouvoir exprimer les propriétés des spécifications avec du non-déterminisme, nous souhaitons en général obtenir des modèles déterministes pour des raisons évidentes d'efficacité. Ceci nous amène à vouloir simplifier les modèles synthétisés afin d'optimiser leur évaluation ou leur représentation concrète dans un programme.
    Dans cette thèse, les modèles de transformations qui nous intéressent sont exprimés par des Streaming String Transducers (SSTs). Un SST est un automate fini déterministe équipé d'un nombre fini de registres qui peuvent être utilisés pour élaborer un mot de sortie. Ces registres peuvent être mis à jour en utilisant la concatenation de registres ou en les préfixant ou suffixant par des mots finis. Nous sommes intéressés par le problème ambitieux de la minimisation de registres, qui consiste, étant donné un SST, à calculer un SST équivalent avec un nombre minimal de registres. Comme première étape à la prise en compte de ce modèle très expressif, nous contraignons la manière dont les registres sont manipulés: ils ne peuvent pas être concaténés les uns aux autres (cette classe est appelée Concatenation-Free SST).
    Nous présentons deux contributions principales. Tout d'abord, nous élaborons une procédure permettant de minimiser le nombre de registres dans la classe des Copyless Appending SSTs (dans cette classe, les registres ne peuvent qu'être suffixés par un mot). Ensuite, nous montrons, étant donné un Copyful Concatenation-Free SST, comment décider s'il existe un Concatenation-Free SST équivalent à un seul registre.
    Lorsque l'on considère la simplification des Finite-State Transducers (FST), un problème classique est le problème de la séquentialité [Cho77], qui demande si un FST donné admet un FST séquentiel équivalent. Pour nos deux résultats, les techniques de preuves utilisées généralisent le cadre créé autour du problème de séquentialité.


    • Olivier CARTON (IRIF, CNRS, Université Paris-Diderot), Rapporteur
    • Anca MUSCHOLL (LaBRI, CNRS, Université de Bordeaux), Rapporteure
    • Christof LÖDING (RWTH Aachen University), Examinateur
    • Benjamin MONMEGE (LIS, CNRS, Aix-Marseille Université), Examinateur
    • Jean-Éric PIN (IRIF, CNRS, Université Paris-Diderot), Examinateur
    • Pierre-Alain REYNIER (LIS, CNRS, Aix-Marseille Université), Directeur

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é)

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.

Rencontre : Saison indécidabilité et impossibilité

21/11/2019 à 14h00

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

Le programme est disponible sur la page des séminaires de l'équipe MoVe : ICI.

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 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.

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"


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 :

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

Soutenance de Thèse : Soutenance de thèse de Sébastien RATEL

08/11/2019 à 14h00

  • Date et heure: Vendredi 8 Novembre 2019 à 14h00
  • Lieu: Salle de séminaire du 2ème étage de la Frumam, St Charles
  • Titre: "Densité, VC-dimension et étiquetages de graphes"
  • Encadrants: Victor CHEPOI et Arnaud LABOUREL
  • Résumé

    Un schéma d'étiquetage est un procédé permettant de distribuer la représentation d'un graphe sur ses sommets. Il consiste en une fonction d'encodage qui attribue des étiquettes binaires (courtes) à chaque sommet, et en une fonction de décodage qui, étant données les informations locales contenues dans deux étiquettes, et sans connaissance supplémentaire sur le graphe, permet de répondre (rapidement) à un type de requête pré-établi. Une partie des résultats de cette thèse sont initialement motivés par la construction de telles représentations distribuées. Ce document traite cependant de problèmes d'intérêt plus généraux tels que l'étude de bornes sur la densité de graphes, de la VC-dimension de familles d'ensembles, ou de propriétés métriques et structurelles.
    Nous établissons dans un premier temps des bornes supérieures sur la densité des sous-graphes de produits cartésien de graphes, puis des sous-graphes de demi-cubes. Pour ce faire, nous définissons des extensions du paramètre classique de VC-dimension (utilisé par Haussler, Littlestone et Warmuth en 1994 pour majorer la densité des sous-graphes d'hypercubes). De ces bornes sur la densité, nous déduisons des bornes supérieures sur la longueur des étiquettes attribuées par un schéma d'adjacence à ces familles de graphes.
    Dans un second temps, nous nous intéressons à des schémas de distance et de routage pour deux familles importantes de la théorie métrique des graphes: les graphes médians et les graphes pontés. Nous montrons que la famille des graphes médians, sans cube, avec n sommets, admet des schémas de distance et de routage utilisant tous deux des étiquettes de O(log^3 n). Ces étiquettes sont décodées en temps constant pour retourner, respectivement, la distance exacte entre deux sommets, ou le port vers un sommet rapprochant (strictement) une source d'une destination. Nous décrivons ensuite un schéma de distances 4-approchées pour la famille des graphes pontés, sans $K_4$, avec $n$ sommets, utilisant des étiquettes de O(log^3 n) bits. Ces dernières peuvent être décodées en temps constant pour obtenir une valeur entre la distance exacte et quatre fois celle-ci.


    • Nicolas NISSE, I3S/INRIA, Rapporteur
    • Laurent VIENNOT, IRIF/INRIA, Rapporteur
    • Olivier BOUSQUET, Google AI, Examinateur
    • Nadia CREIGNOU, LIS, Examinatrice
    • Cyril GAVOILLE, LaBRI, Examinateur
    • Nabil MUSTAFA, ESIEE, Examinateur
    • Victor CHEPOI, LIS, Directeur
    • Arnaud LABOUREL, LIS, Directeur

Soutenance de Thèse : soutenance thèse Riikka HUUSARI

07/11/2019 à 14h00

Dear all,

I'm glad to invite you all to my thesis defence 7th November, 14h, in St Charles, la salle des Voutes, as well as to the small celebration afterwards.

The jury is composed of:

Juho Rousu (Prof, Aalto University) : rapporteur
Amaury Habrard (Prof, Université de Saint-Etienne) : rapporteur
Alain Rakotomamonjy (Prof, Université de Rouen) : examinateur
Massih-Reza Amini (Prof, Université Grenoble Alpes) : examinateur
Liva Ralaivola (Université d'Aix-Marseille) : examinateur
Cecile Capponi (Université d'Aix-Marseille) : supervisor
Hachem Kadri (Université d'Aix-Marseille) : supervisor

Title: Kernel learning for structured data: A study on learning operator- and scalar-valued kernels for multi-view and multi-task learning problems


The current era of enthusiastic data gathering has made datasets with non-standard structures more common. This includes the already well-known multi-task framework where each data sample is associated with multiple output labels, as well as the multi-view learning paradigm, in which each data sample can be seen to contain numerous possibly heterogeneous descriptions. To obtain a good performance in tasks like these, it is important to model the interactions present in the views or output variables well.

Kernel methods offer a justified and elegant way to solve many machine learning problems. Operator-valued kernels, which generalize the well-known scalar-valued kernels, have been under attention recently as a way to learn vector-valued functions. For both scalar- and operator-valued kernel methods the choice of a good kernel function suitable for the data plays crucial role for the success on the learning task, and a natural question to ask is: is it possible to automate the process of choosing the kernel? Kernel learning tries to answer this question by treating it as a machine learning problem.

This thesis offers kernel learning as a solution for various machine learning problems. The problems range from supervised to unsupervised, yet the data is always described under multiple views or has multiple output variables. In both of these cases it is important to model the interactions present in order to obtain good learning results. Chapters two and three investigate learning the interactions with multi-view data. In the first of these, the focus is in supervised inductive learning and the interactions are modelled with operator-valued kernels. These kernels are learnable, adapting to the data at hand in the learning stage. We give a generalization bound for the algorithm developed to jointly learn this kernel and predictive function, and illustrate its performance experimentally.Chapter three tackles multi-view data and kernel learning in unsupervised context and proposes a scalar-valued kernel learning method for completing missing data in kernel matrices of a multi-view problem. In the last chapter we turn from multi-view to multi-output learning, and return to the supervised inductive learning paradigm. We propose a method for learning inseparable operator-valued kernels that model interactions between inputs and multiple output variables. We also provide insight to current state of operator-valued kernel learning and introduce a general framework to study them.

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!) :

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é)

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 -, 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 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. (

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

Workshop on Machine Learning and Quantum Computation

Université d'Aix-Marseille, LIS, Marseille, France

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
  • 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 ( 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,
    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,

    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.

    Soutenance de Thèse : Soutenance de thèse : "Recommandation automatique, temps réel, et adaptative d'emojis" - G. Guibon, St Jérôme

    24/05/2019 à 14h00

    Depuis leur apparition en 1999, les emojis ont une popularité grandissante dans les systèmes de communication. Ces petites images pouvant représenter une idée, un concept ou une émotion, se retrouvent disponibles aux utilisateurs dans de nombreux contextes logiciels : messagerie instantanée, courriel, forums et autres réseaux sociaux en tout genre. Leur usage, en hausse constante, a entraîné l'apparition récurrente de nouveaux emojis, allant jusqu'à 2 789 emojis standardisés en fin d'année 2018. Le parcours de bibliothèques d'emojis ou l'utilisation de moteur de recherche intégré n'est plus suffisant pour permettre à l'utilisateur de maximiser leur utilisation ; une recommandation d'emojis adaptée est nécessaire. Pour cela nous présentons nous travaux de recherche axés sur le thème de la recommandation d'emojis. Ces travaux ont pour objectifs de créer un système de recommandation automatique d'emojis adapté à un contexte conversationnel informel et privé. Ce système doit améliorer l'expérience utilisateur et la qualité de la communication, en plus de pouvoir prendre en compte d'éventuels nouveaux emojis créés. Dans le cadre de cette thèse, nous contribuons tout d'abord en montrant les limites d'usage réel d'une prédiction d'emojis ainsi que la nécessité de prédire des notions plus générales. Nous vérifions également si l'usage réel des emojis représentant une expression faciale d'émotion correspond à l'existant théorique. Enfin, nous abordons les pistes d'évaluation d'un tel système par l'insuffisance des métriques, et l'importance d'une interface utilisateur dédiée. Pour ce faire, nous utilisons une approche orientée apprentissage automatique à la fois supervisée et non supervisée, ainsi que la conception de modèles de langues ou, plus précisément, de plongements lexicaux. Plusieurs composantes de ce travail ont donné lieu à des publications nationales et internationales, dont le prix du meilleur logiciel reproductible, ainsi que celui du meilleur poster pour la catégorie des médias sociaux. La soutenance sera présentée devant un jury composé de : Chloé CLAVEL, rapportrice - Télécom ParisTech Horacio SAGGION, rapporteur - Universitat Pompeu Fabra Béatrice DAILLE, examinatrice - LS2N-CNRS, Université de Nantes Frédéric LANDRAGIN, examinateur - LaTTiCe-CNRS, ENS Pierre LISON, examinateur - Norsk Regnesentral, Norwegian Computing Center Patrice BELLOT, directeur - LIS-CNRS, Aix-Marseille Université Magalie OCHS, co-directrice - LIS-CNRS, Aix-Marseille Université

    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 con gurations. 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 : 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: 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).

    Soutenance d'HDR : BAC Alexandra : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques

    07/02/2019 à 14h00

    Mme BAC Alexandra soutiendra son HDR sur le thème : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques, dans l'Amphi A du bâtiment Polytech sur le campus de Luminy.

    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

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

    00/00/0000 à 00h00

    Gabriel Abba 23 Mai 2019