Separability and games for 1-register automata

Speaker(s)

Mathieu Lehaut

Affiliation

University of Warsaw

Language of the talk

English

Date

Jan. 28, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Separability and games for 1-register automata

Seminar

Seminar Automata Theory

---

The separability problem asks whether two disjoint "complex" sets can be separated by a "simple" one, in the sense that the simple one fully contains one of the complex set and is disjoint from the second one.
Many instances of this problem exist, parameterized by how "complex" and "simple" sets are defined.

Here, we study the case where those sets are languages given by register automata.
Register automata are one (of many) extension of automata that accept words over an infinite alphabet.
Unlike regular automata, non-deterministic register automata are known to be strictly more expressive than deterministic ones.
Thus, it makes sense to consider the separability problem where "complex" sets are languages given by non-deterministic register automata, and "simple" by deterministic ones.

This problem reduces to some two-player game setting whose winning condition is given by a non-deterministic register automaton.
We studied this class of games, with many different combinations of parameters: which player has access to the infinite alphabet, which player the winning condition refers to, which player's strategy we are looking for, and whether we look for a strategy or a finite controller.
We have shown that even for automata with only one register those games are undecidable, for all possible combinations of parameters we considered (which unfortunately means decidability of the separability problem is still open).
It is also known that register automata are very closely related to timed automata, and our results similarly hold for games over timed automata, with one minor exception.

Joint work with S. Lasota, J. Parreaux, and R. Piórkowski.

 

---