Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

21 juin 2021

Jerboa, un modeleur géométrique à base de règles de transformation de graphes.

Agnes Arnould (XLIM, Poitiers)

Les objets géométriques structurés sont classiquement réprésentés par le graphe de leur structure topologique (sommets, arrêtes, faces…). Les opérations de modélisation géométrique peuvent alors être définies comme des règles de transformation de graphe. Ce langage formel permet d’établir des propriétés qui garantissent la préservation de la cohérence des objets géométriques construits. Il est à la base de la plate-forme Jerboa qui comprend :

  • un éditeur qui vérifie inter-activement les propriétés et guide ainsi son utilisation,
  • un générateur de noyaux de modeleurs qui est générique en dimension et dans la nature des informations géométriques et physiques (couleur, matériaux…),
  • une interface paramétrable qui permet de construire inter-activement et visualiser des objets géométriques.

Les premières applications de Jerboa ont permis de développer des modeleurs dans les domaines de la reconstruction du sous-sol géologique, la simulation physique, la modélisation procédurale de cathédrales, etc.

14 juin 2021

À propos des réseaux d’automates booléens

Sylvain Séné (laboratoire d’Informatique et Systèmes, Aix-Marseille)

Les réseaux d’automates booléens constituent un modèle mathématique dans lequel des entités (les automates) à états booléens interagissent les unes avec les autres au cours du temps (discret). C’est un modèle qui est apparu au moment où l’informatique moderne est née. Il a été introduit sous une forme spécifique dans les années 1940 par McCulloch et Pitts avec leur travail sur les réseaux de neurones formels. Il a par la suite été largement développé en suivant plusieurs lignes d’intérêt, avec entre autres les modèles de calcul, les systèmes dynamiques et la modélisation des réseaux biologiques.

Dans ce séminaire, nous évoquerons les réseaux d’automates booléens sous un angle plutôt théorique, en laissant de côté les liens qu’ils entretiennent avec la biologie. Plus précisément, nous parlerons de certaines des lois générales historiques connues à leur sujet, avant de présenter quelques résultats plus récents relatifs à leurs ensembles limites et d’ouvrir la discussion sur leur sensibilité structurelle.

17 mai 2021

A Hennessy-Milner Theorem for ATL with Imperfect Information

Catalin Dima (LACL)

We show that a history-based variant of alternating bisimulation under imperfect information is related to a variant of ATL with imperfect information by a Hennessy-Milner theorem. The variant of ATL we consider has a “common knowledge” semantics, which requires that the uniform strategy available for a coalition to accomplish some goal must be common knowledge inside the coalition. The proof utilizes a bisimulation game between two coalitions, each composed of two agents, for which we provide a Gale-Stewart determinacy theorem. We notice that other semantic variants of ATL with imperfect information do not accomodate a reverse Hennessy-Milner theorem. We also show that the existence of a history-based alternating bisimulation between two finite Concurrent Game Structures with imperfect information (iCGS) is undecidable.

Joint work with Francesco Belardinelli, Vadim Malvone and Ferucio Tiplea

10 mai 2021

Size-varying reversible causal graph dynamics

Amélia Durbec (LIS, Aix Marseille University)

Consider a network that evolves reversibly, according to nearest neighbours interactions. Can its dynamics create/destroy nodes?
On the one hand, since the nodes are the principal carriers of information, it seems that they cannot be destroyed without jeopardising bijectivity. On the other hand, there are plenty of global functions from graphs to graphs that are non-vertex-preserving and bijective. The question has been answered negatively—in three different ways. Yet, in this paper we do obtain reversible local node creation/destruction—in three relaxed settings, whose equivalence we prove for robustness. We motivate our work both by theoretical computer science considerations (reversiblecomputing, cellular automata extensions) and theoretical physics concerns (basic formalisms towards discrete quantum gravity).

12 avril 2021

Milner et Alur entrent dans un bar

Daniele Varacca (LACL)

Alternating bisimulation for Alternating transition systems has been defined by Alur et al. It bears some ressemblence to the well known concept devised by Milner and Park for classical transition systems. The first aim of this work is to make the connection more formal: how can we make them look more similar to each other? Milner’s bisimulation is also a sound (and often complete) proof technique for contextual equivalences. What does “contextual equivalence” mean for alternanting transition systems, when there is no syntax, and therefore no notion of context? We propose an answer to this question, and we show that our version of alternating bisimulation is sound and complete for this generalised notion of contextual equivalence.
This is joint work with Romain Demangeon (LIP6) and Catalin Dima (LACL)

15 mars 2021

Left and Right Kan Extensions in Cellular Automata

Luidnel Maignan (LACL)

Paraphrasing the famous book of Saunders Mac Lane: “Everything is a Kan Extension”. However, depending on ones background of course, there might not be many examples that arise directly as Kan Extensions. In this talk, we show how the latter describes very naturally local to global definitions, as is the case for cellular automata for instance. Indeed the formal definition simply says “you have a local transformation and a way to compare arbitrary transformations? So simply choose the best global transformation possible!”.
This is based on my works with Antoine Spicher and Alexandre Fernandez on so-called “Global Transformations”

8 mars 2021

Computability, universality and quantum automata

Pablo Arrighi (LRI - University of Paris-Saclay )

I will draw a distinction between finite-dimensional quantum evolutions (“automata“) and infinite-dimensional evolutions (“operators”), and then explore their consequences upon two well-established concepts in Computer Science : computability and universality. Most of the results I will mention will rely on a decomposition of quantum operators, into quantum cellular automata—which is based upon the tacit assumption of a fixed partial order. Time-allowing, I will try to touch on the topical question of quantum partial orders.