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

Reachability in Parametric One-Counter Machines

Visit website for this news | Export event in iCalendar format

 James Worrell
Date
Tuesday, November 03 2009 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
James Worrell (University of Oxford)

In this talk we consider one-counter machines in which counter updates can mention integer-valued parameters. Our main result is to show NP-completeness of the problem of determining whether a given state is reachable from the initial state for some value of the parameters. Membership in NP is shown by reduction to the existential fragment of Presburger arithmetic with divisibility.


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Feb 19

Past seminars