A simplified version of the schedule (with no abstracts) can be found here.

Scientific events will take place in Zeeman D1.07.
Coffee breaks will take place in Zeeman C1.14.
Meals will take place in Scarman Conference Centre Dining Hall.

1 April 2025

09:30-10:00 Coffee Break

10:00-10:15 Welcome

10:15-11:00 Invited Talk: Non-sequential finite automata (Robert Mercas, Loughborough University)
In this presentation I will be discussing some not well-known models of finite automata that process the tape in a non-sequential manner. To this end, I will be focusing on a model introduced almost 10 years ago, the right-one way jumping finite automata, and provide some complexity insights with respect to them.

11:00-11:15 Introduction Session
Each attendee will be asked to introduce themselves briefly (30-60 seconds).

11:15-12:15 Early Career Researcher Talks

1. A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter (Henry Sinclair-Banks, University of Warsaw)
2. Word Equations’ Length Abstractions using Rational Subsets of Matrix Semigroups (Matthew Konefal, University of Loughborough)
3. Nominal Logics for Fresh-Register Automata (Mohamed Bandukara, Queen Mary, University of London)
4. A distance-based robustness measure for a timed logic over signals (Neha Rino, University of Warwick)

12:30-14:30 Lunch

14:30-15:15 Invited Talk: Arithmetical subword complexity of automatic sequences (Jakub Konieczny, University of Oxford)
It is well-known that the subword complexity of an automatic sequence grows at most linearly, meaning that the number of length-l subwords which appear in a given automatic sequence a = (a(n))_n is at most Cl for a constant C dependent only on a. In contrast, arithmetic subword complexity measures the number of subwords which appear along arithmetic progressions, and can grow exponentially even for very simple automatic sequences. Indeed, the classical Thue-Morse sequence has arithmetic subword complexity 2^l, which is the maximal possible complexity for {0,1}-valued sequence. Together with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us to express any (complex-valued) automatic sequence as the sum of a structured part, which is easy to work with, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now apply these techniques to the study of arithmetic subword complexity of automatic sequences. We show that for each automatic sequence a there exists a parameter r --- which we dub "effective alphabet size" --- such that the arithmetic subword complexity of a is at least r^l and at most (r+o(1))^l.

15:15-16:00 Open Problem Session
Bring your open problems! Please feel free to send slides in advance or indicate interest in presenting a problem by emailing the organisers.

16:00-16:30 Coffee Break

16:30-17:15 Invited Talk: Learning weighted automata over general semirings (Laure Daviaud, University of East Anglia)
We consider active learning of models of automata by equivalence and membership queries, in an Angluin style. (Fast) learning algorithms have been developed for weighted automata over specific semirings such as fields. In this talk, we present a general framework for learning weighted automata over semirings. This framework does not guarantee the existence of fast learning algorithms but gives the limitations of this approach when it comes to more exotic semirings such as the tropical semiring. (Joint work with Marianne Johnson - University of Manchester).

17:15-18:00 Invited Talk: Determinisation and Unambiguisation of Weighted Automata (David Purser, University of Liverpool)
We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata. If time allows, I’ll also talk briefly about the problem in the max, plus semiring.

19:00-20:30 Dinner

2 April 2025

09:00-09:45 Invited Talk: The complexity of Orbit-Closure problems (Mahsa Shirmohammadi, IRIF)
Computational problems concerning the orbit of a point under the action of a matrix group occur in numerous subfields of computer science, including complexity theory, program analysis, quantum computation, and automata theory. In many cases the focus extends beyond orbits proper to orbit closures under a suitable topology. Typically one starts from a group and several points and asks questions about the orbit closure of the points under the action of the group, e.g., whether two given orbit closures intersect. In this talk, I will introduce and motivate several problems involving groups and orbit closures, focusing on computation and determination tasks. In regards to computation, we are given a set of matrices and tasked with computing the defining ideal of the algebraic group generated by those matrices. The determination task, on the other hand, involves starting with a given variety and determining whether and how it can be represented as an algebraic group or an orbit closure. The “how” question often asks whether the underlying group can be topologically generated by s matrices for a given s.

09:45-10:15 Coffee Break

10:15-11:00 Invited Talk: Comparing labelled Markov decision processes via probabilistic bisimilarity distances (Qiyi Tang, University of Liverpool)
A labelled Markov decision process (MDP) is a labelled Markov chain with nondeterminism; i.e., together with a strategy a labelled MDP induces a labelled Markov chain. The model is related to interval Markov chains. Motivated by applications to the verification of probabilistic noninterference in security, we study problems of comparing labelled MDPs via probabilistic bisimilarity distances, in particular, whether there exist strategies such that the probabilistic bisimilarity distance between the induced labelled Markov chains is less than (or greater than) a given rational number, both for memoryless strategies and general strategies. We show that the distance minimisation and maximisation problems are ExTh(R)-complete for memoryless strategies and undecidable for general strategies. We also study the computational complexity of the qualitative problems about making the distance less than or equal to one.

11:00-12:15 Early Career Researcher Talks

1. Robust probabilistic bisimilarity for labelled Markov chains (Zainab Fatmi, University of Oxford)
2. FC-Datalog as a Framework for Efficient String Querying (Owen Bell, Loughborough University)
3. On the limits of PAC learning of networks from opinion dynamics (Luisa Estrada, University of Warwick)
4. Good Games for Recognising Good-for-Games Automata (Aditya Prakash, University of Warwick)

12:30-14:30 Lunch

14:30-15:15 Invited Talk: Iterations of Piecewise Maps (Edon Kelmendi, Queen Mary, University of London)
I will present a few aspects of the reachability problem for piecewise affine maps. These are functions f from the unit interval to itself, such that there is a partition of the domain into intervals where f is affine, i.e. of the form ax+b. They are related to hybrid systems, expansions of numbers into non-integral bases, discount-sum automata etc. The reachability problem asks for a procedure which inputs such a map, a source and target point, and decides whether by iterating the map on the source we reach the target. No such procedure is known. I will give one for injective maps.

15:15-16:30 Discussion and Closing