Développer des invariants pour comparer deux chaînes

Question

L'algorithme suivant est censé comparer deux chaînes $ s_1 $ et $ s_2 $ ("/ " pour la chaîne vide):

X = S1   
Y = S2

E = true   
// (1)
while X != /\ and Y != /\ and E == true          
  if head(X) == head(Y)           
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2)
if !(X == /\ and Y == /\)    
  E = false 
  // (3) S1 != S2 \land E = false
// (4) S1 = S2 <=> E = true
return E

Je veux développer des invariants aux points (1) et (2).

L'invariant à (1) je choisis est $$ s_1 = s_2 iff x = y land e = true. $$

De là, je peux dériver un invariant à (2):

$$ (s_1 = s_2 iff x = y land e = true) land lnot (x neq lambda land y neq lambda land e = true). $$

Ensuite, j'ai essayé de simplifier la formule:

$$ (s_1 = s_2 iff x = y land e = true) land (x = lambda lor y = lambda lor e = false) equiv big ((s_1 = s_2 iff x C'est big) lor big ((s_1 = s_2 iff x = y land e = true) land (e = false) big) equiv (s_1 = s_2 iff x = lambda land Y = lambda land e = true) lor (s_1 = s_2 iff x = lambda land y = lambda land e = true) lor big ((s_1 = s_2 iff x C'est big) lor big ((s_1 = s_2 iff x = y land e = true) land (e = false) big) $$

Mes problèmes sont

• La dérivation ci-dessus est-elle correcte? Si oui, comment simplifier encore cette formule? En particulier, comment gérer la deuxième disjonction? Est-ce simplement $ s_1 neq s_2 land e = false $?
• Comment l'invariant à (3) et (4) découle-t-il de celui à (2)?
• Pouvons-nous obtenir un invariant à (2) dans une seule conjonction au lieu de plusieurs disjusts?