SAMSA Workshop

The ambiguity hierarchy of rational series over a field $\mathbb{F}$ and alphabet $\Sigma$ consists of the sets of series realised by the deterministic, unambiguous, finitely ambiguous, polynomially ambiguous, and unrestricted weighted automata over $\mathbb{F}$ and $\Sigma$. While each of these layers is obviously included in the following one, the strictness of the inclusions can depend both on the field $\mathbb{F}$ and on the alphabet $\Sigma$.

The fundamental question about how the strictness of these inclusions depends on the algebraic properties of the field $\mathbb{F}$ has recently been fully answered by the speaker both for unary and for arbitrary finite alphabets. The talk will review a landscape that has been uncovered by these investigations, with emphasis on the most recent and yet unpublished results.

Consider the following problem: given a language $L \subseteq \Sigma^*$ and a monoid morphism $\mu \colon \Sigma^* \to \mathbb{Q}^{n \times n}$, compute the linear Zariski closure of $\mu(L)$ (i.e. the smallest union of vector spaces containing $\mu(L)$).

This problem can be considered for different classes of languages. When $L$ is regular, it can be solved using the tools for the computation of the linear hull of a weighted automaton, which is an invariant that plays a central role in deciding the existence of an equivalent deterministic or unambiguous automaton as well as the minimization of equivalent cost register automata.

In this talk, we focus on the setting of context-free languages (CFL). Here, the problem remains open and happens to be an interesting subproblem of the computation of the linear hull for weighted tree automata, which would allow extending the previous results from words to trees on a ranked alphabet.

It has also been considered for the more general Zariski topology in [Ait El Mansour et al., 2026] where it was shown to be decidable for languages recognizable by 1-VASS (which is a subclass of CFL) and undecidable for indexed languages (which generalize CFL).

Based on joint work with Nathan Lhote and Pierre Alain-Reynier.

We consider decision problems related to finite monoids of rational matrices.

We show that determining finiteness of a given finitely presented monoid is in PSPACE, improving the known co-NEXP^NP bound. We also show that the membership problem for finite matrix monoids is PSPACE-complete, improving the known NEXP upper bound.

Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.

This talk is based on a paper accepted to ICALP 2026, and is joint work with Rida Ait El Manssour, Nathan Lhote, Mahsa Shirmohammadi and James Ben Worrell.

XNFAs (also known as XOR-NFAs or symmetric-difference NFAs) are a variant of standard finite automata in which an input word is accepted iff the number of accepting runs is odd. Equivalently, these are weighted automata over the field of two elements, whereas the more familiar nondeterministic finite automata (NFAs) are weighted automata over the Boolean semiring. Much like NFAs, XNFAs recognise exactly the class of regular languages and are exponentially more succinct than DFAs. Unlike NFAs, XNFAs admit efficient complementation and minimisation.

Given an automaton A and a word w, the acceptance problem asks whether A accepts w. In this talk, we compare the acceptance problem for XNFAs and NFAs in a fine-grained manner, focusing on optimising the degrees of polynomials in the running-time bounds. We first refine the upper bounds for the acceptance problem for XNFAs and NFAs of bounded ambiguity (e.g., unambiguous automata). We then show that, under the assumption of polynomial ambiguity, NFA acceptance reduces to XNFA acceptance. This is joint work with Dmitry Chistikov, Radoslaw Piorkowski and Brink van der Merwe.

Simon's theorem is a fundamental result in formal languages that lets one factorise words with respect to a finite semigroup. This talk is an advertisement for a Simon-inspired method to compute bounded summaries of words with respect to a finite semigroup, while losing some information. We will see an application of this method for a flow-maximisation problem.

Given a language $L \subset \Sigma^*$ and homomorphisms $h, k\colon \Sigma^* \rightarrow \Sigma^*$, the homomorphism equivalence problem (HEP) asks whether $h$ and $k$ are equivalent when restricted to $L$. We show decidability of the HEP for ET0L languages (a subclass of indexed languages) using a Hilbert method approach, and discuss the obstacles which arise when one attempts to generalize it to the full class of indexed languages.

The well known Todd-Coxeter algorithm is widely used to construct transformation representations of finitely presented monoids. It can be seen, in some sense, as computing the direct limit of a sequence of semiautomata approximating the right Cayley graph of the underlying monoid. This algorithm can also be used for finitely presented groups and, perhaps more surprisingly, there exists an analogue of the Todd-Coxeter algorithm for inverse monoids due to J. B. Stephen (1987). This is despite the fact that the free inverse monoid is not finitely presented as a monoid. Could it be possible to extend the Todd-Coxeter algorithm to other classes of monoids, such as finitely based varieties of monoids?

In this talk I will briefly describe a category theory based approach to modeling the Todd-Coxeter algorithm and I will present an extension of the Todd-Coxeter algorithm to presentations in finitely based varieties of monoids, motivated by a recent NL-space algorithm for deciding if a monoid identity is modelled by a given finitely generated transformation monoid due to L. Fleisher and T. Jack (2020).

The purpose of this presentation is to advertise the notion of Lie rank of a series. It was introduced by Fliess in the 1980's as a generalisation of the notion of Hankel rank (also introduced by Fliess).

The Lie rank is less than or equal to the Hankel rank, and consequently the series of finite Lie rank generalise the rational series (which are those of finite Hankel rank). The pinnacle of the theory is a result of Fliess, who has shown that series of finite Lie rank have minimal automata recognisers.

As a new result, we show that the Lie rank is computable for the class of rational and shuffle-finite series.

This is joint and ongoing work with Nathan Lhote.

Aperiodic finite semigroups are part of a beautiful correspondence between restricted automata models, first-order logic on strings, and star-free regular expressions. There have been several propositions for a generalisation of these objects to a weighted setting (preserving said correspondence), defining aperiodic weighted automata, aperiodic matrix semigroups, and star-free rational series. I will present what little is known about these models, and conjectures that are believed to hold in general.

Formal power series have long played a central role in both Mathematical Systems Theory and Automata Theory. A foundational result by Marcel-Paul Schützenberger established that recognizable series (the semantics of weighted automata) are precisely the rational series, where rationality is defined via the rational closure under the Cauchy product of non-commutative polynomials.

This connection extends into systems theory through the framework of Chen–Fliess series (named after K. T. Chen & Michel Fliess), where rational series correspond to canonical realizations of bilinear systems.

Motivated by this interplay, a natural question arises: What if we replace the Cauchy product with the shuffle product in forming the rational closure? This leads to the notion of shuffle-rational series. In this talk, we will introduce the concept of shuffle recognizability, and present a Schützenberger-type result showing the equivalence between shuffle rationality and shuffle recognizability. We will also explore the implications of these ideas in the context of nonlinear systems theory.

In a related direction, Schützenberger also proved that rational series are closed under the shuffle product. This observation leads to a second construction: the rational closure of rational series under shuffle—giving rise to doubly-rational series. If time permits, we will discuss the notion of doubly-recognizable series as well, and the relation of all these classes with respect to shuffle-finite series.

The talk is intended to be self-contained and assumes no prior background in systems theory or Chen–Fliess series.

The Nottingham group is a profinite group of power series over a finite field, with composition as the group operation. It is known to contain many elements of finite order, but, except in very special cases, no explicit formulas for such elements had been known.

I will explain how finite automata can be used to give explicit descriptions of such elements. The construction uses techniques from algebraic geometry and number theory to produce algebraic power series, which are then converted into automata using Christol's theorem. I will also discuss the problem of finding sparse representatives of some of these elements.

The talk is based on joint work with Gunther Cornelissen, Djurre Tijsma, and Mieke Wessel.

Given a finite alphabet $A$, we say that a two-dimensional configuration $c$ over $A$ is of low complexity if there exist two integers $M$ and $N$ such that $P_c(M,N) \leq MN$ holds, where $P_c$ denotes the pattern complexity function of $c$. As a potential generalization of the one-dimensional Morse and Hedlund theorem, Nivat's conjecture states that any such configuration must be periodic.

A counterexample to this conjecture would then be a low-complexity but non-periodic configuration. What would such a configuration look like? Could the understanding of its shape reveal the absurdity of its existence? Using a geometric interpretation of underlying algebraic geometry tools developed by Jarkko Kari and Michal Szabados, I will take you through the different attempts we have made at answering those questions.

This work is joint work with Pierre Guillon, Jarkko Kari and Etienne Moutot.

Loop invariants are properties that hold before and after each iteration of a program loop, and they play a central role in program verification by ensuring the correctness of algorithms throughout execution. This talk focuses on polynomial loops, where loop assignments are given by polynomial maps. While computing polynomial invariants for general loops is undecidable, efficient methods exist for certain restricted classes of loops such as solvable loops. I consider a more general setting in which the loop assignments may involve arbitrary polynomials. Using tools from algebraic geometry, I present two algorithms for generating all polynomial invariants of a polynomial loop up to a specific degree. These algorithms differ depending on whether the initial values of the loop variables are fixed or treated as parameters.

Abstract. We consider famous Collatz problem (the \(3x + 1\) problem) and treated it from the automata theory point of view. New forms of Collatz automata is proposed that can be analytically studied. Let \(C(n)\) be the famous Collatz function \(C(n) = n/2\) if \(n\) is even, and \(3n + 1\) if \(n\) is odd. The autonomous automaton \(A_1 = (\mathbb{N}, \{1\}, \delta_1)\) simulates this function, where \(\mathbb{N}\) is the set of natural numbers, and \(\delta_1(n, 1) = C(n)\) for all \(n \in \mathbb{N}\). According to Collatz conjecture the trivial cycle \((1,4,2)\) will be the attractor for the super-word \(1^\infty\).

Denote by \(\mathbb{N}_0\) and \(\mathbb{N}_1\) the subsets of the even and odd natural numbers, respectively. Let \(\mathrm{ord}(n)\) be the maximal number \(m\) for which \(2^m\) divides \(n\). Consider the autonomous automaton \(A_2 = (\mathbb{N}_1, \{1\}, \delta_2)\), where:

From Collatz conjecture follows that super-word \(1^\infty\) will be synchronizing for the automaton \(A_2\), i.e., the first state 1 will be the attractor \(\mathrm{im}(1^\infty) = \{1\}\).

In the automaton \(A_3 = (\mathbb{N}_1, \{0,1\}, \delta_3)\), versus the automaton \(A_2\), multiplication and division operations is separated

Here we can see for the super-word \((10)^\infty\) struggle between multiplication and division, where division wins.

Keywords: \(3x + 1\) problem, Collatz conjecture, infinite automata.

A sequence $(u_n)$ is holonomic (or P-finite) if it satisfies a recurrence $a_d(n) u_{n+d} = a_{d-1}(n) u_{n+d-1} + \cdots + a_0(n) u_n$, with polynomial coefficients $a_i(n)$. In the case where the coefficients are constants, we call $(u_n)$ a C-finite sequence, and in this setting, the celebrated Skolem-Mahler-Lech theorem states that the set of zeros is a union of finitely many arithmetic progressions and a finite set. This has since been refined to give effective upper bounds on the number of arithmetic progressions and the size of the finite set based only on the order $d$.

In the world of P-finite sequences, an analogue of the Skolem-Mahler-Lech theorem is known (since 2012) for P-finite sequences where the first and last coefficients are non-zero modulo a prime $p$. In this talk, I will discuss recent/ongoing work in which we refine this result to give effective upper bounds on the number of arithmetic progressions and the size of the finite set based only on the order $d$, the degrees of the coefficients $a_i(n)$, and the prime $p$.

The Positivity Problem asks: is every term in a recursively-defined sequence non-negative? Recent works, focusing on low-order P-finite sequences, have shown that problem instances for Positivity can be resolved by settling equality tests (e.g., determine whether a given constant is zero). Obstacles to progress arise because the constants involved in such tests are commonly expressed as the limits of infinite products or generalised continued fractions. In this talk, we will take an examples-based approach and present current challenges in the field.

We consider the sequences of natural integers that can be computed by a deterministic transducer, with input in an arbitrary structure, output in natural integers, and with memory the set of stacks of stacks of the structure. We show, by constructive proofs, that these sequences are exactly the counting sequences of formal languages generated by unambiguous context-free indexed grammars, with indexes in the structure. This general theorem applies, notably, to the structure of natural integers endowed with the decrement operation, showing that the polynomial recurrences count exactly the index-languages.

An integer linear-exponential straight line program (ILESLP) over the base 2 is an arithmetic circuit/program with gates for addition, multiplication by rationals, and taking exponent with base 2. For example, $\{x := 2^y,\; y = 3z + w;\; z = 2^5,\; w = 7\}$ is an ILESLP representing the value $2^{3 \cdot 2^5 + 7}$. ILESLPs can be used to efficiently encode the solutions of integer linear-exponential programs, which extend integer linear programs with the functions $x \mapsto 2^x$ and $(x,y) \mapsto (x \bmod 2^y)$. Recently, it was shown that the optimal solutions of such programs have polynomial-sized ILESLPs. However, for such an encoding of huge integers to be useful, it is desirable to have efficient algorithms for performing computations over them. I will briefly discuss algorithms to validate the well-formedness of a given ILESLP and determine whether it represents a positive integer (PosSLP). I will then introduce a few interesting open problems, such as performing binary search over a set of ILESLPs and solving the PosSLP problem for ILESLP with two bases.

$k$-recognizable sets of nonnegative integer vectors are those whose $k$-ary representations form regular languages. For any $k \ge 2$, this yields a distinct, well-behaved superclass of semilinear sets. A classical result states that $k$-recognizable sets are exactly those that can be defined in Büchi arithmetic, linear integer arithmetic extended with a function $V_k$ yielding the largest divisor of its argument which is a power of $k$.

We consider a parametric setting where the base $k$ itself is treated as a variable. For a single formula, different bases often define an infinite family of distinct sets. We establish a connection between this parametric arithmetic and a class of symbolic automata. Furthermore, we establish a deep structural insight: a first-order sentence of parametric Büchi arithmetic is effectively equivalent to a Presburger constraint on the base—resolving an open question from 2021.

This talk is based on joint work with Alessio Mansutti and Mikhail Starchak.

The sum of square-roots problem is an important computational problem in numerical analysis, with applications to computational geometry: Given positive integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$, check if $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} > \sqrt{b_1} + \sqrt{b_2} + \cdots + \sqrt{b_m}$. The problem has a trivial linear time algorithm on the real RAM (just compute the sums and compare them!) but surprisingly this is not a polynomial time algorithm in the traditional Turing machine model. This problem naturally occurs in computational geometry, particularly in Euclidean shortest path problems, complicating the transfer of algorithms from the real RAM to the standard integer RAM.

I will survey what is known about this problem and the difficulty in obtaining an efficient algorithm. I will present an interesting observation that gives an "efficient algorithm" for certain special cases of the problem and explain what it would take to make "efficient" actually efficient for the general case.

Expressing formal languages is a natural role of variables in word equations. For instance, the equation $X = Ya$ asserts that the assignment to $X$ should belong to the language $\Sigma^* a$. The induced class of languages is not well-understood. String-solving, perhaps the foremost application of this expression mechanism, must be done tractably, and thus practical examples of word equations often have restricted form. A natural question is how this impacts the expressivity. It is known that the mechanism becomes strictly more powerful each time one more variable is allowed. We study the classes of languages expressed by quadratic and subquadratic equations, wherein the structure of the equation is constrained, yet arbitrarily many variables are permitted. We separate the associated hierarchy of language classes. Sometimes, we are able to describe these language classes explicitly. In other cases, combinatorial hurdles (e.g. non-parameterisability) or difficult examples prevent us from doing so. Lots of (non-)closure properties result.