Retour à la vue des calendrier
Jeudi 2 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On big data, optimization and learning
Description: Prof. Andrea Lodi In this talk I review a couple of applications on Big Data that I personally like and I try to explain my point of view as a Mathematical Optimizer -- especially concerned with discrete (integer) decisions -- on the subject. I advocate a tight integration of Machine Learning and Mathematical Optimization (among others) to deal with the challenges of decision-making in Data Science. For such an integration I try to answer three questions: 1) what can optimization do for machine learning? 2) what can machine learning do for optimization? 3) which new applications can be solved by the combination of machine learning and optimization?
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Reachability Analysis of Pushdown Systems with an Upper Stack
Description: Adrien Pommellet Pushdown systems (PDSs) are a natural model for sequential programs, but they can fail to accurately represent the way an assembly stack actually operates. Indeed, one may want to access the part of the memory that is below the current stack or base pointer, hence the need for a model that keeps track of this part of the memory. To this end, we introduce pushdown systems with an upper stack (UPDSs), an extension of PDSs where symbols popped from the stack are not destroyed but instead remain just above its top, and may be overwritten by later push rules.

We prove that the sets of successors post* and predecessors pre* of a regular set of configurations of such a system are not always regular, but that post* is context-sensitive, so that we can decide whether a single configuration is forward reachable or not. In order to underapproximate pre* in a regular fashion, we consider a bounded-phase analysis of UPDSs, where a phase is a part of a run during which either push or pop rules are forbidden. We then present a method to overapproximate post* that relies on regular abstractions of runs of UPDSs. Finally, we show how these approximations can be used to detect stack overflows and stack pointer manipulations with malicious intent.
Vendredi 3 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Introduction à la théorie de la complexité géométrique, d'après K. Mulmuley
Description: Luc Pellissier La théorie de la complexité géométrique est un programme de recherche porté par
Ketan Mulmuley, qui vise à résoudre des questions de complexité après les avoir
traduites comme des inclusions de surfaces algébriques représentant des groupes
de symétries.

Après avoir présenté la théorie avec beaucoup de recul, on présentera un
résultat de séparation obtenu ainsi (entre P et une classe ad hoc).
Lundi 6 Mars
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Automatic Deception Detection in Text Applying Topic Modeling Algorithms
Description: Hiram Calvo We deal with deceptive text identification by using different kinds of features: a continuous semantic space model based on latent Dirichlet allocation topics (LDA), one-hot representation (OHR), syntactic information from syntactic n-grams (SN), and lexicon-based features using the linguistic inquiry and word count dictionary (LIWC). We will present experiments with several combinations of these features were tested to assess the best source(s) for deceptive text identification aiming to present a state of the art performance. We conducted our tests on three different available corpora: a corpus consisting of 800 reviews about hotels, a corpus consisting of 600 reviews about controversial topics, and a corpus consisting of 236 book reviews. Additionally, we present an analysis on which features lead to either deceptive or truthful texts, finding that certain words can play different roles (sometimes even opposing ones) depending on the task being evaluated. We will present results of experiments in one-domain setting by training and testing our models separately on each dataset (with fivefold cross-validation); in a mixed-domain setting by merging all datasets into one large corpus (again, with fivefold cross-validation), and finally, with cross-domain setting: using one dataset for testing and a concatenation of all other datasets for training.
Mardi 7 Mars
Heure: 11:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Valid quadratic inequalities for convex and some non-convex quadratic sets
Description: Julio César Góez In recent years, the generalization of Balas disjunctive cuts for mixed integer linear optimization problems to mixed integer non-linear optimization problems has received significant attention. Among these studies, mixed integer second order cone optimization (MISOCO) is a special case. For MISOCO one has the disjuncti ve conic cuts approach. That generalization introduced the concept of disjunctive conic cuts (DCCs) and disjunctive cylindrical cuts (DCyCs). Specifically, it showed that under some mild assumptions the intersection of those DCCs and DCyCs with a closed convex set, given as the intersection of a second order cone and an affine set, is the convex hull of the intersection of the same set with a linear disjunction. The key element in that analysis is the use of pencils of quadrics to find close forms for deriving the DCCs and DCyCs. In this talk we present an overview of the DCCs main results and we use the same approach to show the existence of valid conic inequalities for hyperboloids and non-convex quadratic cones when the disjunction is defined by parallel hyperplanes. Joint work with Miguel F. Anjos.
Jeudi 9 Mars
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hybride Modelling, Analysis and Quantitative Verification of Large Biological Regulatory Networks
Description: Louis Fippo Fitime Biological Regulatory Networks (BRNs) are usually used in systems biology for modelling,
understanding and controlling the dynamics of different biological functions (differentiation,
proliferation, proteins synthesis, apoptose) inside cells. Those networks are enhanced with
experimental data that are nowadays more available which give an idea on the dynamics of BRNs components.
Formal analysis of such models fails in front of the combinatorial explosion of generated behaviours
despite the fact that BRNs provide abstract representation of biological systems.

This thesis handles hybrid modelling, the simulation, the formal verification and control of Large
Biological Regulatory Networks. This modelling is done thanks to stochastic automata networks, thereafter
to Process Hitting by integrating time-series data.

Firstly, this thesis proposes a refining of the dynamics by estimation of stochastic and temporal (delay)
parameters from time-series data and integration of those parameters in automata networks models. This
integration allows the parametrisation of the transitions between the states of the system. Then,
a statistical analysis of the traces of the stochastic simulation is proposed to compare the dynamics
of simulations with the experimental data.

Secondly, this thesis develops static analysis by abstract interpretation in the automata networks
allowing efficient under- and over-approximation of quantitative (probability and delay) reachability properties.
This analysis enables to highlight the critical components to satisfy these properties.

Finally, taking advantage from the previous developed static analyses for the reachability properties in the
qualitative point of view, and from the power of logic programming (Answer Set Programming), this thesis addresses the domain
of control of system by proposing the identification of bifurcation transitions. Bifurcations are
transitions after which the system can no longer reach a state that was previously reachable.
Vendredi 10 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Retrofitting linear types
Description: Arnaud Spiwack Type systems based on linear logic and their friends have proved that they are both capable of expressing a wealth of interesting abstractions. Among these the ability to mix garbage-collected and explicitly managed data in the same language. This is of prime interest for distributed computations that need to reduce latency induced by GC pauses: a smaller GC heap is a happier GC heap.

I had always had the belief that to add linear types to a language was a rather intrusive procedure and that a language with linear types would basically be an entirely new language. The Rust language is a case in point: it has a linear-like type system, but it's a very different language from your run-of-the-mill functional language.

This turns out not to be the case: this talk presents a way to extend a functional programming language. We are targeting Haskell but there is little specific to Haskell in this presentation. I will focus mostly on the type system and how it can be generalised: among other things the type system extends to dependent types.
Mardi 14 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Géométrie combinatoire : densité d'hypergraphes et méthode probabiliste
Description: Xavier Goaoc Un hypergraphe à n sommets dont aucune projection sur k sommet n'est complète a au plus O(n^{k-1}) arêtes. Ce résultat, découvert simultanément par Sauer, Vapnick-Chervonenkis et Perles-Shelah au début des années 1970, est fondamental en apprentissage. En géométrie combinatoire et algorithmique, il permet souvent de contrôler la complexité (globale) d'une structure par sa "densité" locale. J'introduirai à ce mécanisme avant de présenter quelques extensions récentes, obtenues conjointement avec Boris Bukh (https://arxiv.org/abs/1701.06632), qui permettent un controle plus fin de la complexité. L'exposé ne supposera aucune connaissance préalable et un des ingrédients sera une construction probabiliste.
Jeudi 16 Mars
Heure: 15:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Preserving Partial Order Runs in Parametric Time Petri Nets
Description: Cesar Rodriguez Parameter synthesis for timed systems aims at deriving parameter
valuations satisfying a given property.
In this paper we target concurrent systems; it is well known that
concurrency is a source of state-space explosion, and partial order
techniques were defined to cope with this problem.
Here we use partial order semantics for parametric time Petri nets as a
way to significantly enhance the result of an existing synthesis
Given a reference parameter valuation, our approach synthesizes other
valuations preserving, up to interleaving,
the behavior of the reference parameter valuation.
We show the applicability of our approach using acyclic asynchronous circuits.

Join work with Thomas Chatain and Étienne André.
Vendredi 17 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Des preuves, oui, mais formelles !
Description: Micaela MAYERO Dans cet exposé, très informel, lui, je parlerai de l'évolution des outils de preuves formelles ces 20, voire ces 30, dernières années. Nous nous appuierons sur quelques exemples afin de montrer comment les formalisations contribuent à la fois au développement de ces outils via des avancés théoriques majeurs ainsi qu'aux domaines qui s'engagent peu à peu dans leur utilisation. Suite à une première partie accessible à tout public, nous parlerons de la logique sous-jacente à l'un des système connaissant le plus d'avancées et de changements: Coq. Nous aborderons les évolutions de la théorie des types avec (im)prédicativité, la logique classique avec le choix de la totalité et d'autres avancées, pour finir, si nous avons le temps, par quelques mots sur CoqHoTT et l'axiome d'univalence.
Jeudi 23 Mars
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: CARET Model Checking For Pushdown Systems
Description: Huu-Vu Nguyen CARET (A temporal logic of calls and returns) was introduced by Alur et al. This logic allows to write linear temporal logic formulas while taking into account matching of calls and returns. However, CARET model checking for Pushdown Systems (PDSs) was never considered in the literature. Previous works only dealt with the model checking problem for Recursive State Machine (RSMs). While RSMs are a good formalism to model sequential programs written in structured programming languages like C or Java, they become non suitable for modeling binary or assembly programs, since, in these programs, explicit push and pop of the stack can occur. Thus, it is very important to have a CARET model checking algorithm for PDSs. We tackle this problem in this paper. We also consider CARET model checking with regular valuations, where the set of configurations in which an atomic proposition holds is a regular language. We reduce these problems to the emptiness problem of Büchi Pushdown Systems. We implemented our technique in a tool, and we applied it to different case studies. Our results are encouraging. In particular, we were able to apply our tool to detect several malwares.

This is a joint work with Tayssir Touili.
Vendredi 24 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Syntaxe transcendentale: seconde lecture.
Description: Christophe Fouqueré Suite de la première lecture: JY Girard, avec ses 3 articles sur la "syntaxe transcendentale", aborde la logique sous un angle à la fois philosophico-logique et sous un angle technique, pour aller au-delà de ce qui est fait jusqu'à présent: non seulement la logique linéaire propositionnelle mais encore le traitement de l'égalité donc du premier ordre. Modestement, je commencerai par présenter la partie technique, qui reprend et étend le modèle des réseaux de preuves, en présentant la représentation de MALL et des exponentielles.
Mardi 28 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints
Description: Sergey Dovgal We show that by restricting the degrees of the vertices of a graph to an arbitrary set ?, the threshold ?(?) of the phase transition for a random graph with n vertices and m = ?(?).n edges can be either accelerated (e.g.,?(?) approx 0.38 for ? = {0,1,4,5}) or postponed (e.g., ?(?) approx 0.95 for ?={1,2,50}) compared to a classical Erd?s?Rényi random graph where ?(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...).We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literalis incident to belongs to the set ?. We prove a lower bound for the probability that a formula with n variables and m=2.?(?) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.?.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson.This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals.Joint work with Vlady Ravelomanana.
Vendredi 31 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Équivalences entre programmes
Description: Jean-Yves Moyen Partant du théorème de Rice, on définit l'équivalence extensionelle comme "deux programmes sont équivalents si ils calculent la même fonction." Le théorème de Rice stipule alors une indécidabilité forte de cette équivalence (aucune union de classes n'est décidable).

Qu'en est-il des autres équivalences entre programmes ? Certaines sont décidables (eg, avoir le même nombre de lignes de codes), d'autres non. L'ensemble des équivalences possède une structure de treillis complet et le théorème de Rice parle de l'indécidabilité d'un filtre principal de ce treillis.

À partir de ces constatations, j'explore deux pistes parallèles. D'une part, quelle est l'importance de l'équivalence extensionelle dans ces résultats ? Est-ce qu'on peut obtenir d'autres résultats similaires à partir d'une autre équivalence ? D'autre part, comment étudier l'ensemble du treillis des équivalences ? Est-ce qu'on peut trouver des sous-ensembles qui conservent la structure lié à l'ordre tout en étant plus facilement manipulables (notamment, dénombrables) ?
Mardi 4 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: String algorithms for bioinformatics
Description: Mireille Régnier
Mardi 11 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Utilisation avancée de Maple : calcul parallèle et interfaçage avec des bibliothèques externes
Description: Nicolas Gachadoit et Nicolas Cottereau Maple possède plusieurs milliers de fonctions, mais certains calculs spécifiques peuvent nécessiter l'utilisation de bibliothèques externes. Par ailleurs, les ordinateurs n'évoluent plus tellement dans le sens d'une augmentation de la fréquence des processeurs maisdans le sens d'une augmentation du nombre de c?urs de calcul.Cette présentation (par Nicolas Gachadoit) détaillera les fonctionnalités de Maple permettant de réaliser des calculs parallèles et de s'interfacer avec du code écrit dans d'autres langages.Il y aura également une présentation rapide (par Nicolas Cottereau) de quelques fonctionnalités de la plateforme Maple dédiée pour l?enseignement.
Mardi 18 Avril
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Deriving differential approximation results for k-CSPs from combinatorial designs
Description: Sophie Toulouse Given two integers q, k ? 2, k-CSP?q is the unconstrained optimization problem in which variables have domain Z_q and the goal is to optimize a weighted sum of constraints, each acting on at most k of the variables. Standard inapproximability results for Max-k-CSP?q often involve balanced k-wise independent distributions over Z_q or rather equivalently, orthogonal arrays of strength k over Z_q. We here illustrate how combinatorial designs are a relevant tool in order to establish approximation results for k-CSP?q with respect to the differential approximation measure, which compares the distance between the approximate value and the worst solution value to the instance diameter. First, connecting the average differential ratio to orthogonal arrays, we deduce that this ratio is ?(1/n^(k/2)) when q = 2, ?(1/n^(k-1)) when q is a prime power and 1/q^k on (k+1)-partite instances. We also consider pairs of arrays that can be viewed as some constrained decomposition of balanced k-wise independent functions. We exhibit such pairs that allow when q > k to reduce k-CSP?q to k-CSP?k with an expansion 1/(q?k/2)^k on the approximation guarantee. This implies together with the result of [Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), pp. 141–160] a lower approximability bound of 0.429/(q ? 1)^2 for 2-CSP?q. Similar designs also allow to establish that every Hamming ball with radius k provides a ?(1/n^k)-approximation of the instance diameter.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Holonomie et non-holonomie des marches dans le quart de plan
Description: Thomas Dreyfus
Vendredi 21 Avril
Heure: 15:00 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Complex network analysis in ubiquitous and social environments
Description: Martin Atzmueller In the world of today, a variety of interaction data of humans, services and systems is generated, e.g. , by sensors and social media. This enables the observation and capture of physical and social activities, and subsequent extended analysis of interactions, structures and patterns covering both online and offline contexts. This talk focuses on behavioral analytics in social media and the physical world, and presents exemplary methods and results in the context of real-world systems. Specifically, we focus on the grounding and analysis of behavior, interactions and complex structures emerging from heterogeneous data, and according modeling approaches using complex network analysis.
Mardi 25 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Random graphs and average-case analysis of NP-complete problems
Description: Tom Denat
Jeudi 27 Avril
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: RoSTBiDFramework: Optimised Framework based on Rough Set Theory for Big Data Pre- processing in Certain and Imprecise Contextsble
Description: Zeineb Chelly Over the last decades, the amount of data has increased in an
unprecedented rate, leading to a new terminology: "Big Data". Big data
are specified by their Volume, Variety, Velocity and by their
Veracity/Imprecision. Based on these 4V specificities, it has become
difficult to quickly acquire the most useful information from the huge
amount of data at hand. Thus, it is necessary to perform data
(pre-)processing as a first step. In spite of the existence of many
techniques for this task, most of the state-of-the-art methods require
additional information for thresholding and are neither able to deal
with the big data veracity aspect nor with their computational
requirements. This project's overarching aim is to fill these major
research gaps with an optimised framework for big data pre-processing
in certain and imprecise contexts. Our approach is based on Rough Set
Theory (RST) for data pre-processing and Randomised Search Heuristics
for optimisation and will be implemented under the Spark MapReduce
model. The project combines the expertise of the experienced
researcher Dr Zaineb Chelly Dagdia in machine learning, rough set
theory and information extraction with the knowledge in optimisation
and randomised search heuristics of the supervisor Dr Christine Zarges
at Aberystwyth University. Further expertise is provided by internal
and external collaborators from academic and non-academic
institutions, namely Lebbah and Azzag (University of Paris 13), Shen
(University of Aberystwyth), Tino (University of Birmingham), Merelo
(University of Granada) and an industrial partner from France.
Mardi 2 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatoire énumérative des pseudo-n?uds
Description: Jean-Marc Steyaert
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Mots minimaux absents
Description: Alice Héliou
Vendredi 5 Mai
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Why complexity theorists should care about philosophy
Description: Thomas Seiller Theoretical computer science was somehow born almost a hundred years ago when logicians asked themselves the question: "What is a computable function?". This question, purely theoretical, was answered before the first computer was designed, in the form of the Church-Turing thesis: a computable function is one that can be defined in one of the following equivalent models: recursive functions, Turing machines, or lambda-calculus. The apparition of actual computing devices however made it clear from the start that another question made more sense for practical purposes, namely: "What is an *efficiently* computable function?". This question was tackled by three different work in the span of a single year, marking the birth of computational complexity.

Nowadays, computational complexity is an established field: many methods and results have been obtained, and the number of complexity classes grows every year. However, a number of basic open problems remain unanswered, in particular concerning classification of complexity classes. Even worse than that, a number of results – called barriers – show that no known method will succeed in producing a new separation result, i.e. show that two classes (e.g. P and NP, or L and P) are disjoint. From a purely theoretical point of view, this lack of methods might be explained by a historic tradition of viewing programs as functions. Once this misconception identified, it points to a lack of adequate foundations for the theory of computation. Fortunately, some recent technical developments may provide a solution to this problem.
Mardi 9 Mai
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Derivative-Free Line search Methods for Solving Integer Programming Problems
Description: Francesco Rinaldi In this talk, we describe some derivative-free methods for integer programming problems with both bound constraints on the variables and general nonlinear c onstraints. The approaches combine linesearches with a specific penalty approach for handling the nonlinear constraints. The use of both suitable generated search directions and specific stepsizes in the linesearch guarantee that all the points are generated in the integer lattice.

We analyze the theoretical properties of the methods and show extensive numerical experiments on both bound constrained and nonlinearly constrained problems.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Random graphs and average-case analysis of NP-complete problems
Description: Tom Denat
Jeudi 11 Mai
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Accountable classification without frontiers
Description: Khaled Belahcen We address the problem of multicriteria ordinal sorting through the lens of accountability, i.e. the ability of a human decision-maker to own a recommendation made by the system. We put forward a number of model features that would favor the capability to support the recommendation with a convincing explanation. To account for that, we design a recommender system implementing and formalizing such features. This system outputs explanations defined under the form of specific argument schemes tailored to represent the specific rules of the model. At the end, we discuss possible and promising argumentative perspectives.
Vendredi 12 Mai
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Monades et comonades (suite)
Description: Flavien Breuvart Dans cette deuxième séance du GdT modades et comonades, je
présenterais les monades et comonades gradées. J'insisterais, en
particulier, sur ma vision de ces objets comme potentielle piste pour
faire interagir interprétation abstraite et typage dans les langages
Lundi 15 Mai
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Directed homology theories for geometric models of true concurrency
Description: Jérémy Dubut Studying a system through its geometry is the main purpose of directed algebraic topology. This topic emerged in computer science, more particularly in true concurrency, where Pratt introduced his higher dimensional automata (HDA) in 1991 (actually, the idea of geometry of concurrency can be tracked down Dijkstra in 1965). Those automata are geometric by nature: every set of n processes executing independent actions can be modeled by a n-cube, and such an automata then gives rise to a topological space, obtained by glueing such cubes together, with a specific direction of time coming from the execution flow. It then seems natural to use tools from algebraic topology to study those spaces: paths model executions, homotopies of paths, that is continuous deformations of paths, model equivalence of executions modulo scheduling of independent actions, and so on, but all those notions must preserve the direction somehow. This brings many complications and the theory must be done again, essentially from scratch.

In this talk, after developing this idea of geometry of true concurrency, I will focus on homology. Homology is a nice computable tool from algebraic topology and it is a challenge in directed algebraic topology to find a satisfactory analogue that behaves well with direction. I will present our candidate of `directed homology’, called natural (or bimodule) homology. This object consists in a functor with values in modules, which looks at the classical homology of trace spaces (a nice abstraction of what we may call `space of executions’) and how those homologies evolve with time. This evolution can be studied through an abstract notion of bisimulation of functors with values in modules, that has many equivalent characterizations (using relations, using lifting properties, using Grothendieck construction, …) and whose existence is decidable in simple cases. Finally, among nice properties of our directed homology, I will show you that it is computable on simple spaces, which are already enough to model simple truly concurrent systems.

Joint work with Eric Goubault and Jean Goubault-Larrecq.
Mardi 16 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Génération uniforme de marches 2D
Description: Yann Ponty
Heure: 15:30 - 18:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Thé combinatoire accompagné d'un petit problème de combinatoire géométrique issu de l'apprentissage
Description: Yann Chevaleyre
Mardi 23 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Magouilles diverses pour les machines à signaux
Description: Thierry Monteil Les machines à signaux sont un modèle de calcul déterministe dont espace et temps sont continus.Si les accumulations d'événements sont interdites, ce modèle est connupour être équivalent au modèle de BlumShubSmale linéaire. Nousconstruirons dans ce cadre un oracle universel optimal (en nombre devitesses et de paramètres irrationnels). Nous verrons comment jouer aubillard permet semi-décider l'algébricité d'un nombre réel alors que c'estimpossible dans le modèle BSS-linéaire. Nous verrons comment modifierlégèrement le modèle pour obtenir un modèle équivalent au modèle BSSstandard.Lorsque l'on permet aux accumulations d'événements de produire un signal,nous verrons, en jouant sur l'alternance discret/continu, commentconstruire des machines dont le pouvoir dépasse largement les modèles decalcul usuels, en particulier, nous construirons une "courbe de Peano" c'est a dire une surjection de [0,1] dans[0,1]^2. un "oracle universel continu", c'est à dire un machine à un paramètreM(p) telle que toute suite N->[0,1] est generèe un certain M(p). une "fonction analytique universelle", c'est à dire une machine avec2 parametres t,x telle que pour toute fonction analytique f de rayon deconvergence >1, il existe t tel que f(x)=M(t,x) pour tout x dans [-1,1],en particulier, on peut calculer les fonctions exp(x), sin(), en déplaçantun curseur. aussi, on peut prendre en compte la géométrie du modèle dans laformulation même de ce que peut "calculer" (ou "dessiner") une machine,pas seulement un booléen, un entier ou un réel comme dans le cas discret.Étant donnée une machine M, si certains types de collisions sont coloriésen rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Ilse trouve que cette restriction est la seule : il existe une machine à unparametre M(p) telle que pour tout compact K inclus dans [0,1], il existep dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps1 est K.L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.
Mardi 30 Mai
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial optimization problems in networks
Description: Nelson Maculan We present optimization models with a polynomial number of variables and constraints for combinatorial optimization problems in networks: optimum elementary cycles (whose traveling salesman problem), optimum elementary paths even in a graph with negative cycles, and optimum
trees (whose Steiner tree problem) problems. Computational results for the Steiner tree problem are also presented.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sommes binomiales, diagonales de fonctions rationnelles et intégrales sur des cycles
Description: Pierre Lairez