The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
In sets with atoms, finiteness is relaxed to ''finiteness up to permutation'', formally defined as orbit-finiteness. The talk will be an overview of models of computation, such as (various kinds of) automata, Petri nets or Turing machines, where state spaces, input alphabets and transition relations are orbit-finite sets with atoms. I will focus on fundamental properties, such as (lack of) determinisation, and on fundamental analysis problems, such as reachability. I will also mention recently discovered links to descriptive complexity, constraint satisfaction, and model theory.
(joint work with Mikołaj Bojańczyk, Bartek Klin, Joanna Ochremiak and Szymon Toruńczyk)