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

Approximate Satisfiability and Equivalence

Visit website for this news | Export event in iCalendar format

Date
Tuesday, March 11 2008 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Michel de Rougemont (LRI)

We show how to approximate decision problems such as satisfiability of a formula by a structure, or Equivalence between two formulas, such that we gain an exponential factor (or more) in complexity. A typical case is to decide if two Non-deterministic automata are equivalent: we decide the approximate version in polynomial time whereas the exact version is PSPACE complete. For Pushdown automata, we decide the approximate version in exponential time whereas the exact version is undecidable.


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Feb 19

Past seminars