Frama-C-discuss mailing list archives

This page gathers the archives of the old Frama-C-discuss archives, that was hosted by Inria's gforge before its demise at the end of 2020. To search for mails newer than September 2020, please visit the page of the new mailing list on Renater.

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Frama-c-discuss] Jessie sort specification

Hello Kerstin,

Le mer. 03 juin 2009 13:43:48 CEST,
"Kerstin Hartig" <kerstin.hartig at first.fraunhofer.de> a ?crit :

> the array are growing. There's always a problem with the loop 
> invariants. The post conditions are valid.

Just a remark here: the post-condition is valid modulo the assumption
that the loop invariant is valid (if you have a look at the why gui,
you'll see an hypothesis corresponding to the invariant) and the loop
test is false (same thing). But this still leaves the issue of proving
that the loop invariant holds.

> Is it possible we miss something in the specification? Maybe another loop invariant?
> It is possible to prove that \forall integer k; 0 <= k < size ==> a[k] ==  k;

Not with your current loop invariant. Remember that when considering a
loop, the only thing that jessie knows of all the steps preceding the
current ones is the loop invariant. Conversely, everything which is not
stated in the loop invariant is out of reach. In order to complete the
proof, you'll thus have to add another invariant stating that:
loop invariant \forall integer k; 0<=k<i ==> a[k] == k;
(in fact, since this invariant implies that \forall k; 0<=k<i-1 ==>
a[k]<=a[k+1], the latter becomes useless as a loop invariant).

Best regards,
-- 
E tutto per oggi, a la prossima volta.
Virgile