Tag: logic

I prove the accuracy of the naive correspondence of the strings with the help of Hoare logic. I have the following pseudocode:

            NaiveStringMatch (T, P)
         0 characters
P is an array of m> 0 characters>

for (s = 0 to T.length - P.length)
<invariant: for all 0 ≤ s' < s there is no match>
           j = 1
while (j ≤ P.length and P[j] == T[s + j])
              
              j ++
if (j == P.length + 1)
results
back -1
         -1 then P[i] == T[i + s], 1 ≤ i ≤ m,
and there are no s & # 39; < s for which this holds>

The thing I'm fighting with is the conditional statement

if (j == P.length + 1)
results

In particular, the Hoare logic test rule for the conditions, and the required postcondition, $ psi $, in that case. The conditional rule looks like this:

$$ frac { { phi coin B } C_1 { psi } > > > > { phi coin neg B } C_2 { psi }} { { phi } > > if > > B > > then > > C_1 > > else > > C_2 > > { psi }} $$

My precondition, $ phi $, is it:
$$ phi = text {for all teams} 0 leq s <text there is no match and} \ P[1…j] text {matches the corresponding characters in} T[s…s + j]$$

The postcondition, $ psi $what was given to me is this:

$$ psi = text {for all teams} 0 leq s text {there is no match} $$

Looking a little closer, we notice that when the inner loop ends, then j ≤ P.length + 1. There are two cases:

1) if j <P.length + 1then P does not match T to change sThus, the outer for loop invariant is retained. After evaluating the statement though, we also satisfy $ psi $, since there is no match when $ s = s $.

2) if j == P.length + 1, P matches T to change sand the algorithm ends when returning s. Thus, the outer for loop invariant is retained. Now it is there that I am confused. After evaluating the if statement, how $ psi $ satisfied here? Because after the if statement is executed, we can clearly find the offset $ s = s $ for which there is a valid match. So in my mind $ psi $ is not satisfied. Unless the return return means we do not need to check $ psi $ and therefore, we simply ignore the fact that $ psi $ is not satisfied?