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