On monday, at 2pm - UPEC CMC - Room P2-131

April 15, 2019

TBA

Nathanael Fijalkow (LABRI - Université de Bordeaux)

TBA

April 1, 2019

TBA

Meghyn Bienvenu (LABRI)

TBA

March 18, 2019

TBA

Sébastien Labbé (LABRI - Université de Bordeaux)

TBA

February 11, 2019

TBA

Luc Dartois (LACL UPEC)

TBA

February 4, 2019

TBA

Sébastien Tavenas (LAMA - Université de Savoie)

TBA

January 28, 2019

Points apériodiques dans les sous-shifts de dimension 2

Anael Grandjean (LACL UPEC)

La théorie des espaces de pavages (sous-shifts) a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au coeur de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en dimension 2 :

Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ?
Comment se comportent les espaces de pavages ne possédant aucun point apériodique ?

Nous montrons qu’un espace de pavage 2D sans point apériodique a une structure très forte : il est “équivalent” (presque conjugué) à un espace de pavage 1D, et ce résultat s’applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s’appliquent aux espaces 2D sans point apériodique. La situation en dimension supérieure semble beaucoup moins claire.

Cet exposé est issu d’une collaboration avec Benjamin Hellouin de Menibus et Pascal Vanier

January 7, 2019

The Automotive Analytics Factory as a Big Data Concept

Daniel NEAGU (Daniel NEAGU)

Big data is currently the new commodity empowering Industry 4.0 towards an effective digital economy.
Current developments in data gathering using sensors and data-driven technologies connected through the Internet of Things enable automotive industry among others to join the efforts to process data into information with the aim to extract knowledge and generate intelligent actions. For example the automotive industry invests in big data systems from the car lifecycle, including product development and vehicles in the field to R&D. Consequently the
demand for effective big data processes increases, with challenges derived from both scarcity of effective tools and expertise to issues regarding data quality and model management.
This talk reviews the journey of the Advanced Automotive Analytics (AAA) team at the University of Bradford, with details and examples of recent and current contributions. The team’s vision of the Automotive Analytics Factory as the emerging model for an integration of data, models and tools applied to
the vehicle lifecycle is introduced with references to AAA research projects, publications and events.

December 3, 2018

Descriptive distributed complexity

Fabian Reiter (IRIF)

This talk connects two classical areas of theoretical computer science:
descriptive complexity and distributed computing. The former is a branch of
computational complexity theory that characterizes complexity classes in terms
of equivalent logical formalisms. The latter studies algorithms that run in
networks of interconnected processors.

Although an active field of research since the late 1970s, distributed computing
is still lacking the analogue of a complexity theory. One reason for this may be
the large number of distinct models of distributed computation, which make it
rather difficult to develop a unified formal framework. In my talk, I will
outline how the descriptive approach, i.e., connections to logic, could be
helpful in this regard.

November 26, 2018

Algorithmique polynomiale sans mémoire

Bruno Grenet (LIRMM - Université de Montpellier)

Le calcul formel s’intéresse à l’algorithmique des objets mathématiques exacts, en particulier des polynômes et des matrices. Depuis les années 1960, de nombreux algorithmes ont été proposés pour atteindre des complexités temporelles quasi-optimales (quasi-linéaires en la taille des entrées et des sorties) pour manipuler des polynômes. Dans ce travail, nous nous intéressons à obtenir des versions efficaces en mémoire de ces algorithmes, c’est-à-dire des algorithmes qui n’utilisent qu’une mémoire constante en plus des registres d’entrée et de sortie.

Nous développons pour ce faire des méthodes génériques de réduction qui permettent de transformer n’importe quel algorithme pour une tâche donnée en un algorithme de même complexité temporelle asymptotique, et de complexité spatiale améliorée, dans la veine des réductions pour la complexité à grain fin. Dans l’exposé, nous nous concentrerons sur les problèmes basiques autour de la multiplication de polynômes et évoquerons brièvement les extensions à d’autres problèmes comme la division euclidienne ou l’interpolation.

Travail en cours, en commun avec Pascal Giorgi et Daniel S. Roche.

November 19, 2018

Trace Metrics for Nondeterministic Probabilistic Processes

Valentina Castiglioni (LIX - Ecole Polytechnique)

When probabilistic aspects of process behavior are taken into account, reason-
ing in terms of behavioral equivalences is only partially satisfactory: any tiny
variation in the values of the probabilities, which may be also due to a measure-
ment errors or approximations, will break process equivalence without giving
any further information on the differences in their behaviors. For this reason,
behavioral metrics have been proposed. The idea is to define, for each semantics,
a proper notion of distance on processes allowing us to quantify the differences
in the behavior of processes with respect to that particular semantics.

However, the interplay of nondeterminism and probability, typical of prob-
abilistic automata, leads to several possible expressions for process behavior,
thus making the definition of a proper metric subject to interpretations.

In this talk, we will discuss this issue by considering linear properties only.
In detail, we will present three main approaches to probabilistic trace seman-
tics: the trace distributions, the trace-by-trace and the supremal probabilities
approaches. For each of them we will propose a notion of trace metric, mea-
suring the disparities in the linear behavior of processes, and we will compare
these metrics with respect to their properties and their distinguishing power.