Participation at the event is free of charge, but registration is compulsory.

BGSMATH: Stallings Automata and Applications

Sign in
Advanced course / School
From January 17, 2023
to February 16, 2023


17th January - 16th Februrary

Tuesdays and Thursdays, from 16h to 18h.

Registration deadline 12 / 01 / 2023

🖥️ via ZOOM

🗓️ Tuesdays and Thursdays, from January 17 to February 16, 2023

🕘 16h – 18h (CET), UTC +1

course description


Enric Ventura | UPC
Jordi Delgado | UPC
Pascal Weil | Laboratoire bordelais de recherche en informatique (LaBRI), Université Bordeaux I



17/1/23 (2h): Introduction: Free groups. We will introduce free groups (from several points of view, algebraic, combinatorial, and categoric) and its first algebraic properties. We will present some natural questions and examples motivating the course.

19/1/23 (2h): Automata and languages. We will set up the connection between automata (i.e., graphs with certain decorations), languages, and (subgroups of) the free group. This includes several relevant (graph-theoretical) definitions together with the proof of a few technical lemmas crucial to establish this connection.

24/1/23 (2h): The Stallings bijection. This session is devoted to the central result in Stallings theory: there is a bijection between a certain kind of automata and the lattice of subgroups of the free group. We will stress the computability of this map when restricted to finitely generated subgroups (corresponding to finite graphs). As a corollary, we obtain the Nielsen-Schreier and the computabity of bases, among other results.

26/1/23 (2h): First applications. In this session we will consider the first natural applications of the Stallings bijection: the membership problem (including explicit rewriting in terms of the given generators) and the conjugacy problem for subgroups. We will stress some similarities and some (big) differences between the behaviour of the lattice of subgroups of the free group, the lattice of subspaces of a vector space.

31/1/23 (2h): Index and Marshall Hall Theorem. We will explain the relation between vertices of the automata and cosets of the subgroup. We will obtain a graphical characterization for finite index subgroups, and the Schreier index formula relating index and rank. As a corollary we obtain also a proof of Marshall Hall Theorem, and the residual finiteness of free groups.

2/2/23 (2h) Intersection of subgroups. We introduce the product of automata and see the relation with the intersection of subgroups. This will allow us to deduce the Howson property for free groups (intersections of finitely generated subgroups are always finitely generated), and the Hanna-Neumann inequality (removing the coefficient 2 has been a famous problem solved recently with the help of other techniques out of the scope of this course). On the way, we will be able to compute a basis for the intersection of two finitely generated subgroups. Almost at the same price, we will be able to compute intersections of cosets, and understand malnormality.

7/2/23 (2h) Algebraic extensions and quotients of automata. We define the notion of algebraic extension between subgroups of a free group and prove (a modern version of) Takahasi’s Theorem saying that finitely generated subgroups have finitely many algebraic extensions, and they are all computable. From this result, we will deduce several interesting algebraic applications. 

9/2/23 (2h): Counting automata and counting subgroups. We’ll introduce a recent technique developed to count (or asymptotically estimate) the amount of subgroups satisfying certain properties. This is done by counting automata, which can be seen via partial injections (they form an inverse monoid generalizing the classical symmetric group in an interesting way).

14/2/23 (1h): Sage. A brief introduction to the Stallings_graphs package for SageMath, a nice piece of software meant to experiment with finitely generated subgroups of (finite rank) free groups.

14/2/23 (1h): Enriched Stallings automata I. We will introduce and briefly describe a recent extension of Stallings automata: by decorating the automata with integral vectors in an appropriate way, we obtain a bijection (similar to the Stallings one) between a certain kind of enriched automata and the lattice of subgroups of $F_n \times Z^m$, the direct product of a free and a free abelian group. Of course, the algebraic questions related to the free abelian part usually become systems of equations, but the interplay between the two parts is interesting and sometimes highly non-trivial.

16/2/23 (2h): Enriched Stallings automata II: Despite the apparent similarity, the lattices of subgroups of $F_n$ and $F_n \times Z^m$ behave very differently, especially when we consider intersections. A big difference is that the second one does not satisfy the Howson property: it admits pairs of finitely generated subgroups whose intersection is not fnitely generated. By looking carefully at the pull-back of (enriched) Stallings automata, we’ll explain how to decide when the corresponding intersection is finitely generated and, if so, how to compute a set of generators for it. 


1. L. Bartholdi and P.V. Silva, “Rational subsets of groups”, Chapter 23 from J.E. Pin “Handbook on automata theory”, EMS Publishing House (2021), 1608 pages. Available at arXiv:1012.1532.
2. J. Delgado, E. Ventura, “Autòmats de Stallings, un camí d’anada i tornada” (in catalan). To appear at Butlletí de la Societat Catalana de Matemàtiques. Available at https://arxiv.org/pdf/2202.07642.pdf
3. J. Delgado and E.Ventura, “Stallings automata for free-times-abelian groups: intersections and index”. Publicacions Matemàtiques 66 (2022), 789–830.
4. J. Delgado, E. Ventura, “A list of applications of Stallings automata”, Transactions on Combinatorics 11(3) (2022), 181—235. Available at https://arxiv.org/pdf/2109.01268.pdf
5. I. Kapovich and A. Myasnikov. “Stallings foldings and subgroups of free groups”. Journal of Algebra 248.2 (Feb. 2002), pp. 608–668.
6. A. Miasnikov, E. Ventura, and P. Weil. “Algebraic extensions in free groups”. In: Geometric Group Theory. Ed. by G.N. Arzhantseva, J. Burillo, L. Bartholdi, and E.Ventura. Trends in Mathematics. Birkhäuser Basel, Jan. 2007, pp. 225–253.
7. J.R. Stallings. “Topology of finite graphs”. Inventiones Mathematicae 71 (Mar. 1983), pp. 551–565.
8. N.W.M. Touikan, “A fast algorithm for Stallings’ folding process”. International Journal of Algebra and Computation 16(06) (Dec. 2006), pp. 1031–1045.


Name Institution
Juan Jose Rue Perna Universitat Politècnica de Catalunya
Swarnadeep Choudhury Tripura University (A Central University)
Paloma López Larios Universitat Politècnica de Catalunya
Ignat Soroko University of North Texas
Yanlong Hao University of Illinois at Chicago
Pubo Huang University of Wisconsin–Madison
Corentin Bodart University of Geneva
Xabier Legaspi ICMAT
Kasia Jankiewicz University of California
André Carvalho University of Porto
Soumya Dey Krea University
Kaan Doganay Mimar Sinan University
Ioannis Papavasileiou National and Kapodistrian University of Athens
Georgii Veprev University of Geneva
Letizia Issini University of Geneva
Megan Howarth University of Geneva
Eduardo Silva École normale supérieure - Paris
Gemma Crowe Heriot-Watt University
Karel Dekimpe Katholieke Universiteit Leuven
Yves Stalder Université Clermont Auvergne
Eric Pope Memorial University of Newfoundland
Joseph MacManus University of Oxford
Greyson Meyer University of California
Alberto Cassella University of Milan - Bicocca
Anders Cornect Memorial University of Newfoundland
Iván Chércoles Cuesta ICMAT
Douglas Vilela de Paiva Silva Federal University of Minas Gerais
Niyaz Tokmagambetov Centre de Recerca Matemàtica
Wenhao Wang Steklov Mathematical Institute
Panagiotis Tselekidis University of Oxford
Joan Galobart UPC
Lucía Asencio Martín Newcastle University
Jennifer Beck University of North Carolina at Greensboro
Miquel Saucedo Centre de Recerca Matemàtica
Andy Moawad Miami University
Max Gheorghiu University of British Columbia
Dario Ascari University of Oxford
Kristina Oganesyan Universitat Autònoma de Barcelona
Audrey Goodnight University of Nebraska–Lincoln
Petra Lynn Vanderhei University of Nebraska–Lincoln
Qing Shen University of Technology, Sydney
Lucas Henrique Rocha de Souza None
Nicolas Bitar Université Paris-Saclay
Xiaobing Sheng University of Tokyo
Jake Murphy Louisiana State University - Baton Rouge
Niv Levhari Tel Aviv University
António Malheiro Universidade Nova de Lisboa
Ash DeClerk University of Nebraska–Lincoln
Katie Vokes University of Luxembourg
Jon Merladet Urigüen University of Southampton
Pablo Sánchez Peralta Universidad Autónoma de Madrid
Leon Pernak Saarland University
Emmanuel Rauzy Saarland University
Joren Matthys Katholieke Universiteit Leuven
Alejandra Garrido Universidad Autónoma de Madrid
Marcos Escartin Ferrer Universidad de Zaragoza
Ado Dalla Costa Federal University of Santa Catarina
Henrique Souza Universidad Autónoma de Madrid
Haoyang He University of Manchester
Lisa Sasso Katholieke Universiteit Leuven
Islam Foniqi University of East Anglia
Lore De Weerdt Katholieke Universiteit Leuven
Yongsheng Jia University of Manchester
Lukas Vandeputte Katholieke Universiteit Leuven
Mallika Roy  Universitat Politècnica de Catalunya
Michael Chapman Hebrew University of Jerusalem
Alex Lubotzky Hebrew University of Jerusalem
Dominik Francoeur ICMAT
Lluis Vena Cros Universitat Politècnica de Catalunya
Oorna Mitra Indian Statistical Institute
Genevieve Walsh Tufts University
Jean-Eric Pin CNRS

 For inquiries about this event please contact the research programs coordinator Ms. Núria Hernández at nhernandez@crm.cat​​