https://semflajolet.math.cnrs.fr/ Exceptionnellement à 14 heures.

Titles and abstracts available at: https://chocola.ens-lyon.fr/events/meeting-2023-09-28/

We present a layered approach to solve a multi-agent control problem. This methods mixes three domains: timed automata, SMT and reinforcement learning, in order to obtain the best of each: the method based on timed automata solves the combinatorial aspect of the problem, the SMT refine our model into a more realistic one and the two methods are combined into a SWA-SMT solver. Finally, the Reinforcment Learning trains the policy in order to show that the initial dataset generated with the the SWA-SMT solver is crucial for the overall success of the method.

Closure conversion is a program transformation at work in compilers for functional languages to turn inner functions into global ones, by building 'closures' pairing the transformed functions with the 'environment' of their free variables. Abstract machines rely on similar and yet different concepts of 'closures' and 'environments'.

In this talk, we analyze the relationship between the two approaches. We adopt a very simple lambda-calculus with tuples as source language and study abstract machines for both the source language and the target of closure conversion.

We overview three contributions. Firstly, a new simple proof technique for the correctness of closure conversion, inspired by abstract machines. Secondly, we show how the closure invariants of the target language allow us to design a new way of handling environments in abstract machines, not suffering the shortcomings of other styles. Thirdly, we analyze the machines from the point of view of sharing and time complexity, dissecting how different aspects of closure conversion impact on the cost of the execution.

Church’s Problem asks for the construction of a procedure which, given a logical specification φ(I, O) between input ω-strings I and output ω-strings O, determines whether there exists an operator F that implements the specification in the sense that φ(I, F(I)) holds for all inputs I. Büchi and Landweber gave a procedure to solve Church’s problem for MSO specifications and operators computable by finite-state automata. We investigate a generalization of the Church synthesis problem to the continuous time of the non-negative reals. It turns out that in the continuous time there are phenomena which are very different from the canonical discrete time domain of the natural numbers.

Je présenterai des résultats sur l'énumération exacte et asymptotique de rectangulations génériques (partitions d'un rectangle en régions rectangulaires, sans point où 4 rectangles se rencontrent, et considérées selon deux relations d'équivalences, faible ou forte). Ces objets sont en correspondance avec certains modèles de cartes planaires orientées (orientations bipolaires dans le cas faible, structures transverses dans le cas fort), qui peuvent être encodées par certains chemins dans le quart de plan en appliquant une bijection due à Kenyon, Miller, Sheffield et Wilson. Je montrerai également une extension au cas de rectangulations non génériques, donnant un continuum de modèles de cartes planaires aléatoires qui s'approchent asymptotiquement du réseau régulier.

Travaux en commun avec Erkan Narmanli et Gilles Schaeffer

We study a variant of the widely popular, fast, and often used family of community detection procedures referred to as label propagation algorithms. These mechanisms also exhibit many parallels with models of opinion exchange dynamics and consensus mechanisms in distributed computing.

Initially, given a network, each vertex starts with a random label in the interval [0,1]. Then, in each round of the algorithm, every vertex switches its label to the majority label in its neighborhood (including its own label). At the first round, ties are broken towards smaller labels, while at each of the next rounds, ties are broken uniformly at random.

We investigate the performance of this algorithm on the binomial random graph G(n,p). Via a technically delicate analysis, we show that for np>n^(5/8+epsilon), the algorithm terminates with a single label a.a.s. Moreover, we show that if np = omega(n^(2/3)), a.a.s., this label is the smallest one, whereas if n^(5/8+epsilon) < np = o(n^(2/3)), the surviving label is, a.a.s., not the smallest one.

Joint work with Lyuben Lichev (Univ. Jean Monnet), Dieter Mitsche (Univ. Jean Monnet & Pontifícia Univ. Católica de Chile), and Pawel Pralat (Toronto Metropolitan Univ.).

Let $b\geq2$ be a positive integer. Then every real number $x\in[0,1]$ admits a $b$-adic representation with digits $a_k$. We call the real $x$ simply normal to base $b$ if every digit $d\in\{0,1,\dots,b-1\}$ occurs with the same frequency in the $b$-ary representation. Furthermore we call $x$ normal to base $b$, if it is simply normal with respect to $b$, $b^2$, $b^3$, etc. Finally we call $x$ absolutely normal if it is normal with respect to all bases $b\geq2$.

In the present talk we want to generalize this notion to normality in measure preserving systems like $\beta$-expansions and continued fraction expansions. Then we show constructions of numbers that are (absolutely) normal with respect to several different expansions.

In this talk we describe functorial data migration from a re-writing perspective, by way of the open-source CQL tool from categoricaldata.net. We describe how co-presheaves and their lifting problems can be finitely presented, how solving word problems in categories enables computational category theory, and some techniques for performing functorial data migration using chase algorithms.

Zoom meeting registration link

YouTube live stream