Tag : Français

Dans cet exposé, nous étudions une distribution non-uniforme sur les permutations (de taille fixée quelconque), où la probabilité d’une permutation est proportionnelle à \(\theta^{rec}\), où \(rec\) désigne le nombre de records (ou maxima de gauche à droite).

La définition de ce modèle de permutations aléatoires non-uniformes est motivée par des questions d’analyse d’algorithmes. En effet, lors de l’analyse d’algorithmes fonctionnant sur des tableaux de nombres (modélisés par des permutations), on suppose généralement une distribution uniforme sur l’ensemble des entrées possibles. Cependant, les données réelles sur lesquelles ces algorithmes sont utilisés sont rarement uniformes et présentent souvent un biais vers les tableaux « partiellement triés ». Notre modèle rend compte de ce biais vers les tableaux « partiellement triés », tout en restant maniable du point de vue de l’analyse des algorithmes.

Nous obtenons trois types de résultats. Premièrement, nous présentons plusieurs générateurs aléatoires efficaces de permutations sous cette distribution. Deuxièmement, nous analysons le comportement de certaines statistiques classiques de permutation, dont certaines ont des applications dans l’analyse des algorithmes. Enfin, nous décrivons la « forme typique » des permutations dans notre modèle, à l’aide de leur permuton limite (déterministe).

Il s’agit d’un travail en collaboration avec Nicolas Auger, Cyril Nicaud et Carine Pivoteau.

Dans de nombreux pays, l’union est divisée en États, et le nombre de députés au congrès fédéral dépend de chaque État. Imaginons que chaque année, un·e député·e soit élu·e pour présider le congrès. Le défi consiste à attribuer ce rôle de manière à ce qu’à tout moment, le nombre cumulé de présidences provenant de chaque État reste proportionnel à son poids attribué. Ce problème est connu sous le nom de problème d’attribution de la présidence. Dans cet exposé, nous introduirons une métrique permettant de quantifier l’équité dans ce contexte et expliquerons son lien avec la dynamique symbolique. Cette présentation constituera également une introduction aux systèmes dynamiques symboliques.

We present an algorithm to construct the binary partition tree by altitude ordering based on Borvka’s minimum spanning tree strategy. The binary partition tree by altitude ordering is a data structure to represent an image in the form of a hierarchy of segmentations that is widely used in mathematical morphology processing. Recently, the authors of PANDORA have proposed a novel parallel algorithm for computing single linkage clustering from the minimum spanning tree of a point cloud on a GPU. We show that their method can indeed be nicely cast in the framework of watershed cuts and waterfalls for computing the binary partition tree by altitude ordering. More precisely, the method consists in performing a sequence of watershed cuts-basins contractions, seen as a variant of Borvka’s algorithm with a complexity of O(n log(n)), followed by a dedicated postprocessing. Furthermore, we show that this algorithm can be extended to process any edge-weighted graphs and not only minimum-spanning trees. These results open a new path towards massively parallel algorithms for hierarchical watershed algorithms

Les contraintes d’intégrité ont un rôle majeur pour garantir la qualité des données. Si les langages de contraintes ont été largement étudiés dans le cadre des bases de données relationnelles, leur expressivité comparative dans le cadre des bases de données graphes reste peu explorée. En particulier, l’interaction entre la topologie du graphe et les valeurs des données introduit de nouveaux défis de modélisation et de raisonnement.
Pendant ce séminaire, je présenterai une étude rigoureuse de l’expressivité du langage PG-Keys, introduit récemment. Nous le comparons à deux langages de contraintes fondamentaux pour les bases de données graphes, les Graph Functional Dependencies (GFDs) et les Graph Generating Dependencies (GGDs), dans un cadre unificateur paramétrant ces langages selon une composante topologique et une composante logique, et les étendant lorsque nécessaire. Nous identifions des fragments ayant de bons comportements, établissons des traductions syntaxiques, et montrons des résultats de séparation, ce qui permet de donner une hiérarchie complète et stricte d’expressivité. Ces résultats clarifient le rôle des PG-Keys parmi les langages de contraintes.
Je me concentrerai sur le cas des requêtes conjonctives avec prédicats d’égalité et d’inégalité, même si nos résultats peuvent être naturellement étendus à d’autres cadres, comme celui des regular path queries, je présenterai des résultats de séparation sur nos fragments, et donnerai des réécritures qui établissent la hiérarchie entre GFDs, GGDs, et PG-Keys.

ENGLISH VERSION

Integrity constraints play a central role in ensuring data quality. While constraint languages have been extensively studied for relational databases, the comparative expressiveness of constraint languages for property graph databases remains underexplored. In particular, the interplay between graph topology and data values introduces new modeling and reasoning challenges.
In this talk, I will present a principled study of the expressive power of the recently introduced PG-Keys language. We compare it with two core property graph constraint languages, Graph Functional Dependencies (GFDs) and Graph Generating Dependencies (GGDs), within a unifying framework that parametrizes these languages by topological constraints and logical predicates, and extends them when needed. We identify well-behaved fragments, establish syntactic translations, and prove separation results, yielding a complete and strict hierarchy of expressive power. The results clarify the role of PG-Keys in the landscape of property graph constraints.
I will focus on conjunctive queries with equality and inequality, although our results naturally extend to richer settings such as regular path queries, present separation results concerning our well-behaved fragments, and give rewritings establishing the hierarchy between GFDs, GGDs, and PG-Keys.

Contrary to the case of automata over finite words, omega-regular languages do not admit unique, minimal deterministic automata. Yet, not all hope is lost! In this talk I will introduce layered automata, a formalism to capture a subclass of alternating parity automata, extending deterministic ones. We show:
(1) All layered automata are history-deterministic and 0-1-probabilistic.
(2) Each omega-regular language can be recognised by a unique minimal layered automaton, admitting a congruence-based description.
(3) This minimal automaton is computable in polynomial time from a given layered automaton.

This is work in progress with Christof Löding and Igor Walukiewicz.

This thesis, situated in the digital humanities, focuses on the study of drama, and more particularly, on the design and evaluation of models to represent play texts, and perform automatic comparisons between them.

On the literary side, several digital corpora are used, with a particular attention paid to classical theater, and French 17\textsuperscript{th} century European theater. Among the most prevalent corpora used are the Hyperpièces dataset, comprising more than 500 pairs of similar plays, and files from the Dracor project, a European database of XML-TEI plays, totaling nearly 2000 plays for its French version. We also achieve corpus augmentation by porting 1350 new plays to XML-TEI, from the Theatre-Documentation website, enriching our corpus with 18\textsuperscript{th} century productions.

These corpora are used throughout our work as test data for the comparison algorithms we design. Our algorithms both leverage structural and semantic similarities to compare plays.
For structural comparison, we give an overview of the existing models, most notably character networks. We introduce the use of the parameterized words formalism to detect character renamings between plays. We give a complete study of the theoretical complexity of approximate parameterized matching, under several edit distances variants. We prove the NP-completeness of a large class of these problems, and give heuristics and approximate algorithms to solve them. We also provide exact algorithms for these problems, in the form of Max-SAT encodings. We introduce a generalization of parameterized matching using sets, and study the associated problems. Finally, we detail the usage of parameterized matching for the study of drama on a curated multilingual corpus and discuss the strengths and limitations of the technique.

To perform semantic comparisons, we use several NLP models to design algorithms to automatically generate alignments between plays. We introduce and analyze a model using TF-IDF metrics to compare character networks, and retrieve character renamings. We propose methods for distant reading comparisons using indicators of increasing complexity, using Word2Vec methods. Using BERT models to compare sentences, we introduce a method to produce alignments between plays. We perform close reading analysis on several of the generated alignments, and analyze the performance of the algorithms.

Binary decision diagrams are a family of data structures that can be used to efficiently represent a Boolean function. They were popularized by Randal Bryant in 1986 and have since been used in numerous applications.

In this presentation, we will address some counting issues related to these structures, focusing on the best-known variant, called reduced ordered decision diagram (ROBDD). The main result is to provide a polynomial algorithm for calculating the number of ROBDDs with \(k\) variables of size \(n\) (the size being the number of decision nodes in the structure). After much effort, we were able to apply the method for 16 variables (it is important to remain modest).

As an application of these results, we propose the first polynomial method for uniform random generation (for size) of ROBDDs.

« Strategic voting » or manipulability by coalition, occurs when a group of voters can obtain an election outcome they prefer by not voting sincerely. Among the various existing voting systems, Instant-Runoff Voting (IRV) is reputed to be more resistant to strategic voting than others. IRV is used for several presidential and parliamentary elections around the world (Australia, India, Ireland, Papua New Guinea, Sri Lanka). We study the probability that strategic voting is ineffective under IRV when voters randomly draw their preferences among the candidates. This work combines social choice theory, probability, and analytic combinatorics.

Based on joint work with François Durand and Guillem Perarnau

Ce séminaire est motivé par des échanges récents au laboratoire à propos des politiques de libre accès de certains éditeurs (publishers) et le paiement des charges de publication (Access Processing Charges, APCs).
Nous rappellerons les principes du libre accès à la littérature scientifique de la Budapest Open Access Initiative (BOAI, 2002), le besoin de mieux comprendre le droit d’auteur et les avancées plus récentes sur le besoin de modifier l’évaluation de la recherche dans le cadre de la Science ouverte.

La présentation de T. Gomez-Diaz sera suivie d’une intervention A. Drouet, Responsable du Service VPR-IST, et d’un espace d’échange et questions

Si la géométrie euclidienne est étudiée depuis des millénaires, la géométrie discrète est, elle, une géométrie beaucoup plus jeune puisqu’elle ne s’est développée que quelques décennies plus tôt, motivée par l’avènement du traitement d’images sur ordinateurs nécessitant la manipulation de structures de données finies.
Un sujet des sujets d’intérêt fondamental de cette géométrie est notamment le processus de discrétisation, permettant la conversion d’un objet réel à un objet dans la grille discrète : comment garantir la bonne préservation des propriétés topologiques et géométriques des formes discrétisées ? Bien que différents processus de discrétisation existent pour répondre à cette problématique, la fidélité de la discrétisation dépend fortement des hypothèses de régularité de la forme originale. A ce titre, plusieurs classes de formes ont été proposées, émettant des hypothèses sur les formes continues afin d’en contrôler le bord et, ainsi, améliorer leur discrétisation.
Parmi elles, nous nous intéressons aux courbes à courbure totale localement bornées (CTLB) : une classe de formes suffisamment vaste pour inclure un grand nombre de polygones et de formes régulières, mais suffisamment restreintes pour garantir la bonne préservation de leurs caractéristiques géométriques et topologiques sous discrétisation. Si les courbes CTLB ont déjà été largement étudiées dans le cas de la 2D, leur extension aux dimensions supérieures n’est pas triviale. Nous introduisons ainsi les surfaces CTLB, une généralisation des courbes CTLB à la 3D, et présentons leurs premiers résultats dans l’espace euclidien.