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.
Reachability is a fundamental problem in the context of many finite and infinite state systems, computational models, hybrid and dynamical systems, rewriting systems, probabilistic and parametric systems, and open systems modelled as games. In general terms, it can be formalized as follows: for a computation model specified via a set of allowed rules or transformations, decide whether a certain state is reachable from a given initial state.
The proposed talk will be focused on reachability problems for classical mathematical objects, which naturally appear in many computational processes and abstractions. I will mainly focus on such objects as words, matrices, iterative maps, knots, braids and will aim to highlight most recent developments on decidability and complexity results in the area and will illustrate connections of reachability questions with fundamental long standing open problems in mathematics and computer science.