Automata in the Wild 2026

Classical automata theory traditionally studies finite-state machines operating over one-dimensional words or counter-based extensions such as Minsky machine. However, many natural computational phenomena arise in environments where computation involves multidimensional structures, algebraic transformations, relational data, or infinite interactions. In such settings, classical models no longer provide adequate abstractions.

In this talk, we survey a family of non-classical automata models, which could be referred to as "wild" automata. These models arise naturally from fundamental computational problems across several areas of theoretical computer science. Examples include finite automata operating in two-dimensional environments, insertion–deletion systems over relational words, weighted automata on infinite words, linear recurrence automata, and automata defined by matrix and polynomial transformations.

Together, these examples illustrate how diverse problems can be viewed through a common automata-theoretic lens, highlighting wild automata as natural abstractions for studying the limits of computation beyond the classical setting.

Regular functions are a well-understood class of string-to-string functions. They are the functions which are recognisable by deterministic two-way transducers, and consequently, the output length is at most linear in terms of the input length. To enable polynomial growth, we can enlarge the configuration space by equipping the transducer with multiple reading heads. When only one head moves at a time, we can envision the resting heads as pebbles, markers that are dropped and picked up while navigating the input.

The resulting class of polyregular functions has proven highly robust. Multiple equivalent characterisations across logic and automata theory have been found, and variations of the corresponding models have been studied. My talk aims to give an accessible guide through the history and evolution of polyregular functions. I will discuss the intuition behind the equivalence of various characterisations as well as the relations between their complexity parameters. In particular, we will explore the somewhat surprising asymmetric connection between the number of pebbles and the degree of the growth polynomial.

Given $k$ nondeterministic finite automata (NFA) $A_1, \dots, A_k$, finding an NFA for the language $L(A_1) \cap \dots \cap L(A_k)$ is a basic problem in automata theory. We observe that the classical Cartesian product construction is non-optimal in the worst case, that is, if the automata have many transitions. For a fixed alphabet, the Cartesian product of two NFA may have $\Theta(m^2)$ transitions if these NFA have at most $n$ states and $m$ transitions each.

In this talk, we describe alternative constructions with $O(m n)$ transitions; or $O(m n^{k-1})$ for the intersection of $k$ NFA (for fixed $k \ge 2$ and alphabet $\Sigma$). This gives a faster algorithm for deciding NFA intersection emptiness, that is, deciding whether $k$ given NFA accept a word in common. We also show that this new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting $(k+1)$-cliques in undirected graphs. Lastly, we show how these new product constructions allow us to certify NFA intersection emptiness faster.

Infinite words can be used to encode interesting properties of the orbits of discrete dynamical systems. Analysing the complexity of such a system may then be analysed through this encoding. Combinatorially speaking, quite often its complexity is measured through its finite factors, or finite contiguous blocks appearing in the infinite encoding. For example, the factor complexity function (counting the number of distinct blocks of a given length) reveals interesting global properties of the word, and the notion has been applied successfully, e.g., in transcendental number theory. Other combinatorial complexity functions have also been introduced in recent years.

When an infinite word has a finite description (e.g., it is generated by a Deterministic Finite Automaton with Output (DFAO)), one might hope that its combinatorial complexity functions also have finite descriptions (e.g., given by a weighted automaton over the integers). In this talk, I will give an overview of automatic aspects of combinatorial complexity functions of sequences generated by DFAOs and discuss some recent results and ongoing research about the so-called binomial complexity functions (functions that count factors up to similarity of scattered subword structures) of automatic sequences.

The talk is based on joint work with M. Rigo, M. Stipulanti, and N. Wingate.

Solvency games are a gambling problem on infinite-state MDPs where the investor's fortune, a natural number n, is the state. In every round, the investor chooses an action from a finite action set Act = {A,B,...}, and every action yields a distribution over integer-valued gains/losses in an interval [-x,+y].

The risk-averse investor wants to maximize the chance of staying solvent, i.e., to minimize the probability of eventual ruin (reaching a fortune below zero). A generalized version adds control-states, and thus becomes a problem about 1-counter MDPs.

It is easy to show that solvency games always admit optimal memoryless deterministic strategies σ: ℕ → Act, i.e., the optimal action depends only on the fortune n. However, how does the function σ behave? If the fortune n is sufficiently large, does it suffice to always pick an action σ(n) with maximal expected payoff? Is σ eventually constant, or at least eventually periodic? And is σ computable?

Already in the case of gains in the interval [-3,+1], it is possible for the optimal strategy to be unique but aperiodic (disproving a conjecture of Kucera: RP'2012). However, in the special case of gains in [-2,+1] there always exists an optimal strategy that either has a pure tail or strictly alternates between just two actions.

The optimal strategy is computable if it is unique (but without any known complexity bound). Moreover, some optimal strategy is computable (in time polynomial in n) in the case of gains in [-x,+1], while computability in the general case remains open.

Multi-pushdown automata (MPDA) are a classic computational model that can be used to capture the behavior of multithreaded recursive programs. Here, each parallel thread is simply modeled by a single stack, and there is a fixed number of them. Due to the well known fact that most verification problems are undecidable for MPDA, even with just two stacks, the literature contains many different ways to restrict the runs of this model, in such a manner as to recover decidability. A popular restriction of this kind is known as bounded context-switching: For a fixed bound k, every parallel thread (or stack) may only be interrupted by another thread up to k times.

We consider an extended setting, where the number of parallel threads is not fixed, and more of them can be spawned dynamically during execution. This gives rise to the model of dynamic networks of concurrent pushdown systems (DCPS), which we still restrict with bounded context-switching. In this setting, we consider various verification questions, that have been asked for similar models in the past. These include state reachability, non-termination (with and without assumptions on fairness), and boundedness of the thread buffer. Moreover we consider the novel verification problem of Dyck inclusion: Given a model with action sequences over some alphabet of bracket pairs, are all its executions well-bracketed? Our results close a preexisting complexity gap for state reachability, and settle the complexity of several other verification problems, where in many cases even decidability was unknown before.