2015


Retour à la vue des calendrier
Lundi 2 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Open questions on Dynamic Semantic Annotation
Description: Ivan GARRIDO MARQUEZ Semantic annotation provides a powerful advantage for several
applications requiring text analysis. Semantic annotation requires the
presence of a semantic model to link the elements of the text to their
semantic representation. An a priori built ontology requires to be
maintained, adapted and to grow to keep its usefulness. When this update
is made along the annotation process, by exploiting the annotated text
to enrich the model we can discuss a dynamicity of the annotation. We
can identify two processes closely related with this dynamicity, the
knowledge acquisition and the annotation process itself. On this talk we
will try present an overview on this processes and how they have been
approached before.
Mardi 3 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Généralisation des nombres et polynômes de Bernoulli aux cas multiples
Description: Olivier Bouillot Les nombres et polynômes de Bernoulli sont des objets classiques qui apparaissent respectivement lors du prolongement analytique des fonctions zêta de Riemann et de Hurwitz aux entiers négatifs.En lien avec la généralisation multiple de ces fonctions, les multizêtas et multizêtas de Hurwitz, nous allons généraliser les nombres et polynômes de Bernoulli au cas multiple.Bien qu'il n'y a pas unicité d'une telle généralisation, nous introduirons un exemple explicite et satisfaisant où nombres de propriétés importantes des polynômes de Bernoulli se transmettent au cas multiple.Au passage, cela permet de répondre à une question sur la renormalisation des multizêtas aux entiers négatifs.
Mercredi 4 Mars
Heure: 09:30 - 10:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On an Extension of Freeze LTL with Ordered Attributes
Description: Normann Decker We present an extension of Freeze LTL, a temporal logic equipped with registers,
over data words. Each position in a (multi-attributed) data word carries a
letter from a finite alphabet and assigns a data value to a fixed, finite set of
attributes. While reasoning on collections of data values is valuable for
expressing correctness properties of executions of dynamic programs the
satisfiability problem of Freeze LTL is undecidable if more than one register is
available or tuples of data values can be stored and compared arbitrarily. Our
extension therefore allows for specifying a dependency relation on attributes.
These dependencies introduce a restricted, yet flexible way of storing and
comparing collections of attribute values. This new dimension of flexibility is
orthogonal to, e.g., the number of registers or the available temporal
operators. In this setting we characterise precisely the type of dependency
relations that maintain decidability of the logic. To this end, we employ
reductions from and to nested counter systems. Moreover, by a complexity
theoretic characterisations we can show that our extension is strict and induces
a semantic hierarchy of logical fragments.
Vendredi 6 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Plotkin's call-by-value lambda-calculus from a linear-logical viewpoint
Description: Giulio Guerrieri We translate the terms of ordinary lambda-calculus into proof-nets
accordingly the Girard's call-by-value "boring'' encoding of intuitionistic
implication A->B = !A-o!B. We show that (1) the Plotkin's call-by-value
beta-reduction is (bi)simulated in proof-nets via cut-elimination; (2)
there is a sequentialization theorem that characterizes all and only the
proof-nets which are translations of some lambda-term; (3) the equivalence
relation on lambda-terms which identifies lambda-terms having the same
translation in proof-nets is the call-by-value counterpart of Regnier's
sigma-equivalence and is not included in Plotkin's call-by-value
beta-equivalence. The semantics of lambda-terms is preserved by our
call-by-value sigma-equivalence.
Adding an oriented version of the call-by-value sigma-rules to the
call-by-value beta-reduction (and keeping the same syntax of ordinary
lambda-calculus) we preserve confluence and we get a call-by-value
operational characterization of solvable and potential valuable terms (this
is not possible in original Plotkin's call-by-value lambda-calculus).
Moreover, we give a semantic characterization of solvable and potential
valuable terms in a relational model, based on Linear Logic, satisfying the
Taylor expansion formula. As a technical tool, we also use a
resource-sensitive calculus in which the elements of the model are
definable.
Lundi 9 Mars
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sequence Classification Based on Delta-Free Sequential Patterns
Description: Pierre Holat Sequential pattern mining is one of the most studied and challenging tasks in data mining. However, the extension of well-known methods from many other classical patterns to sequences is not a trivial task. This talk presents a study of the notion of delta-freeness for sequences. While this notion has extensively been discussed for itemsets, the work described in this talk is the first to extend it to sequences. In this work, we define an efficient algorithm devoted to the extraction of delta-free sequential patterns. Furthermore, we show the advantage of the delta-free sequences and highlight their importance when building sequence classifiers, and we show how they can be used to address the feature selection problem in statistical classifiers, as well as to build symbolic classifiers which optimizes both accuracy and earliness of predictions.
Mardi 10 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Multiband Robust Optimization: theory and applications
Description: Fabio D'Andreagiovanni Over the last years, Robust Optimization (RO) has emerged as an effective and efficient
methodology to tackle data uncertainty in real-world optimization problems. RO takes into
account data uncertainty in the shape of hard constraints that restrict the feasible set and
maintain only robust solutions, i.e. solutions that remain feasible even when the values of the
input data change.
In this talk, we provide an overview of our research about theory and applications of RO.
Specifically, we present Multiband Robustness, a new model for RO that we recently
proposed to generalize and refine the classical Gamma-robustness model by Bertsimas and
Sim. The main aim of our new model is to provide a refined representation of arbitrary non-
symmetric distributions of the uncertainty, that are commonly present in real-world
applications. Such refined representation grants a reduction in conservatism of robust
solutions, while maintaining the accessibility and computational tractability that have been a
key factor of success of Gamma-robustness. We also provide an overview of applications of
the Multiband model to real-world problems that we have considered in past and ongoing
research and industrial projects.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Une généralisation des mots de Christoffel en dimension d.
Description: Sébastien Labbé In this work, we extend the definition of Christoffel words todirected subgraphs of the hypercubic lattice in arbitrary dimensionthat wecall Christoffel graphs. Christoffel graphs when $d=2$ correspond towell-known Christoffel words.We show that Christoffel graphs have similar properties to those ofChristoffel words: symmetry of their central part and conjugation withtheirreversal. Our main result extends Pirillo's theorem (characterization ofChristoffel words which asserts that a word $amb$ is a Christoffelword if andonly if it is conjugate to $bma$) in arbitrary dimension.In the generalization, the map $ambmapsto bma$ is seen as a flipoperation ongraphs embedded in $mathbb{Z}^d$ and the conjugation is a translation.We show that a fully periodic subgraph of the hypercubic lattice is atranslate of its flip if and only if it is a Christoffel graph.This is joint work with Christophe Reutenauer.Preprint is available at http://arxiv.org/abs/1404.4021.
Jeudi 12 Mars
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Extraction de motifs graduels pour le résumé de données numériques
Description: Amal Oudni Les résumés linguistiques constituent une représentation linguistique décrivant
un ensemble de données numériques en phrases simples, compréhensibles et facilement interprétables.
Cet exposé se concentre sur les résumés linguistiques sous une forme particulière,
appelée motifs graduels, exprimant des corrélations de co-variations des valeurs
des attributs : on peut les illustrer pa r un exemple du type « plus l'âge du père
est avancé à la naissance des enfants, plus le risque d'autisme chez les enfants augmente ».

Lors de mon exposé, je présenterai trois types de contextualisation de ces motifs graduels.
Dans un premier temps, je décrirai le problème de motifs graduels contradictoires et une
nouvelle approche permettant d’éviter toute ambiguïté entre motifs validés.
Je présenterai ensuite la caractérisation des motifs graduels qui permet de faciliter
l'interprétation des motifs générés en grand nombre en introduisant une nouvelle clause
linguistiquement introduite par l'expression « surtout si ».
Je terminerai par la présentation d’une contextualisation qualifiant le mode de dépendances
graduelles, en introduisant la notion d'accélération par rapport aux autres attributs.

Pour chacune des formes de motifs enrichis extraits, je présenterai une formalisation
de la sémantique et l'interprétation souhaitées, des mesures de qualité pour évaluer
et quantifier la validité des motifs proposés, ainsi que des algorithmes efficaces
d'extraction automatique de ces motifs maximisant les critères de qualité définis.
Heure: 16:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Building Bridges Between Sets of Partial Orders
Description: Hernán Ponce de León Partial orders are a fundamental mathematical structure capable of representing concurrency and causality on a set of atomic events. In many applications it is essential to consider multiple partial orders, each representing a particular behavioral scenario or an operating mode of a modeled system.

In this talk I will present two mathematical formalisms capable of the compressed representation of sets of partial orders: Labeled Event Structures (LESs) and Conditional Partial Order Graphs (CPOGs). I will demonstrate their advantages and disadvantages and propose efficient algorithms for transforming of a set of partial orders from a given compressed representation in one formalism into an equivalent representation in another formalism without the explicit enumeration of each scenario. These algorithms make use of an intermediate mathematical formalism, which we call Conditional Labeled Event Structures (CLESs), that combines the advantages of LESs and CPOGs.

This is joint work with Andrey Mokhov (Newcastle University)
Vendredi 13 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Functors are Type Refinement Systems
Description: Noam Zeilberger The standard reading of type theory through the lens of category
theory is based on the idea of viewing a type system as a category of
well-typed terms. In this joint work with Paul-André Melliès we propose a basic revision of this reading: rather
than interpreting type systems as categories, we describe them as
functors from a category of typing derivations to a category of
underlying terms. Then, turning this around, we explain how in fact
*any* functor gives rise to a generalized type system, with an
abstract notion of typing judgment, typing derivations and typing
rules. This leads to a purely categorical reformulation of various
natural classes of type systems as natural classes of functors.

In the talk I want to motivate and introduce this general framework
(which can also be seen as providing a categorical analysis of
_refinement types_), and as a larger example give a sketch of how the
framework can be used to formalize an elegant proof of a coherence
theorem by John Reynolds. If time permits, I will also describe some
of the natural questions raised by this perspective that are the
subject of ongoing research.
Mardi 17 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: ALEA, au CIRM (16-20 mars)
Description: Journées ALEA
Jeudi 19 Mars
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Calcul efficace de la stabilité des concepts formels
Description: Sadok BEN YAHIA Dans l'ère des données massives, l'alliance de la qualité avec l'efficience pour la sélection des concepts formels « intéressants » serait une condition sine qua non. Dans ce cadre, la mesure de stabilité, de concepts formels, indiquerait dans quelle mesure l'intension de ce concept est liée à la présence d'objets particuliers dans son extension. Un concept stable possède, ainsi, une existence d'autant plus « réelle » que son intension ne dérive pas fortuitement d'une description bruitée de ses objets. Ainsi, les concepts stables sont très intéressants à localiser dans beaucoup de domaines puisqu'ils sont résistants au bruit, e.g., détection de communautés stables, classification par des classes monothétiques/ polythétiques.

Cependant, le calcul de la stabilité serait très couteux, ie., exponentiel en fonction de la taille de l'extension du concept. En effet, il faudrait explorer l'espace de tous les sous-ensembles de l'extension à la recherche qui restent fidèles à l'intension du concept formel.

Dans ce séminaire, nous passons en revue les très peu nombreux travaux qui se sont intéressés au calcul de la stabilité des concepts formels (organisés sous forme de treillis ou non). Ensuite, nous présentons des travaux récents sur l'exploitation des propriétés de monotonie et d'anti-monotonies des éléments clés dans l'espace de recherche. Ainsi, la saturation des cliques maximales non génératrices permet de traiter des espaces avoisinant les 215000. Nous montrons aussi que les identités d'inclusion/ exclusion servent au calcul efficace des stabilités des concepts formels organisés sous la forme d'un treillis.
Heure: 14:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Effective verification of low-level software with nested interrupts
Description: Lihao Liang Interrupt-driven software is difficult to test and debug, especially when
interrupts can be nested and subject to priorities. Interrupts can arrive
at arbitrary times, leading to an explosion in the number of cases to be
considered. We present a new formal approach to verifying interrupt-driven
software based on symbolic execution. The approach leverages recent
advances in the encoding of the execution traces of interacting, concurrent
threads. We assess the performance of our method on benchmarks drawn from
embedded systems code and device drivers, and experimentally compare it to
conventional formal approaches that use source-to-source transformations.
Our experimental results show that our method significantly outperforms
conventional techniques. To the best of our knowledge, our technique is the
first to demonstrate effective formal verification of low-level embedded
software with nested interrupts.

Joint work with
Daniel Kroening, Tom Melham, Peter Schrammel and Michael Tautschnig
Vendredi 20 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An infinitary model of linear logic
Description: Charles Grellois We construct an infinitary variant of the relational model of linear logic, where the exponential modality is interpreted as the set of finite or countable multisets. We explain how to interpret in this model the fixpoint operator Y as a Conway operator alternatively defined in an inductive or a coinductive way. We then extend the relational semantics with a notion of color or priority in the sense of parity games. This extension enables us to define a new fixpoint operator Y combining both inductive and coinductive policies. We conclude by sketching the connection between the resulting model of lambda-calculus with recursion and higher-order model-checking.
Mardi 24 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Unit Commitment problems: approaches and solution algorithms
Description: Claudio Gentile The Unit Commitment is a the problem to manage a set of power generating units of different types over a short time horizon.
Unit Commitment is formulated as a Mixed Integer Nonlinear Programming problem. It requires special techniques to handle both the large size of the instances to be solved and the nonlinearity of the objective function.
Two main approaches have been used in its solution: the Lagrangian Relaxation coupled with primal heuristics and MILP approximations. We discuss some new advancements for both approaches.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Automates d'arbres
Description: Gwendal Collet
Mercredi 25 Mars
Heure: 14:00 - 15:00
Lieu: Amphi A
Résumé: Extending Petri Nets with Object-Orientation
Description: Charles Lakos This seminar will introduce the formalism of Petri Nets and their use in modelling and analysing concurrent systems. It will briefly mention some of the extensions of Petri Nets to achieve greater descriptive comfort. It will then report on work over a number of years to extend Petri Nets with Object-Oriented features, thereby making it easier to define polymorphic modules and to capture incremental development. The seminar will also describe the properties of such nets and the analysis possibilities.
Mardi 31 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TASEP
Description: Erik Aas
Jeudi 2 Avril
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Extraction non supervisée de classes évolutives à partir de données temporelles
Description: Allou Samé La classification de données évoluant au cours du temps constitue une problématique centrale dans de nombreuses applications. Dans ce cadre, les paramètres des classes doivent pouvoir s’adapter à l’évolution potentiellement non stationnaire des données. Cet exposé montrera comment les mélanges de lois peuvent être exploités, conjointement avec les modèles à espace d’état (filtre de Kalman), pour atteindre cet objectif. Partant de ce formalisme, un algorithme EM variationnel et sa version online seront détaillés. Ceux-ci seront illustrés sur des données simulées et des données réelles dans le cadre d’un problème de diagnostic dans le secteur ferroviaire.
Mardi 7 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Structure algébrique des opérateurs de Fliess.
Description: Loïc Foissy
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Présoutenance de thèse : A left/right dynamic on permutations
Description: Quentin de Mourgues Soit s une permutation dans Sigma_n.Soit i(s)=s(1), j(s)=s^{-1}(1),Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes).On definit L et R comme suit:L(s) = C_{j(s)}.s etR(s) = s.C_{i(s)}^{-1}Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes.Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.
Heure: 16:00 - 19:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Présoutenance de thèse : Tilings
Description: Alexandra Ugolnikova
Jeudi 9 Avril
Heure: 14:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Enhanced Distributed Behavioral Cartography of Parametric Timed Automata
Description: Hoang Gia Nguyen Parametric timed automata (PTA) allow the specification and verification of timed systems incompletely specified, or subject to future changes. The behavioral cartography splits the parameter space of PTA in tiles in which the discrete behavior is uniform. Applications include the optimization of timing constants, and the measure of the system robustness w.r.t. the untimed language. Here, we present enhanced distributed master-worker algorithms to compute the cartography efficiently. Experimental results show that our new algorithms significantly outperform previous distribution techniques.
Mardi 14 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Diamètre et hamiltonicité des associaèdres de graphe
Jeudi 16 Avril
Heure: 14:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: "Formalising Concurrent UML State Machines Using Coloured Petri Nets"
Description: Mohamed Mahdi Benmoussa While UML state machines are widely used to specify dynamic systems behaviours, their semantics is described informally, which prevents the complex systems verification.
In this paper, we propose a formalisation of concurrent UML state machines using coloured Petri nets.
We consider in particular concurrent aspects (orthogonal regions, forks, joins, shared variables), the hierarchy induced by composite states and their associated activities, internal/external/local transitions, and entry/exit/do behaviours.
Vendredi 17 Avril
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: gdt Homotopy Type Theory - séance 1
Description: Andrew Polonsky The first of a little series of talks on Homotopy Type Theory (i.e., higher-order algebraic treatment of the notion of equality in dependant type theory).

Logical relations are a technique for proving meta-theoretic
properties of type systems.
In recent years, they have received a lot of attention as it became
clear that logical relations give the most natural definition of
extensional equality in type theory.
A major open problem is to define a type system which contains
extensional equality as an internal type constructor. For this, it is
necessary to reflect the external logical relation back into the
syntax of the type language.
In this talk I will describe how to do this.
Mardi 21 Avril
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La tour de Hanoï, revue par Dudeney
Description: Thierry Bousch Dans la version classique de "la Tour de Hanoï", c'est-à-direavec trois aiguilles, on sait bien qu'on peut transférer N disquesd'une aiguille vers une autre en 2^N-1 mouvements, et que ce nombreest minimal. Ajoutons une quatrième aiguille: quel est alors le nombreminimum de mouvements nécessaires pour transférer N disques d'uneaiguille vers une autre? Etrangement, ce problème posé il y a plusd'un siècle par le puzzliste anglais Henry Ernest Dudeney n'a étérésolu que tout récemment. Et pour d'autres variantes de la Tourde Hanoï, avec davantage d'aiguilles ou des restrictions sur lesmouvements, le problème est largement ouvert.voir aussi l'article sur le site du CNRS
Mardi 28 Avril
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Exact Algorithms for Nonconvex Quadratic Integer Optimization
Description: Christoph Buchheim The talk addresses the problem of minimizing a quadratic objective function over integer variables. Even in the most simple case of binary or box-constrained integer variables, such problems are very hard to solve in theory and in practice. In fact, the problem remains NP-hard both in the case of a convex objective function over binary variables (then being equivalent to max-cut) and in the case of a non-convex objective function over the unit cube (the so-called BoxQP).

After shortly reviewing some classical approaches for quadratic discrete optimization, we present two recent methods that are specifically designed for the nonconvex case, aiming at relaxations that jointly address the nonconvexity of the objective function and the nonconvexity of the discrete variable domains. While the first approach results in a semidefinite relaxation of the problem, the second approach uses ellipsoidal relaxations; both approaches can be embedded into branch-and-bound schemes. We present experimental results for the resulting algorithms, showing that the SDP-based approach yields very strong dual bounds that however take more time to be computed, while the second approach based on ellipsoidal relaxations is able to enumerate a large number of nodes in a short time due to a sophisticated preprocessing phase. The resulting total running times are comparable; both approaches however significantly outperform standard software such as Couenne or BARON.
Mardi 5 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Comptage et énumération de surfaces plates, formes quasimodulaires
Description: Samuel Lelièvre
Jeudi 7 Mai
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Présoutenance de thèse : A left/right dynamic on permutations
Description: Quentin de Mourgues Soit s une permutation dans Sigma_n.Soit i(s)=s(1), j(s)=s^{-1}(1),Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes).On definit L et R comme suit:L(s) = C_{j(s)}.s etR(s) = s.C_{i(s)}^{-1}Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes.Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.
Heure: 16:00 - 19:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Présoutenance de thèse : Tilings
Description: Alexandra Ugolnikova
Lundi 11 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Structured Prediction, Optimization and Deep Syntax
Description: Caio Filippo Corro A sequence of words is not a sufficient representation for efficient
processing of natural languages. In order to extract information from
sentences, we need to decode their underlying abstract structure(s).
Unfortunately, grammar formalisms that are able to properly capture
complicated phenomena encountered in natural languages (wh-movements,
cross-serial dependencies,...) have a repelling complexity. The work in
this thesis will focus on developing efficient parsing algorithms for
various formalisms (TAG, LCFRS, RCG) using optimization methods
(Lagrangian relaxation, dual decomposition).
Mardi 12 Mai
Heure: 11:00 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Various aspects of automaton synchronization
Description: Mikhael Berlinkov
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: EXACT APPROACHES TO THE NETWORK DESIGN PROBLEM WITH RELAYS
Description: Ivana Ljubic This work considers the Network Design Problem with Relays (NDPR). The
NDPR arises in the context of network design when given node-pairs need
to communicate with each other, but, due to signal deterioration,
communication paths have to respect given distance limits. To cover
longer distances, equipment for signal regeneration (i.e., relays) may
be required. To enable required communications, one has to upgrade the
network: by installing new links, by installing relays on the existing
network, or by a combination of both. Besides applications in network
design, the NDPR arises in the context of e-mobility where relays model
charging stations for electric cars and edge costs correspond to road
tolls.

In contrast to previous work on the NDPR, which was mainly focused on
heuristic approaches, we propose new exact approaches based on different
mixed integer linear programming formulations for the problem. We
develop Branch-and-Price and Branch-Price-and-Cut algorithms that build
upon models with an exponential number of constraints and variables. In
a computational study, we analyze the performance of these approaches
for instances with different characteristics.

This is a joint work with M. Leitner, M. Riedler and M. Ruthmair
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Énumération d'automates minimaux et fonctions de parking
Description: Jean-Baptiste Priez
Mardi 19 Mai
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Approximating the energy storage problem and other continuous dynamic programs
Description: Giacomo Nannicini We study the problem of optimally managing a source of renewable
energy connected to the power grid, a battery, and potentially a
household or some other form of energy sink. This problem can be
naturally cast as a dynamic program. We propose a model for this
problem that subsumes other models in the literature, and we analyze
its complexity, showing that in the deterministic setting the problem
is solvable in polynomial time, but it becomes #P-hard in the
stochastic setting. A variant of the problem that is commonly
encountered in practice (i.e. the one where selling energy to the
power grid is not allowed) admits a Fully Polynomial Time
Approximation Scheme (FPTAS) if the energy levels are discretized;
but what about the more natural case where energy is considered a
continuous variable? We show that in this case, the problem belongs to
a class of convex continuous dynamic programs that admits neither a
multiplicative nor an additive approximation. We then show that we can
construct a novel type of approximation scheme, where additive and
multiplicative approximation are required at the same time but both
can be arbitrarily small. We discuss a preliminary computational
evaluation of this new type of approximation scheme for continuous
convex dynamic programs, showing its potential.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Explicit forms and combinatorial content of Levy stable distributions
Description: Katarzyna Górska
Jeudi 21 Mai
Heure: 14:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Reachability Preservation Based Parameter Synthesis for Timed Automata
Description: Étienne André The synthesis of timing parameters consists in deriving conditions
on the timing constants of a concurrent system such that it meets its
specification.
Parametric timed automata are a powerful formalism for parameter
synthesis, although most problems are undecidable.
We first address here the following reachability preservation
problem: given a reference parameter valuation and a (bad) control
state, do there exist other parameter valuations that reach this control
state iff the reference parameter valuation does?
We show that this problem is undecidable, and introduce a procedure
that outputs a possibly underapproximated answer.
We then show that our procedure can efficiently replace the
behavioral cartography to partition a bounded parameter subspace into
good and bad subparts; furthermore, our procedure can even outperform
the classical bad-state driven parameter synthesis semi-algorithm,
especially when distributed on a cluster.
Mardi 26 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Efficient Algebraic Diagonals and Walks
Description: Louis Dumont The diagonal of a multivariate power series F is the univariate power series Diag F generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. Westudy algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag F is an algebraic function. We propose an algorithm that computes an annihilating polynomial forDiag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. Throughout the talk, we use a common problemof counting certain lattice walks to illustrate the capacities and limits of our tools.
Mercredi 27 Mai
Heure: 14:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Logics via algebras and substitutions
Description: Antonino Salibra In this talk we present a translation of formulas and models of classical and non-classical logics
into factor algebras. The correspondence:
Propositional variables --- operator of decompositions
Logical operations --- substitutions
Formulas --- algebraic terms
Models --- factor algebras,
provides a uniform calculus of provability for all the logics which admit the translation.
Many examples will be discussed:
classical logic, intuitionistic logic, linear logic, many-valued logics.