All reports by Author Mohand-Saïd Hacid:

__
TR12-069
| 23rd March 2012
__

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry#### On the complexity of computing minimal unsatisfiable LTL formulas

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

We show that (1) the Minimal False QCNF search problem (MF-search) and

the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ...
more >>>