We introduce open parity games, which is a compositional approach to parity games. This is achieved by adding open ends to the usual notion of parity games. We introduce the category of open parity games, which is defined using standard definitions for graph games. We also define a graphical language for open parity games as a prop, which have recently been used in many applications as graphical languages. We introduce a suitable semantic category inspired by the work by Grellois and Melliès on the semantics of higher-order model checking. Computing the set of winning positions in open parity games yields a functor to the semantic category. Finally, by interpreting the graphical language in the semantic category, we show that this computation can be carried out compositionally. We also discuss current work on an efficient implementation of a compositional solver of graph games.
Monadic interpreters have been used for a long time as a mean to embed arbitrary computations in purely functional contexts. At its core, the idea is elementary: the object language of interest is implemented as an executable interpreter in the host language, and monads are simply the abstraction used to embed features such as side effects, failure, non-determinism. By building these interpreters on top of the free monad, the approach has offered a comfortable design point notably enabling an extensible syntax, reusable modular components, structural compositional definitions, as well as algebraic reasoning. The approach has percolated beyond its programming roots: it is also used as a way to formalize the semantics of computational systems, programming languages notably, in proof assistants based on dependently typed theories. In such assistants, the host language is even more restricted: programs are all pure, but also provably terminating. Divergent programs can nonetheless be embedded using for instance the Capretta monad: intuitively, a lazy, infinite (coinductive) tree models the dynamic of the computation. Interaction trees are a specific implementation, in the Coq proof assistant, of a set of tools realizing this tradition. They provide a coinductive implementation of the iterative free monad, equipped with a set of combinators, allowing notably for general recursion. Each iterator comes with its equational theory established with respect to a notion of weak bisimulation --- i.e. termination sensitive, but ignoring the amount of fuel consumed --- and practical support for equational reasoning. Further effects are implemented into richer monads via a general notion of interpretation, allowing one to introduce the missing algebras required for proper semantic reasoning. Beyond program equivalence, support for arbitrary heterogeneous relational reasoning is provided, typically allowing one to prove a compilation pass correct. Introduced in 2020, the project has spawned realistic applications --- they are used to model LLVM IR's semantics notably ---, as well as extensions to reduce the necessary boilerplate, or to offer proper support for non-determinism. In this talk, I will attempt to paint an illustrative overview of the core ideas and contributions constitutive of this line of work.
This talk proposes full convexity as an alternative definition of digital convexity, which is valid in arbitrary dimension. It solves many problems related to its usual definitions, like possible non connectedness or non simple connectedness, while encompassing its desirable features. Fully convex sets are digitally convex, but are also connected and simply connected. They have a morphological characterisation, which induces a simple convexity test algorithm. Arithmetic planes are fully convex too. Full convexity implies local full convexity, hence it enables local shape analysis, with an unambiguous definition of convex, concave and planar points. We propose also a natural definition of tangent subsets to a digital set. It gives rise to the tangential cover in 2D, and to consistent extensions in arbitrary dimension. We present two applications of tangency: the first one is a simple algorithm for building a polygonal mesh from a set of digital points, with reversibility property, the second one is the definition and computation of shortest paths within digital sets. In a second part of the talk, we study the problem of building a fully convex hull. We propose an iterative operator for this purpose, which computes a fully convex enveloppe in finite time. We can even build a fully convex enveloppe within another fully convex set (a kind of relative convex hull). We show how it induces several natural digital polyhedral models, whose cells of different dimensions are all fully convex sets. As perspective to this work, we study the problem of fully convex set intersection, which is the last step toward a full digital analogue of continuous convexity.
L'allostérie est un phénomène d'importance fondamentale en biologie qui permet la régulation de la fonction et l'adaptabilité dynamique des enzymes et protéines. Malgré sa découverte il y a plus d'un siècle, l'allostérie reste une énigme biophysique, parfois appelée « second secret de la vie ». La difficulté est principalement associée à la nature complexe des mécanismes allostériques qui se manifestent comme l'altération de la fonction biologique d'une protéine/enzyme (c-à-d. la liaison d'un substrat/ligand au site active) par la liaison d'un « autre objet » (``allos stereos'' en grec) à un site distant (plus d'un nanomètre) du site actif, le site effecteur. Ainsi, au cœur de l'allostérie, il y a une propagation d'un signal du site effecteur au site actif à travers une matrice protéique dense, où l'un des enjeux principal est représenté par l'élucidation des interactions physico-chimiques entre résidus d'acides aminés qui permettent la communication entre les deux sites : les chemins allostériques. Ici, nous proposons une approche multidisciplinaire basée sur la combinaison de méthodes de chimie théorique, impliquant des simulations de dynamique moléculaire de mouvements de protéines, des analyses (bio)physiques des systèmes allostériques, incluant des alignements multiples de séquences de systèmes allostériques connus, et des outils mathématiques basés sur la théorie des graphes et d'apprentissage automatique qui peuvent grandement aider à la compréhension de de la complexité des interactions dynamiques impliquées dans les différents systèmes allostériques. Le projet vise à développer des outils rapides et robustes pour identifier des chemins allostériques inconnus. La caractérisation et les prédictions de points allostériques peuvent élucider et exploiter pleinement la modulation allostérique dans les enzymes et dans les complexes ADN-protéine, avec de potentielles grandes applications dans l'ingénierie des enzymes et dans la découverte de médicaments.
Reconstructing digital humans is a key problem in 3D vision with many applications for autonomous driving, robotics, Virtual and Augmented Reality and has attracted a lot of research for decades. In this talk I will discuss about non-invasive hardware-based solutions to jointly capture human body shape and motion. We will see that efficient modelisation of human body deformation is key to enable real-time tracking. I will also present recent works about AI-based solutions for both human shape reconstruction from a single color images and full body animation with minimum driving signal such as a skeleton. We will see that deep learning opens new perspectives and possibilities to create real digital humans and animate them in the digital spaces.
Constructive modal logics are obtained by adding to intuitionistic logic a minimal set of axioms for the box and diamond modalities. During this talk I will present two new semantics for proofs in these logics. The first semantics captures syntactically the proof equivalence enforced by non-duplicating rules permutations, and it is defined by means of the graphical syntax of combinatorial proofs. The second semantics captures a coarse notion of proof equivalence, and it is given by means of winning innocent strategies of a two-player game over graphs encoding formulas. This latter semantics is provided with a notion of compositionality and indeed defines the first concrete model of a denotational semantics for these logics.
La théorie des types de Martin-Löf compte parmi les instances les plus abouties de la correspondance preuves-programmes : les types dépendants et les types inductifs permettent de spécifier des propriétés complexes aux programmes, et la hiérarchie d'univers fournit une puissance logique suffisante pour encoder l'essentiel des constructions mathématiques -- ce qui en fait un outil de choix pour les assistants de preuves! Toutefois, l'égalité inductive fournie par la théorie n'est pas très adaptée au raisonnement mathématique, car elle encode l'égalité des programmes (intensionnalité'') et non l'égalité des comportements (extensionnalité''). Cela implique des conséquences désagréables : il est impossible de prouver que les fonctions qui à n associent respectivement n+2 et 2+n sont égales, il est impossible de quotienter un type par une relation, etc. C'est précisément pour remédier à ça qu'a été développée l'idée de théorie des types observationnelle, qui fournirait ces principes d'extensionnalité souhaitables, tout en préservant la correspondance preuves-programmes et les propriétés qui en font un outil si pratique (normalisation, canonicité, décidabilité du typage…). Dans cet exposé, je présenterai TT^obs, une altération conceptuellement simple de la théorie de Martin-Löf qui en fait une théorie observationnelle complète, je montrerai quelques exemples d'utilisation, et j'ébaucherai sa méta-théorie si le temps le permet.
Tout polynôme multivarié P(X_1,...,X_n) peut être écrit comme une somme de monômes, i.e., une somme de produits de variables et de constantes du corps. La taille naturelle d'une telle expression est le nombre de monômes. Mais, que se passe-t-il si on rajoute un nouveau niveau de complexité en considérant les expressions de la forme : somme de produits de sommes (de variables et de constantes) ? Maintenant, il devient moins clair comment montrer qu'un polynôme donné n'a pas de petite expression. Dans cet exposé nous résoudrons exactement ce problème. Plus précisément, nous prouvons que certains polynômes explicites n'ont pas de représentations ``somme de produits de sommes'' (SPS) de taille polynomiale. Nous pouvons aussi obtenir des résultats similaires pour les SPSP, SPSPS, ... etc. pour toutes les expressions de profondeur constante.
We introduce a new formalisation of language computation, called keyboards. We consider a set of atomic operations (writing a letter, erasing a letter, going to the right or to the left) and we define a keyboard as a set of finite sequences of such operations, called keys. The generated language is the set of words obtained by applying some non-empty sequence of those keys. Unlike classical models of computation, every key can be applied anytime. We define various classes of languages based on different sets of atomic operations, and compare their expressive powers. We also compare them to rational, context-free and context-sensitive languages. We obtain a strict hierarchy of classes, whose expressiveness is orthogonal to the one of the aforementioned classical models. We also study closure properties of those classes, as well as fundamental complexity problems on keyboards.
We study the decomposition of multivariate polynomials as sums of powers of linear forms. In this talk, we focus on the following problem: given a homogeneous polynomial of degree 3 over a field, decide whether it can be written as a sum of cubes of linearly independent linear forms over an extension field. This task can be equivalently expressed as a decomposition problem for symmetric tensors of order 3. Even if the input polynomial has rational coefficients, the answer may depend on the choice of the extension field. We study the cases where the extension field is either the real or the complex numbers. Our main result is an algorithm that solves this problem in polynomial time when implemented in the bit model of computation. Furthermore, contrary to the previous algorithms for the same problem, our algorithm is algebraic and does not make any appeal to polynomial factorization. We also discuss how our algorithm can be extended to other tensor decomposition problems. This talk is based on a joint work with Pascal Koiran.
In this talk, we will see how to build trace models of programming languages in a systematic way using labelled transition systems designed by operational game semantics. The primary purpose of these models is to characterize contextual equivalence, the maximal observational equational theory, thanks to full-abstraction results. We will consider higher-order programming languages with features that include mutable store (local references), control operators (call/cc), cryptographic operators (dynamic sealing), and rich type systems (algebraic data types, parametric polymorphism). We will see how to apply this framework to prove a fully abstract compilations result from parametric polymorphism to untyped cryptographic lambda-calculus.
Un tournoi est un graphe orienté complet dans le sens où tous deux sommets sont liés par un arc. Ceci donne aux tournois un sens anarchique, cependant, l'étude que nous présentons sur l'existence de quelques modèles bien ordonnés dans les tournois va changer complètement la situation. Nous allons en apprendre que les tournois, définis d'une manière presque chaotique, sont des architectures impressionnantes structurées suivant des règles bien précises. Nous étudions l'existence des chemins, cycles et arbres dans les tournois, Nous nous intéressons aussi au nombre d'un certain type dans les tournois: la parité, et des liens avec les tournois complémentaires.
Abstract: We study periodic expansions in positional number systems. In particular, for a complex number $alpha$ we prove that there exists a finite set $D$ such that every element of $mathbb Q(alpha)$ can be represented by an eventually periodic expansion with the base $alpha$ and digits in $D$. Through a connection with the so-called spectra of numbers we will be also able to decide whether the expansion are finite on the ring $mathbb Z[alpha]$. As an application of these results, we will show that we can classify totally complex quartic fields whose integers can be expressed as sums of distinct units.
Beta expansions are well known generalisations of the familiar integer base representations of real numbers. Importantly a real number x often has many beta expansions. As such, it is natural to ask whether a real number x has a beta expansion that satisfies a certain additional property. Properties we are interested in may relate to digit frequencies, complexity, etc. In this talk I will survey a number of results in this direction and provide a flavour of their proofs. I will also pose some open questions.
Consider the following Communication Complexity problem: Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A certificate for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. A Clique-Stable set Separator is a set of certificates which contains at least one suitable certificate for each input (K,S). Given a class of graphs, the goal is to know whether there exists, for every graph of the class, a Clique-Stable set Separator with only polynomially many certificates. This question, originally restricted to the case of perfect graphs, occurred to Yannakakis when studying extended formulations of the Stable set Polytope (a polytope P has a small extended formulation if it is the projection of a polytope Q lying in a higher dimensional space, with a small number of facets). A result by Göös provides a super-polynomial lower bound for the class of all graphs, but the case of perfect graphs is still open. We use different techniques to prove that a polynomial Clique-Stable set separator exists in restricted classes of graphs: probabilistic arguments for random graphs, VC-dimension for graphs where a split graph H is forbidden, and structural arguments for some other classes. We moreover highlight strong links between the Clique-Stable set Separation and other problems, including some Constraint Satisfaction Problems.
L'algèbre géométrique ou algèbre de Clifford offre un cadre algébrique intuitif pour la représentation d'objets géométriques et leurs transformations géométriques. Cette algèbre est le résultat de la généralisation de l'algèbre de Grassmann et des quaternions de Hamilton. Le développement de son utilisation pour les problèmes en géométrie discrète et en vision par ordinateur est relativement récent. Dans ce contexte, nous nous sommes intéressés à une implantation efficace de l'algèbre géométrique permettant une utilisation dans les espaces vectoriels de hautes dimensions. Nous avons notamment proposé un formalisme récursif de l'algèbre géométrique sur arbres préfixes en montrant que la définition récursive du produit obtenue vérifiait les propriétés de ce produit. Je montrerai les résultats obtenus en termes de complexité algorithmique. Ces résultats nous ont permis de développer la représentation et la transformation de surfaces quadratiques dans un espace vectoriel de haute dimension. Je montrerai les propriétés et les opérations géométriques possibles dans cet algèbre. En parallèle, nous avons montré que cette algèbre pouvait être utilisée en géométrie digitale pour la représentation des transformations digitales et notamment l'approximation de transformations rigides par des transformations digitales définies avec l'algèbre géométrique. Je montrerai enfin l'atout de cette algèbre pour un problème d'optimisation défini sur des nuages de points.
Dans le contexte de la géométrie discrète et du traitement d'image, la grille hexagonale est souvent considérée intéressante, mais difficile à représenter et à utiliser. Par conséquent, cette grille est moins populaire. Dans cet exposé, je passerai en revue le concept de la grille hexagonale dans le contexte de deux applications. La première est liée aux déplacements rigides discrets définis sur des grilles régulières et à la préservation de l'information sous une telle transformation. En effet, en général, les discrétisations de déplacements rigides ne sont pas bijectives. Néanmoins, certaines sont bijectives, et je vais discuter la caractérisation des rotations discrètes qui sont bijectives sur la grille hexagonale. En fin, je vais comparer les distributions des angles dont les rotations discrétisées sont bijectives dans les grilles hexagonale et carrée. Dans la deuxième partie de mon exposé, je me concentrerai sur les utilisations de la grille hexagonale dans l'architecture et la conception de bâtiments. Depuis un certain temps, on savait que les structures construites à partir de panneaux hexagonaux planaires, sont meilleures que les structures triangulaires en termes de stabilité structurelle et de répartition des contraintes physiques. Dans les structures triangulaires, de telles contraintes (par exemple causées par des chutes de neige) s'accumulent aux sommets. Au contraire, dans le cas des structures hexagonales, ces contraintes sont uniformément réparties sur la structure et transmises par les arêtes. Malheureusement, la conception de maillages hexagonaux planaires est un problème très difficile. Dans cet exposé, je vais passer en revue le problème de la conception de tels maillages hexagonaux planaires et décrire un processus automatique pour le remaillage de maillages triangulaires en maillages hexagonaux planaires.
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate multivalued smooth function $f: R^drightarrow R^{d-n}$. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation $mathcal{T}$ of the ambient space $R^d$. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine and thick triangulation $mathcal{T}$. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fr{'e}chet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.
An automata network (AN for short) is a finite digraph where each node holds a state, chosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the grid'' is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind ofRice theorems'', i.e., results along the lines of:``any nontrivial property of the function computed by an automata network is computationally hard to test''. In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.
Le traitement d’images acquises sous éclairement non contrôlé s’avère fréquent dans de nombreuses applications. En effet, différentes conditions d’acquisitions contraignent la prise de vue comme le mouvement, un éclairement non uniforme, les changements d’opacité de l’objet, le bruit d’acquisition,etc... Ceci a pour conséquence de créer des variations inhomogènes de contraste dans les images. Peu de méthodes de traitement d’images prennent en compte ces variations. Afin de résoudre ce problème, un modèle adapté aux images peu contrastées, à savoir le Logarithmic ImageProcessing(LIP) sera présenté(Jourlin, 2016). Ce modèle est fondé sur la loi optique des transmittances, ce qui lui donne de très bonnes propriétés optiques pour traiter ces images. Grâce au modèle LIP, de nouvelles méthodes robustes à ces changements de contrastes seront introduites : à savoir, les métriques fonctionnelles d’Asplund(Noyel and Jourlin, 2020). Deux métriques seront étudiées : (i) la métrique d’Asplund LIP-multiplicative qui est robuste aux changements d’opacité (ou d’absorption) de l’objet modélisés par la loi multiplicative du modèle LIP, et (i) la métrique d’Asplund LIP-additive, qui est robuste aux variations d’intensité lumineuse (ou du temps d’exposition de la caméra) modélisées par la loi additive du modèle LIP. En pratique, ces métriques s’avèrent très utile pour la reconnaissance de forme grâce à des cartes de distances entre un gabarit de référence et une image. Ces cartes de distances d’Asplund seront reliées au corpus bien établi de la morphologie mathématique. Ceci permettra l’introduction d’un nouveau cadre de travail appelé morphologie mathématique logarithmique(Noyel, 2019). Je présenterai également des critères d’homogénéité de région à partir de contrastes logarithmique et qui sont robustes aux variations de contraste et très utiles pour la segmentation(Noyel and Jourlin, 2019). D’autres exemples d’analyses d’images dans de grandes banques de données seront montrés, notamment en imagerie médicale(Noyel et al., 2017) ou en analyse de texture pour les matériaux.