SAMSA Workshop

A classical decision problem in group theory is the subgroup membership problem: given a finitely generated group $G$, the input consists of a finite list of group elements $g, g_1, \ldots, g_n$ (represented as words over the generators), and the question is whether $g$ belongs to the subgroup generated by $g_1, \ldots, g_n$.

Over the last two decades, several generalizations of the subgroup membership problem have been studied, such as the submonoid membership problem and the rational subset membership problem.

In recent years, significant progress has been made on decidability and complexity questions for various membership problems. We mention a few representative results:

• The speaker showed in 2021 that the subgroup membership problem for the matrix group $\mathrm{GL}(2, \mathbb{Z})$ can be decided in polynomial time when all matrix entries in the input are given in binary notation.
• Romankov (2023) proved that the submonoid membership problem is undecidable in the group of all unitriangular $k$-dimensional integer matrices, provided that $k$ is sufficiently large.
• Bodart (2024) showed that the rational subset membership problem for the Heisenberg group is decidable.
• Bodart (2025) provided the first example of a group $G$ with an undecidable subgroup membership problem such that membership in every fixed finitely generated subgroup of $G$ is decidable.
• Dong (2025), building on results of Shafrir (2024), showed that decidability of the submonoid membership problem is not preserved under finite group extensions.

In my first talk, I will give an overview of these recent developments and discuss open problems. In my second talk, I will provide some technical insights into the proofs.

I will go through natural extensions of linear recurrence sequences (LRS). There are three natural but orthogonal extensions: (1) polynomial recurrence sequences, by changing the recurrence from linear functions to polynomials; (2) holonomic sequences which one can think are definable by context-free grammars; (3) WMSO sequences, which come from the Droste-Gastin logic characterising weighted automata. I will also briefly discuss rational recurrence sequences, which naturally generalises (1) and (2) but has some disadvantages.

Following the survey I will show that the sequence a_n = n^n cannot be defined as a polynomial recurrence sequence, which shows that (1) does not contain (3) in the survey talk.

This talk will survey the main known results and open problems relating to the Boolean and binary rank of 0,1 matrices, with particular emphasis on their relationship to the real rank. We will review the basic definitions of these rank functions and present the main alternative formulations of the binary and Boolean rank, together with their computational complexity and their deep connection to the field of communication complexity. We will see some examples of techniques used to establish lower and upper bounds on the binary and Boolean rank, from both mathematics and theoretical computer science, and also highlight the main mathematical properties of these ranks in comparison with those of the real rank. Finally, we will present some algorithmic approaches for computing and approximating these rank functions.

The Kronecker product is a useful tool to build large structured matrices from smaller ones, with applications in mathematics and computer science. We will discuss Kronecker products of 0,1 matrices, and applications such as direct sum problems in communication complexity or how Kronecker products are used to amplify the gap between the Boolean, binary and real rank. We will show some of the main mathematical techniques used to give lower and upper bounds on the rank of Kronecker products, as well as prove that the Boolean rank is not always multiplicative under this product. The multiplicativity of the binary rank is still an open problem.

Weighted automata can be classified according to their degree of ambiguity, ranging from deterministic and unambiguous automata, over finitely and polynomially ambiguous automata, to exponentially ambiguous ones. These classes form a natural hierarchy with strictly increasing expressive power, which gives rise to both structural and algorithmic questions.

From a structural perspective, a central goal is to characterize the functions that can be realized by weighted automata within a given ambiguity class. From an algorithmic viewpoint, given a weighted automaton, we would like to determine the smallest ambiguity class to which it belongs and, when possible, effectively construct an equivalent automaton within that class.

Significant progress has recently been made on these questions, both for tropical semirings and for fields. In this survey, I will present an overview of the current state of the art for weighted automata over fields, highlighting key results, techniques, and remaining open problems.

Given a function recognized by a weighted automaton over a field, the semigroup generated by its transition matrices plays a central role in determining the ambiguity class of the function. In the special case where all the transition matrices are invertible, we consider the group generated by these transition matrices.

Variations of classical algorithms from computational group theory then become applicable to the problem of deciding the ambiguity class. In this tutorial, I will explain this connection, and discuss some of relevant concepts from algebra that are useful in this context but appear not to have been exploited yet by the WA community (in particular, Wedderburn-Artin Theory).