A multidimensional continued fraction algorithm is a generalization of well-known continued fraction algorithms of small dimensions: Gauss and Euclidean. Ergodic properties of Markov MCF algorithms (ergodicity, nonsingularity, exactness, bi-measurability) affect their convergence (if the MСF algorithm is a Markov algorithm, there is a relationship between the spectral properties and its convergence).

In 2013 T. Miernowski and A. Nogueira proved that the Euclidean algorithm and the non-homogeneous Rauzy induction satisfy the intersection property and, as a consequence, are exact. At the end of the article it is stated that other non-homogeneous markovian algorithms (Selmer, Brun and Jacobi-Perron) also satisfy the intersection property and they also exact. However, there is no proof of this. In our paper this proof is obtained by using the structure of the proof of the exactness of the Euclidean algorithm with its generalization and refinement for multidimensional algorithms. We obtained technically complex proofs that differ from the proofs given in the article of T. Miernowski and A. Nogueira by the difficulties of generalization to the multidimensional case.

In 2002 H. Bruin and S. Troubetzkoy described a special class of interval translation mappings on three intervals. They showed that in this class the typical ITM could be reduced to an interval exchange transformations. They also proved that generic ITM of their class that can not be reduced to IET is uniquely ergodic.

We suggest an alternative proof of the first statement and get a stronger version of the second one. It is a joint work in progress with Mauro Artigiani and Pascal Hubert.

https://semflajolet.math.cnrs.fr/

https://www.irif.fr/rencontres/rentree2022

In the study of programming languages, an essential point is the ability to state program equivalence, whether it is to reason abstractly or to establish that some program transformations, used typically when compiling programs, preserve the behavior of programs. The topic of this talk is the study of program equivalence for the case of programs expressed as terms of the λ-calculus, seen as a mathematical model of functional programming languages. We will survey existing program equivalences and focus on normal form bisimulations, in different variants of the lambda calculus. The lambda calculus was first introduced as a way to represent computable functions, with the Call-by-Name variant which has been extensively studied. Nowadays, functional programming languages use mostly the Call-by-Value variant (OCamL) and some the Call-by-Need variant (Haskell). In Call-by-Name, normal form bisimulations yield very satisfactory results. Unfortunately, these do not export to Call-by-Value. Part of my thesis work will be trying to find a satisfactory program equivalence in Call-by-Value.

The previous talk by Victor Arrial is a nice introduction to this talk but concepts tied to the lambda calculus (and its variants) will be re-explained. We will also need the (more generic) concept of co-induction to form program equivalences, which will be briefly explained as well.

In this talk, we present a new construction of a finite automaton associated with a rational (or regular) expression. It is very similar to the one of the so-called Thompson automaton, but it overcomes the failure of the extension of that construction to the case of weighted rational expressions. At the same time, it preserves all of the properties of the Thompson automaton.

This construction has two supplementary outcomes.

The first one is the reinterpretation in terms of automata of a data structure introduced by Champarnaud, Laugerotte, Ouardi, and Ziadi for the efficient computation of the position (or Glushkov) automaton of a rational expression, and which consists in a duplicated syntactic tree of the expression decorated with some additional links.

The second one supposes that this construction devised for the case of weighted expressions is brought back to the domain of Boolean expressions. It allows then to describe, in terms of automata, the construction of the Star Normal Form of an expression that was defined by Brüggemann-Klein, and also with the purpose of an efficient computation of the position automaton.

This is joint work with Sylvain Lombardy (Labri, U. Bordeaux)

The graph transformation tool GROOVE is actively used in education and research, as an accessible and relatively powerful yet easy to use tool that incorporates many of the basic concepts and quite a number of more advanced GT-based features. However, being academy-ware, documentation is not its strongest point, and so some features are less visible and consequently under-used. In this presentation, I plan to demonstrate both the basic functionality (essentially, state space generation of a graph transformation system, with run-time isomorphism checking), as well as some of the more advanced features: - Typing, including subtyping, abstract types and type specialisation - Path expressions and label variables - Data manipulation, including algebra selection - Quantified rules, including the use of counting and multiary (i.e., set-based) operators - Rule control, including functions and (atomic) recipes.

Zoom meeting registration link

YouTube live stream

Computing a mission plan for an autonomous vehicle consists of path planning and task scheduling, which are two outstanding problems existing in the design of multiple autonomous vehicles. Both problems can be solved by the use of exhaustive search techniques such as model checking and algorithmic game theory. However, model checking suffers from the infamous state-space-explosion problem that makes it inefficient at solving the problem when the number of vehicles is large, which is often the case in realistic scenarios. In this talk, we show how reinforcement learning can help model checking to overcome these limitations, such that mission plans can be synthesized for a larger number of vehicles if compared to what is feasibly handled by model checking alone. Instead of exhaustively exploring the state space, the reinforcement-learning-based method randomly samples the state space within a time frame and then uses these samples to train the vehicle models so that their behavior satisfies the requirements of tasks. Since every state of the model needs not be traversed, state-space explosion is avoided. Additionally, the method also guarantees the correctness of the synthesis results. The method is implemented in UPPAAL STRATEGO and integrated with a toolset to facilitate path planning and task scheduling in industrial use cases. We also discuss the strengths and weaknesses of using reinforcement learning for synthesizing strategies of autonomous vehicles.