# LSV Seminar

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.

## Past Seminars

### Recency-Bounded Verification of Dynamic Database-Driven Systems

- Date
- Tuesday, June 21 2016 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Aiswarya Cyriac (Chennai Mathematical Institute, India)

We propose a formalism to model database-driven systems, called
database manipulating systems (DMS). The actions of a DMS modify the
current instance of a relational database by adding new elements into the
database, deleting tuples from the relations and adding tuples to the
relations. The elements which are modified by an action are chosen by
(full) first-order queries. DMS is a highly expressive model and can be
thought of as a succinct representation of an infinite state relational
transition system, in line with similar models proposed in the literature.
We propose monadic second order logic (MSO-FO) to reason about sequences
of database instances appearing along a run. Unsurprisingly, the
linear-time model checking problem of DMS against MSO-FO is undecidable.
Towards decidability, we propose under-approximate model checking of DMS,
where the under-approximation parameter is the “bound on recency”. In a
k-recency-bounded run, only the most recent k elements in the current
active domain may be modified by an action. More runs can be verified by
increasing the bound on recency. Our main result shows that
recency-bounded model checking of DMS against MSO-FO is decidable, by a
reduction to the satisfiability problem of MSO over nested words.

This is a joint work with Parosh Abdulla, Mohammed Faouzi Atig, Marco Montali and Othmane Rezine.