Marvels and mysteries of rational base numeration systems

The definition of numeration systems with rational base, in a joint work with S. Akiyama and Ch. Frougny (Israel J. Math.  2008), has allowed to make some progress in a number theoretic problem, by means of automata theory and combinatorics of words. At the same time, it raised the problem of understanding the structure of the sets of the representations of the integers in these systems from the point of view of formal language theory.  At first sight, these sets look rather chaotic and do not fit well in the classical Chomsky hierarchy of languages (in contrast with languages defined by some other non standard numeration systems).  They all enjoy a property that makes them defeat, so to speak, any kind of iteration lemma.

On the other hand, these sets also exhibit remarkable regularity properties.  In the subsequent years, these regularities have been studied in a series of joint papers with V. Marsault.  In particular, we have shown that periodic signatures are characteristic of the representation languages in rational base numeration systems (Indagationes Mathematicae, 2017) and studied, jointly with S.Akiyama, a kind of autosimilarity property that also leads to the construction of Cantor-like sets (Discrete Mathematics and Theoretical Computer Science 2018). The representation languages still keep most of their mystery.  The partial results which will be presented call for further investigations on the subject even stronger.

About the Speaker:
Jacques Sakarovitch is an Emeritus Reasearcher at CNRS and Emeritus Professor at Telecom Paris. For 50 years now, his area of research is theoretical computer science and more precisely automata theory, under its many various aspects, from pushdown automata and context-free languages to functions realized by finite automata, from combinatorics of words and combinatorial theory of groups and semigroups to non standard numeration systems. He has published in 2009 at Cambridge University Press a monograph 'Elements of Automata Theory' on the subject.

He has been the director of the federation of the Computer Science laboratories of Paris 6 and Paris 7 universities, as well as the coordinator of a European Project gathering teams from seventeen universities, in the 90's. From 2013 to 2018, he was the Chair of the Technical Committee on Foundations of Computer Science of the International Federation of Information Processing (IFIP).  He is currently a vice-president of IFIP.