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

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.

November 12, 2018

Enumerating pattern matches in texts and trees

Antoine Amarilli (Télécom ParisTech)

We study the data management task of extracting structured
information from unstructured documents, e.g., raw text or HTML pages.
We use the framework of document spanners, where the pattern to extract
is specified declaratively by the user (as a regular expression with
capture variables) and is translated to an automaton that then is
evaluated on the document to compute the pattern matches. We focus on
the last step of this pipeline: our goal is to efficiently find the
matches of the automaton on the document, even when there can be many of
them. We do this by proposing an enumeration algorithm, which first
preprocesses the automaton and document, and then enumerates all matches
with a small delay between consecutive matches. Unlike previous work,
our algorithm achieves the best possible bounds in the input document
(namely, linear preprocessing and constant delay), while remaining
tractable in the automaton. The guiding principle of the algorithm is to
compute a factorized representation of all matches as a product of the
automaton and document, and design efficient indexes based on the
structure of this representation. We also present our ongoing follow-up
work, e.g., how to extend our algorithm to the case of tree-shaped
documents by efficiently enumerating the matches of tree automata, how
to efficiently update the enumeration results when the input document
changes, and other open research directions.

October 15, 2018

Modélisation et utilisation de ressources et services Web et indexation de données dans un contexte d’incertitude.

Asma Omri (LIRIS - UCBL)

Il est communément admis que la production de données connait, depuis plusieurs années, un développement spectaculaire en raison de la multiplication des nouvelles technologies telles que les réseaux sociaux, les nouveaux appareils mobiles, les compteurs intelligents, les capteurs et le cloud computing. De fait, cette explosion de données devrait se poursuivre et même accélérer. S’interroger sur la façon dont on devrait traiter cette masse de qui devient de plus en plus variée, complexe et moins structurée, est alors essentiel. DaaS ( Data As A Service) peut être définie comme l’approvisionnement, la gestion et la fourniture de données présentées dans un format immédiatement consommable aux utilisateurs professionnels des organisations en tant que service. Les données retournées par ces services se caractérisent généralement par l’incertitude et l’hétérogénéité.
Nombreux sont les approches qui traitent les données selon le cycle de vie du service Web qui repose sur 6 phases à savoir la création, la sélection, la découverte, la modélisation, l’invocation et la composition des services, dans le but de résoudre le problème de volume de données, de son hétérogénéité ou de sa vitesse d’évolution. En revanche, il y a très peu d’approches qui s’intéressent à la qualité de données et au traitement de son incertitude dans le Web.
Nous nous sommes naturellement intéressés, dans cette thèse, à la question des services Web dans un contexte de systèmes distribués et hétérogènes. La principale contribution à apporter dans le cadre de ce travail de recherche est d’étudier la composition de services et/ou de ressources Web et l’indexation de données dans un contexte incertain.
Dans un premier temps, au travers des apports de la littérature, le cadre théorique relatif aux spécificités du concept de service DaaS incertain, est présenté en adoptant la théorie possibiliste. Le problème de la composition de services Web et l’impact de l’incertitude, qui peut être associée à la sortie d’un service, sur les processus de sélection et de composition des services sont explicités. Pour ce faire, nous avons proposé une approche possibiliste afin de modéliser l’incertitude des données renvoyées par des services incertains. Plus précisément, nous avons étendu les normes de description de service Web (par exemple, WSDL) pour représenter les degrés d’incertitude des sorties. Nous avons également étendu le processus d’invocation de service pour prendre en compte l’incertitude des données d’entrée. Cette extension est basée sur la théorie des mondes possibles utilisée dans les bases de données possibilistes. Nous avons également mis en avant un ensemble d’opérateurs de composition, sensibles aux valeurs d’incertitude, dans le but d’orchestrer des services de données incertains.
Dans un deuxième temps, nous avons étudié l’impact de l’incertitude sur la représentation et la manipulation des ressources Web. Nous avons défini le concept de ressource Web incertaine et proposé des mécanismes de composition de ressources. Pour ce faire, un modèle de description de l’incertitude à travers le concept de ressource Web incertaine a été présenté. Celui-ci est basé sur un modèle probabiliste où chaque ressource peut avoir plusieurs représentations possibles, avec une certaine probabilité.
Enfin, et dans un dernier temps, nous avons proposé des méthodes d’indexation documentaire des données de type Big Data. Au commencement, nous avons adopté une approche d’indexation syntaxique de données incertaines, ensuite, nous avons suivi une méthode d’indexation sémantique incertaine. Enfin, et pour booster cette démarche, nous avons proposé une méthode hybride d’indexation dans un contexte incertain.

October 8, 2018

Modèle géométriques de programmes concurrents conservatifs

Emmanuel Haucourt (LIX - Ecole Polytechnique)

Un programme concurrent est constitué de plusieurs processus
séquentiels qui s'exécutent simultanément et partagent des ressources.
Pour un processus séquentiel standard, le graphe de flot de contrôle
(GFC) est une sur-approximation classique (et omniprésente dans les
compilateurs et analyseurs statiques) de l'ensemble des traces
d'exécutions du programme. La propriété cruciale du graphe de flot de
contrôle est sa finitude. Définir l'équivalent de cette structure pour
les programmes concurrents n'a rien d'évident. La solution que l'on
propose est basée sur la notion d'espace partiellement ordonné. À chaque
GFC on associe sa réalisation géométrique dirigée, qui consiste à
remplacer chaque flèche du GFC par une copie du segment unité [0,1]
joignant la source de la flèche à son but. Un programme parallèle
constitué des processus séquentiels P_1,...,P_n sera alors représenté
par un sous-espace du produit cartésien E = G_1 x ... x G_n où G_i est
la réalisation du GFC's du i-ème processus. En effet, sous l'hypothèse
que le programme considéré est conservatif, on peut définir une fonction
de potentiel qui associe à chaque point de E la quantité de ressources
nécessaire au fonctionnement du programme en ce point. Si cette quantité
dépasse la quantité de ressources disponible, alors le point est
«interdit». L'ensemble des points interdits forme une sous partie de E
dont le complémentaire M est le modèle géométrique du programme. 
On a les résultats suivants:
1) les chemins (continus) dirigés sur M forment une sur-approximation de
l'ensemble des traces d'exécutions du programme
2) chaque chemin f possède un voisinage V dont tous les éléments g (qui
sont eux-mêmes des chemins dirigés sur M) son équivalent à f au sens où
l'état de la mémoire
de la machine abstraite à la fin de l'exécution de g ne dépend pas de g
3) l'ensemble des traces d'exécution forment un ouvert de l'espace des
chemins dirigés sur M
4) les modèles géométriques appartiennent à une classe d'objets qui
satisfait une propriété de décomposition unique vis-à-vis du produit
cartésien. À partir de la décomposition du modèle géométrique d'un
programme, on peut regrouper ses processus de manière à obtenir des
sous-programmes indépendants.

Les constructions et résultats annoncés ci-dessus seront illustrés de
nombreux exemples. :-)

October 1, 2018

Une perspective personnelle sur le problème de satisfaction de contraintes et ses variantes.

Florent Madelaine (LACL UPEC)

La conjecture de la dichotomie énoncée en 1993 par Feder et Vardi stipule que tout problème de contraintes est soit dans P, soit NP-complet.
Un phénomène qu’il faut contraster avec le théorème de Ladner qui implique que ceci n’est pas vrai en général (provisio P différent de NP).
Cette conjecture est un théorème depuis 2017 : il y a deux preuves proposées indépendemment par Bulatov et Zhuk.
Entre ces deux dates, cette question a permis de réunir des personnes issues de profils variés (combinatoire, bases de données, logique, algèbre, …).

On n’en voudra pas au lecteur de se poser la question suivante : ce domaine est-il moribond?
Cet exposé sera l’occasion de tenter d’y répondre par la négative après avoir fait un présentation personnelle de ce domaine.

September 24, 2018

Nombre de points fixes des réseaux booléen: Complexité algorithmique

Florian Bridoux (LIS - Marseille)

Dans cette présentation nous allons nous intéresser aux
réseaux booléens (RB).
Un RB de taille n peut être vu comme une fonction f: {0,1}^n -> {0,1}^n ou
bien comme un produit de n fonctions f_1, f_2, …, f_n de {0,1}^n à
{0,1}.
Un problème classique est le calcul du nombre de points fixes,
c’est-à-dire le nombre de configurations x dans {0,1}^n tel que
f(x) = x.
Un objet souvent utilisé (et qui justifie la terminologie de «
réseaux ») quand on s’intéresse aux réseaux booléens est le
graphe d’interaction.
Il s’agit d’un graphe à n sommets numérotés de 1 à n tel qu’il y a
un arc entre le sommet i et j ssi la valeur de f_j(x) dépendant de la
i-eme composante de x pour un certain x (= le sommet i “a une
influence” sur j).
Chaque RB a son graphe d’interaction mais un même graphe
d’interaction peut correspondre à de nombreux RBs.
Nous allons noter F(G) l’ensemble des RBs correspondant à un certain
graphe d’interaction G.
Et nous allons nous intéresser à la question: “Étant donné G et un
entier k, existe-t-il f dans F(G) qui a au moins/au plus k points
fixes?”
Nous allons voir que selon la nature de k et l’exacte question posée,
le problème peut appartenir à différentes classe de complexité allant de P à NEXPTIME.