2016


Retour à la vue des calendrier
Mardi 4 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Évaluation multi-précision rigoureuse de fonctions D-finies en Sage
Description: Marc Mezzarobba Je présenterai une implémentation en développement d'algorithmes d'évaluation numérique de fonctions D-finies (c.-à-d. solutions d'équations différentielles linéaires à coefficients polynomiaux), pour le logiciel de calcul formel libre SageMath. Ce nouveau package a vocation à remplacer NumGfun, un package un peu similaire pour Maple que j'ai présenté au séminaire CALIN il y a quelques années. Si le temps le permet, je dirai aussi quelques mots des algorithmes originaux utilisés.La fonctionnalité centrale de ce code est le « prolongement analytique numérique » d'une fonction D-finie, qui fournit une approximation de la matrice envoyant un jeu de conditions initiales en un point donné du plan complexe sur les conditions « initiales » qui définissent la même fonction au voisinage d'un autre point. Le prolongement analytique numérique permet de calculer des valeurs ou encore des approximations polynomiales de fonctions D-finies n'importe où sur leur surface de Riemann, des matrices de monodromie d'opérateurs différentiels, etc. Le code traite complètement le cas limite important de conditions initiales généralisées données en un point singulier régulier de l'opérateur. Il peut donc être utilisé pour calculer des matrices de connexion entre singularités régulières, ce qui est utile notamment en combinatoire analytique. Par ailleurs, il s'agit d'une implémentation rigoureuse, au sens où elle renvoie des intervalles qui (sauf bug !) contiennent à coup sûr le résultat mathématique exact.
Jeudi 6 Octobre
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Solving the Asymmetric Travelling Salesman Problem
Description: Luis Gouveia There are many ways of modelling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP).
In this talk we present new formulations for the two problems that can be viewed as resulting from combining precedence variable based formulations, with network flow based formulations. As suggested in [1], the former class of formulations permits to integrate linear ordering constraints.
The motivating formulation for this work is a complicated and "ugly" formulation that results from
the separation of generalized subtour elimination constraints presented in [2] (see also [1]).
This so called "ugly" formulation exhibits, however, one interesting feature, namely the "disjoint subpaths" property that is further explored to create more complicated formulations that combine two (or three) "disjoint path" network flow based formulations and have a stronger linear programming bound.
Some of these stronger formulations are related to the ones presented for the PCATSP in [3] and can be viewed as generalizations in the space of the precedence based variables.
Several sets of projected inequalities in the space of the arc and precedence variables and in the spirit of many presented in [1] are obtained by projection from these network flow based formulations.
Computational results will be given for the ATSP and PCATSP to evaluate the quality of the new
models and inequalities.
References:
[1] L. Gouveia and P. Pesneau. On extended formulations for the precedence constrainted asymmetric
traveling salesman problem. Networks, 48(2):77{89, 2006.
[2] L. Gouveia and J. M. Pires. The asymmetric travelling salesman problem: On generalizations of
disaggregated Miller-Tucker-Zemlin constraints. Discrete Applied Mathematics, 112:129{145, 2001.

Joint work with Pierre Pesneau (University of Bordeaux), Mario Ruthmair (University of Vienna) and Daniel Santos (University of Lisbon)
Heure: 13:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Automatic Extraction of Malicious Behaviors
Description: Khanh-Huu-The Dam
The number of new malwares is increasing everyday.
Thus malware detection is nowadays a big challenge. The
existing techniques for malware detection require a huge
effort of engineering to manually extract the malicious behaviors.
To avoid this tedious task, we propose in this paper
an approach to automatically extract the malicious behaviors.
We model a program using an API call graph,
and we represent the malicious behaviors using a malicious
API graph. We then reduce the malicious behavior extraction
problem to the problem of retrieving from the benign
and malicious API call graphs the set of subgraphs that
are relevant for malicious behaviors. We solve this issue
by applying and adapting well-known efficient Information
Retrieval techniques based on the TFIDF scheme. We use
our automatically extracted malicious behavior specification
for malware detection using a kind of product between
graphs. We obtained interesting experimental results, as we
get 99.04% of detection rate. Moreover, we were able to
detect several malwares that well-known and widely used
antiviruses such as Panda, Avira, Kaspersky, Avast, Qihoo-
360, McAfee, AVG, BitDefender, ESET-NOD32, F-Secure,
and Symantec could not detect.

This is a joint work with Tayssir Touili.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Évaluation multi-précision rigoureuse de fonctions D-finies
Description: Marc Mezzarobba
Mardi 11 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Non-commutative differential equations and (some) geometrical hints
Description: Gérard Duchamp On prendra appui sur les intégrales itérées des systèmesfuschsiens pour proposer une théorie des équations différentiellesnon-commutatives. Plusieurs surprises et cadeaux nous attendentdans cette exploration.
Lundi 17 Octobre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Framester: A Wide Coverage Linguistic Linked Data Hub
Description: Mehwish Alam Semantic web applications leveraging NLP can benefit from easy access to expressive lexical resources such as FrameNet. However, the usefulness of FrameNet is affected by its limited coverage and non-standard semantics. The access to existing linguistic resources is also limited because of poor connectivity among them. We present some strategies based on Linguistic Linked Data to broaden FrameNet coverage and formal linkage of lexical and factual resources. We created a novel resource, Framester, which acts as a hub between FrameNet, WordNet, VerbNet, BabelNet, DBpedia, Yago, DOLCE-Zero, as well as other resources. Framester is not only a strongly connected knowledge graph, but also applies a rigorous formal treatment for Fillmore's frame semantics, enabling full-fl edged OWL querying and reasoning on a large frame-based knowledge graph. We also describe Word Frame Disambiguation, an application that reuses Framester data as a base in order to perform frame detection from text, with results comparable in precision to the state of the art, but with a much higher coverage. Open issues and current research directions will be also presented.
Mardi 18 Octobre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lower bounds in resource constrained shortest path algorithms
Description: Axel Parmentier Resource constrained shortest path problems arise naturally as pricing sub-problems of column generation approaches to a wide range of routing and scheduling problems. The algorithms for these problems rely on dominance relations between paths to discard partial solutions in an enumeration of all the paths. It is well known that the use of bounds on paths resources in addition to dominance relations strongly accelerates these algorithms. Nonetheless, there is still no standard procedure to build such bounds in non-linear or stochastic settings. We provide such a bounding procedure and sho w its efficiency on several deterministic and stochastic path problems. Besides, enumeration algorithms exhibit poor performances when the number of constraints increases. We show that using sets of bounds instead of single bounds enable to discard more paths and thus to tackle better with these difficult instances. Finally, we prove the relevance of these procedures in the context of column generation on industrial instances of the airline crew pairing problem.Â
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatoire des mots
Description: Johan Nilsson
Jeudi 20 Octobre
Heure: 15:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Integer-Complete Synthesis for Bounded Parametric Timed Automata
Description: Étienne André Ensuring the correctness of critical real-time systems, involving concurrent
behaviors and timing requirements, is crucial. Parameter synthesis aims at
computing dense sets of valuations for the timing requirements, guaranteeing a
good behavior. However, in most cases, the emptiness problem for reachability
(i.e. whether there exists at least one parameter valuation for which some
state is reachable) is undecidable and, as a consequence, synthesis procedures
do not terminate in general, even for bounded parameters. In this paper, we
introduce a parametric extrapolation, that allows us to derive an
underapproximation in the form of linear constraints containing all the
integer points ensuring reachability or unavoidability, and all the
(non-necessarily integer) convex combinations of these integer points, for
general PTA with a bounded parameter domain. Our algorithms terminate and can
output constraints arbitrarily close to the complete result.

Joint work with Didier Lime and Olivier H. Roux.
Vendredi 21 Octobre
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Some interplays between proof theory and computational complexity
Description: Anupam Das Proof complexity is the branch of proof theory concerned with the size of proofs. Due to old and well-known results of Cook and Reckhow, many important questions about computational complexity are equivalent to natural problems in proof complexity. For instance, coNP = NP just if there is an 'efficient' proof system for classical propositional logic. I will survey a now well-developed line of work on the proof complexity of 'deep inference' systems which has culminated in several novel phenomena in proof complexity, including improved bounds for monotone proof systems. I will also discuss remaining open problems in the area and some of their consequences.

A closely related area to proof complexity is bounded arithmetic, which studies weak fragments of arithmetic whose representable functions are typically feasible complexity classes, via bounds on quantifiers. They also act as uniform versions of corresponding propositional systems, forming a three-way correspondence. I will show how this methodology can be extended to certain deep inference and monotone systems via intuitionistic versions of bounded arithmetic, making use of a novel technique that combines the usual 'witness function method' of bounded arithmetic with realisability style extraction. I will further motivate the study of such theories in 'linear logic' in order to address the remaining correspondences, and present some recent work along this line.

Finally I will present an upcoming research project that aims to unify various strands of this research in order to develop a comprehensive approach to monotone complexity classes.
Mardi 25 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBA
Description: Vincent Pilaud
Lundi 14 Novembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Identification des expressions poylexicales et analyse syntaxique en dépendances
Description: Mathieu Constant Les expressions polylexicales (EP) sont des séquences formées de plusieurs mots se caractérisant par un certain degré de non-compositionalité que ce soit au niveau morphologique, lexical, syntaxique, sémantique ou/et pragmatique. Leur identification est cruciale pour les différentes applications du traitement automatique des langues.

Dans cet exposé, nous nous intéressons à l’intégration de l’identification des EP au sein de l’analyse syntaxique en dépendances statistique. Après avoir évoqué les différents défis liés à l’identification automatique des EP, nous aborderons ce sujet en essayant de répondre à deux problématiques: (1) trouver une représentation la plus riche possible des exp ressions polylexicales au regard de l’analyse syntaxique; (2) adapter les algorithmes d’analyse existants pour prédire de manière jointe l’analyse lexicale et syntaxique d’une phrase dans cette représentation.
En particulier, nous montrerons de nouvelles représentations factorisées sur deux dimensions, ainsi que de nouveaux algorithmes d’analyse syntaxique intégrant des mécanismes spécifiques pour l’identification des EP.
Mardi 15 Novembre
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On Generalized Hypergeometric Solutions of Linear Differential Systems of First Order
Description: Suzy Maddah In this talk, we consider linear differential systems of first order (equivalently linear differential equations of arbitrary order), and we question whether they can be solved in terms of generalized hypergeometric functions. This question is motivated by the manyproperties of the latter which arise in physics and combinatorics. It has been tackled in the literature for second-order differential equations, namely Bessel's, Whittaker's, Kummer's, and Gauss's. We propose a new algorithm which surpasses the restrictions on thedimension of the system, and equivalently on the order of the equation. This is a joint work with Frédéric Chyzak.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Pavages
Description: Samuel Petite
Heure: 15:15 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An interface between physics and number theory
Description: Quoc Hoan Ngo
Mardi 22 Novembre
Heure: 16:15 - 19:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Double régularisation des polyzêtas en les multi-indices négatifs
Description: Quoc Hoan Ngo
Jeudi 24 Novembre
Heure: 10:00 - 11:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Vers une théorie de la réécriture probabiliste
Description: Flavien Breuvart Après une récapitulation des définitions fondamentales et enjeux
de la théorie de la réduction de termes (TRS et HORS), nous allons
nous poser la question de l'ajout de composantes probabilistes.

Nous verrons que des problématiques importantes apparaissent à un
niveau très élémentaire. En fait, elles apparaissent déjà au
niveau des ARS (graphe orientés infinis décrivant une dynamique)
qui sont extrêmement généraux et contiennent les automates dont
la généralisation probabiliste a été abondamment étudiée. En
utilisant ces travaux sur les automates, et plus généralement sur
les co-algèbres, nous avons décrit un formalisme pouvant, nous
l'espérons, traiter élégamment des problèmes de réécritures
probabilistes.
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Regular Model Checking: Vérification et systèmes de réécriture
Description: Tayssir Touili Nous nous intéressons dans cet exposé au model-checking des systèmes infinis, notamment les systèmes paramétrés et les programmes récursifs parallèles.
Nous présentons un cadre uniforme pour la vérification algorithmique de ces systèmes. Ce cadre est basé sur la représentation des ensembles de configurations par des automates de mots ou d'arbres, et la représentation des relations de transition des systèmes par des règles de réécritures de mots ou de termes. Le problème de la vérification est ensuite réduit au calcul des ensembles des accessibles dans ce cadre.
Vendredi 25 Novembre
Heure: 11:00 - 12:30
Lieu: Salle A303, bâtiment A, Université de Villetaneuse
Résumé: Implémentation de complexité implicite dans les compilateurs
Description: Thomas Rubiano La complexité implicite s’intéresse à la gestion des ressources, temps
ou espace, consommées par un programme. Comme les méthodes de
complexité implicite fonctionnent à l’aide de critères purement
syntaxiques, ces analyses peuvent être faites au moment de la
compilation du programme (et pas au cours de son exécution) et le
“certificat” obtenu peut alors être directement associé à
l’exécutable. De plus, les compilateurs manipulent dans leurs
représentations intermédiaires des langages proches de l’assembleur
avec un accès au graphe de flot de contrôle. Ainsi, on dispose
directement des outils nécessaires pour exprimer certaines méthodes de
complexité implicite. Le but initial de la thèse était d’écrire, un
plugin pour effectuer la détection de programmes qui calculent en
espace constant (Non-Size-Increasing Programs) au cours de la
compilation et en déduire automatiquement des optimisations
d’allocation de mémoire. Le premier compilateur cible a été llvm, une
passe a donc été implémentée.

Ensuite, il était prévu d’une part de continuer à implémenter des
méthodes de complexité implicite dans les compilateurs –notamment la
Size Change Termination ou les polynômes mwp qui s’expriment bien sur
un langage impératif de bas niveau. D’autre part, de chercher à
exprimer d’autres analyses dans ce genre de langage afin de comparer
de manière plus systématique les différentes analyses existantes.

C'est en apprenant les techniques utilisées dans ces deux dernières
théories que nous nous sommes intéressés à implémenter une
optimisation de pelage de boucle présentée sur un langage WHILE dans
un brouillon de Lars Kristiansen. Nous l'avons repris et baptisée:
"Calcul de degré d'invariance et composition de commandes pour du
pelage de boucle". Après avoir fait quelques tests sur le langage C à
l'aide d'un parser « jouet » en python. Une passe LLVM est en cours de
développement…

Les analyses de complexité implicites sont actuellement décrites sur
des langages « jouets ». En les portant sur des « vrais » langages de
programmation, la thèse a pour but de fournir à la communauté un outil
permettant de traiter une grande quantité d’exemples et d’avoir une
idée plus précise de l’expressivité réelle de ces analyses. De plus
elle crée un pont avec la communauté compilation afin que chacune
apporte à l'autre.

Cette thèse est financée par le projet ANR ELICA
Lundi 28 Novembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Semantically enriched methods for next generation microblog message fine-grained geolocalization
Description: Laura Di Rocco Consistent user-generated data represent a valuable source for the extraction of new types of information patterns and knowledge. The multifaceted nature of user-generated data, along with its geographic component, is being exploited to better understand social dynamics and propagation of information. Social media activities can be associated with both an explicit and an implicit geographic information component. Consider, for instance, Twitter as a typical example. In this case, georeferencing information can be explicitly available as metadata, such as the user profile location and the GPS coordinates of the device from which the activity is performed. By contrast, implicit georeferencing information can be inferred, with variable degree of confidence, by the message content itself, which may contain images, names of entities with known spatial location, or by the social relationships and interactions among users.
Our focus is on inferring the tweeting location (i.e., the position of the user when the tweet was sent) rather than the user home location. Since explicit tagging is used only in a small percentage of tweets, we will use geospatial information implicit in the messages to improve the resolution of the georeferencing process. With the aim of fully exploiting the (explicit and implicit) fine-grained georeferencing information made available by social media, the project relies on semantically enhanced and refined crowdsourced geospatial data to extract fine-grained implicit geoinformation contained in tweet contents.

Short Bio:
Laura Di Rocco is a PhD Student at University of Genoa and a visiting PhD Student at Paris Descartes University (LIPADE). Her research interests are in the areas of geospatial data and text mining on social media.
Mardi 29 Novembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Une analyse asymptotique des polyominos digitalement convexes.
Description: Olivier Bodini Dans cet exposé, nous montrerons comment des techniques élémentaires (transformées de Mellin) en combinatoire analytique permettent d'obtenir des résultats assez surprenants sur les polyominos. En particulier, si l'on savait correctement énumérer les polyominos digitalement convexes, nous saurions si l'hypothèse de Riemann est vraie !
Jeudi 1 Décembre
Heure: 15:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Approches pour la modélisation et vérification des systèmes temporisés en utilisant les diagrammes états-transitions et les réseaux de Petri colorés
Description: Mahdi Benmoussa (Répétition avant soutenance de thèse.)
Nous présentons dans ce travail de thèse des approches pour la spécification et la vérification des systèmes temporisés.
La première partie concerne une méthode de spécification en utilisant les diagrammes états-transitions pour modéliser un système donné en partant d'une description textuelle.
Elle comporte plusieurs étapes et utilise des observateurs d'états et des événements afin d'engendrer le diagramme états-transitions.
Un outil qui implémente les différentes étapes de la méthode de spécification pour une application semi-automatique est présenté.
La seconde partie concerne une traduction des diagrammes états-transitions vers les réseaux de Petri colorés, ce qui permet d'utiliser les méthodes de vérification.
Nous prenons en considération dans cette traduction un ensemble important des éléments syntaxiques des diagrammes états-transitions, tels que la concurrence, la hiérarchie, etc.
Un outil qui implémente la traduction pour un passage automatique des diagrammes états-transitions vers les réseaux de Petri colorés est en cours de développement.
La dernière partie concerne l'intégration des contraintes temporelles dans les deux approches précédentes.
Nous définissons des annotations pour les diagrammes états-transitions dont nous fournissons la syntaxe et la sémantique.
Ces annotations seront ensuite utilisées dans la méthode de spécification et la traduction.
Le but est de proposer des annotations faciles à comprendre et à utiliser avec une syntaxe qui prend en compte des contraintes parmi les plus utilisées.
Vendredi 2 Décembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Proving array-manipulating programs without arrays
Description: David Monniaux Automatically verifying safety properties of programs is hard. Many
approaches exist for verifying programs operating on Boolean and integer
values (e.g. abstract interpretation, counterexample-guided abstraction
refinement using interpolants), but transposing them to array properties has
been fraught with difficulties.
Our work addresses that issue with a powerful and flexible abstraction that
morphes concrete array cells into a finite set of abstract ones. This
abstraction is parametric both in precision and in the back-end analysis used.

One possible application would be distributed systems, where processes
are modeled using arrays indexed by the process ID.
Mardi 6 Décembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Streaming and communication complexity of Hamming distance
Description: Tatiana Starikovskaya
Vendredi 9 Décembre
Heure: 14:30 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Développement asymptotique des sommes harmoniques (soutenance de thèse)
Description: Van Chiên Bui En abordant les nombres spéciaux comme les sommes harmoniques ou les polyzêtas sous leur aspect combinatoire, nous introduisons d'abord la définition d'un produit entre mots, dit produit de quasi-mélange q-déformé, une généralisation des produits de mélange et de quasi-mélange, ce qui nous permet de construire des structures complètes d'algèbre de Hopf en dualité. En même temps, nous construisons des bases en dualité, contenant des bases de transcendance associées aux mots de Lyndon, et des formules explicites sur lesquelles les sommes harmoniques, les polyzêtas ou les polylogarithmes sontindexés et représentés par la factorisation de la série génératrice noncommutative diagonale. De cette façon, en identifiant les coordonnées locales, nous trouvons des relations polynomiales homogènes, en poids, entre les polyzêtas indexés par ces bases.Enfin, nous déterminons les développements asymptotiques des sommes harmoniques, indexées aussi par ces bases, grâce à leur série génératrice et à la formule d'Euler Maclaurin.Pour accompagner cette étude théorique, nous proposons des algorithmes et un package en Maple afin de calculer des bases,la structure des polyzêtas et des développements asymptotiques des sommes harmoniques.Le jury sera composé de Gérard Duchamp, Hoang Ngoc Minh,(co-directeurs), Jacky Cressson, Loïc Foissy,(rapporteurs), Sylvie Paycha, Joris van der Hoeven, Daniel Barsky, Christophe Tollu (examinateurs).
Heure: 16:00 - 19:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Double regularization of polyzetas at negative multi-indices and rational extensions (soutenance de thèse)
Description: Quoc Hoan Ngo In this PhD thesis are studied the polylogarithms and the harmonic sums at non-positive (i.e., weakly negative) multi-indices. General results about these objects in relation with Hopf algebras are pr ovided. The technics exploited here are based on thecombinatorics of noncommmutative generating series relative to the Hopf phi-huffle algebra. Our work will also propose a global process to renormalize divergent polyzetas. Finally, we will apply these ideas to non-linear dynamical systems with singular inputs.The jury will be composed of:Gérard Duchamp, Hoang Ngoc Minh (directeurs),Sylvie Paycha, Dominique Manchon (rapporteurs), Karol Penson, Vincent Rivasseau, Loic Foissy, Christophe Tollu.