A rational series is a noncommutative formal power series whose coefficients are recognized by a weighted finite automaton (WFA). A rational series with coefficients in a field $K$ is a Pólya series if all nonzero coefficients are contained in a finitely generated subgroup of $K^\times$. Generalizing results of Pólya (1921), Benzaghou (1970), and Bézivin (1987) for the univariate case, we show that Pólya series are precisely the ones recognized by unambiguous WFAs.

This is joint work with Jason Bell. arXiv:1906.07271

A strong edge coloring of a graph is an assignment of colors to edges such that every color class induces a matching. The smallest number of colors for which a strong edge coloring of a graph G exists is known as the strong chromatic index and it is denoted by $\chi′_s(G)$. It is already known that the problem of finding the strong chromatic index for arbitrary graphs is NP-complete. In this talk, we will discuss strong edge coloring of unitary Cayley graphs.

Every new/old PhD student is invited to come and talk about her/his research interests.

Each talk will be 2-5 minutes long, without any slides, and should be understandable by everyone

Un arbre binaire compacté est un graphe acyclique dirigé qui représente un arbre binaire de façon sans redondances, dans le sens que tous les sous-arbres isomorphes sont partagés. Nous montrons que le nombre des arbres binaires compactés de tailles n croît asymptotiquement en

\Theta(n! 4^n e^{3 a_1 n^{1/3}} n^{3/4}).

Ici, a_1 ≈ -2,338 est la plus grande racine de la fonction d'Airy. Ce résultat est obtenu à partir d'une nouvelle récurrence des nombres de ces arbres compactés, avec une nouvelle méthode qui, inspirée par des estimations empiriques suffissament précises, prouve des bonnes bornes par induction. Ce travail donne aussi des nouvelles bornes sur le nombre d'automates minimaux qui reconnaissent un langage fini d'un alphabet binaire, qui possède aussi un exponentiel étiré. Par sa simplicité, notre méthode s'applique potentiellement aux autres objets.

http://chocola.ens-lyon.fr/events/

IRIF Cake^TM is an amazing opportunity to meet people while simultaneously eating cakes baked by your fellow colleagues! Join us every Thursday, at 5pm, in front of room 3052 (Sophie Germain 3rd floor) for a weekly feast. You can also express your cooking skills and volunteer to bake a cake by sending an email to cake@irif.fr.

Il y a plusieurs caractérisations algébriques (dites “axiomatiques”) de l'entropie discrète de Shannon. Je vais présenter ici une caractérisation analogue pour l'entropie différentielle, qui apparaît dans la théorie de compression des signaux continus: le cadre utilisé est la “cohomologie de l'information”, associé aux préfaisceaux sur certaines structures combinatoires. Si le temps le permet, je vais présenter d'autres théories cohomologiques des faisceaux très proches, définies sur les graphes (Friedman) et les complexes simpliciaux (Abramsky et al.), qui correspondent aussi à la cohomologie des topos.

I will talk about two fun constructions for reachability analysis of one-clock timed automata, which lead to concise logical characterizations in existential Linear Arithmetic.

The first one describes “punctual” reachability relations: reachability in exact time t. It uses a coarse interval abstraction and counting of resets via Parikh-Automata. The other is a “sweep line” construction to compute optimal time to reach in reachability games played on one-clock TA.

Together, these can be used to derive a (tight) NP complexity upper bound for the coverability and reachability problems in an interesting subclass of Timed Petri Nets, which naturally lends itself to parametrised safety checking of concurrent, real-time systems. This contrasts with known super-Ackermannian completeness, and undecidability results for unrestricted Timed Petri nets.

This is joint work with Lorenzo Clemente and Piotr Hofman, and was presented at CONCUR'19. Full details are available at https://arxiv.org/abs/1907.01240.

I will talk about two fun constructions for reachability analysis of one-clock timed automata, which lead to concise logical characterizations in existential Linear Arithmetic.

The first one describes “punctual” reachability relations: reachability in exact time t. It uses a coarse interval abstraction and counting of resets via Parikh-Automata. The other is a “sweep line” construction to compute optimal time to reach in reachability games played on one-clock TA.

Together, these can be used to derive a (tight) NP complexity upper bound for the coverability and reachability problems in an interesting subclass of Timed Petri Nets, which naturally lends itself to parametrised safety checking of concurrent, real-time systems. This contrasts with known super-Ackermannian completeness, and undecidability results for unrestricted Timed Petri nets.

This is joint work with Lorenzo Clemente and Piotr Hofman, and was presented at CONCUR'19. Full details are available at https://arxiv.org/abs/1907.01240.