Lieu : Salle de séminaire 4B125 (bâtiment Copernic)

We study indexing data structures for substring compression problems.Given an input text \(T\), a substring compression problem for a compression scheme \(C\) and a query interval \([i..j]\) asks to compute the compressed form of the substring \(T[i..j]\) with respect to \(C\) — that is, to apply \(C\) to \(T[i..j]\), which we write as \(C(T[i\ldots j])\). While \(T\) and \(C\) are given in advance, the interval \([i\ldots j]\) is specified at query time.

This setting allows preprocessing \(T\) to facilitate efficient answers to substring compression queries under \(C\). Space- or time-optimal solutions are straightforward but impractical:

— A space-optimal solution applies \(C(T[i\ldots j])\) at query time, without any preprocessing (selecting the optimal implementation of \(C\) with respect to space).

— A time-optimal solution precomputes \(C(T[i\ldots j])\) for all text positions \(i, j\), but requires at least quadratic space and preprocessing time.

Here, optimal time refers to linearity in the size of the compressed output. Thus, a natural question arises: Can we build an index over \(T\) that supports substring compression queries with near-optimal query time and subquadratic space?

In this talk, we explore approaches for compression schemes \(C\) related to the Lempel–Ziv 78 factorization, and outline promising directions for future research.

L’algèbre géométrique, ou algèbre de Clifford, offre un cadre unifié pour représenter et manipuler des objets géométriques de toute dimension. Des objets les plus simples comme les scalaires et les vecteurs, jusqu’aux bivecteurs et aux entités de dimensions arbitraires, elle permet de capturer à la fois la magnitude et l’orientation grâce à des opérations comme le produit scalaire, le produit extérieur et le produit géométrique. Cette présentation introduit ces concepts fondamentaux à travers des exemples intuitifs en 2D et 3D. Elle se conclut par une ouverture vers des algèbres plus avancées, telles que PGA (Projective Geometric Algebra), CGA (Conformal Geometric Algebra) et CCGA (Conic Conformal Geometric Algebra), etc. , qui élargissent ce formalisme en permettant de représenter de façon unifiée les intersections, les transformations et les courbes de degré arbitraire

Geometric Algebra, or Clifford Algebra, provides a unified framework for representing and manipulating geometric objects of any dimension. From scalars and vectors to bivectors and higher-grade elements, it captures both magnitude and orientation through operations like the inner, outer, and geometric products. This presentation introduces these core concepts with intuitive examples in 2D and 3D. We conclude by opening the door to more advanced geometric algebras—such as Projective Geometric Algebra (PGA), Conformal Geometric Algebra (CGA), and Conic Conformal Geometric Algebra (CCGA)—which extend the power of this formalism to model intersections, transformations, and arbitrary-degree curves in a unified way.

We investigate two-player win/lose games over finite graphs. In all generality, these games are concurrent, i.e. at each state of the graph, there is a concurrent interaction between the two players to determine the next state visited. In the special case where, at every state of the graph, there are no real concurrent interaction, i.e. only one player is truly playing, the game is turn-based. Various desirable properties hold on turn-based games, but do not on arbitrary concurrent games; e.g. there exist subgame optimal strategies in all prefix-independent turn-based games, while there do not in very simple prefix-independent concurrent games. A possible way to circumvent this issue is to define a subclass of concurrent games, that is a proper superclass of turn-based games, while enjoying several of their nice properties. The goal of this talk is to introduce such a subclass of concurrent games, namely finitely maximizable games, and to show step by step how we came up with this definition. The novel way that we use to define such a subclass of well-behaving concurrent games constitutes a promising approach for investigating more general concurrent games, such as non-antagonistic two-player games, or even multi-player games.