Mealy machines, automaton (semi)groups, decision problems and random generation – MealyM

This project is centered on automaton (semi)groups, namely (semi)groups generated by Mealy machines. This possible presentation for (semi)groups has been so far mainly studied by mathematics researchers via geometric group theory. It has not yet been exploited by computer science community although it allows to get very sophisticated groups from very small and simple objects which are widely used and studied in computer science.

The work will progress along two intertwined axes.

We intend to obtain theoretical results on automaton (semi)groups using computer science techniques, mainly answering decision problems in an effective way: does such a Mealy machine generate a finite or an infinite (semi)group? What is the order of some element of the group? Etc.

We aim to produce efficient tools to generate random (semi)groups via random Mealy machines. Random generation is a classical procedure to verify robustness of programs, to make numerical simulations or to test conjectures.


Results obtained in both directions will be included into Sage, directly or through GAP.


We intend to foster intensive collaboration among the project members by:

- punctuating the project by one-day meetings on a quarterly basis,
- funding for 15 graduate student internship gratification months,
- hosting international experts (long-term visit) and young researchers,
- organizing a main meeting during the fourth year, gathering from 25 to 35 people, graduate students, post-doctoral researchers and established researchers alike, for a week of active discussions on research problems,
- funding a PhD thesis co-advised by the two team leaders (I. Klimann et M. Picantin): the doctoral fellow will work full-time on the project.