A gradual valuation with tuples for general graphs

Using the definitions given in Sections 3.2.1 and 3.2.2, the gradual valuation with tuples given by Definition 10 is applicable for arbitrary graphs after the rewriting process.

Let us apply the rewriting process and Definition 10 on different examples.

Example 7 - Unattacked cycle (continuation)
Consider the following graph:

The rewriting of this graph has been given in Section 3.2.2.

Definition 10 produces:

$v_p(A) = (v_i(A_1^1) \oplus 1) \star \ldots \star (v_i(A_1^n) \oplus 1) \star \ldots$

$v_i(A) = (v_p(A_1^1) \oplus 1) \star \ldots \star (v_p(A_1^n) \oplus 1) \star \ldots$

Applying Definition 10 for different arguments in the rewritten graph produces the following equalities:

• $v(A_n^n) = [0^{\infty},()]$ for each $n \geq 1$
• $v(A_{n-1}^n) = [(),(1)]$ for each $n \geq 2$
• $v(A_n^m) = [v_p(A_{n+2}^m) \oplus 2, v_i(A_{n+2}^m) \oplus 2]$ for each n $\geq 1$ and $m \geq {n+2}$

So, using the above equalities in the formulae giving $v_p(A)$ and $v_i(A)$, we define two sequences of tuples : a sequence ($x_k$, $k \geq 1$) of infinite tuples of even integers, and a sequence ($y_k$, $k \geq 1$) of infinite tuples of odd integers

$x_k = (2) \star (v_i(A_{2k-1}^{2k+1}) \oplus 1) \star \ldots \star (v_i(A_{2k-1}^n) \oplus 1) \star \ldots$

$y_k = (1) \star (v_p(A_{2k-1}^{2k+1}) \oplus 1) \star \ldots \star (v_p(A_{2k-1}^n) \oplus 1) \star \ldots$

From the results stated in Property 7, it is easy to prove that $v_p(A) = x_1$ and for each $k \geq 1$, $x_k = (2) \star (x_{k+1} \oplus 2)$.

Similarly, $v_i(A) = y_1$ and for each $k \geq 1$, $y_k = (1) \star (y_{k+1} \oplus 2)$.

These equations enable to prove that :

For each even integer $p$ $p > 0$, $p$ belongs to each tuple $x_i, i \geq 1$.

For each odd integer $p$, $p$ belongs to each tuple $y_i$, $i \geq 1$.

The proof is done by induction on p.

So, $v(A) = v(B) = [(2,4,6,\ldots), (1,3,5,\ldots)]$.

Then, $v(C) = [(2,4,6,\ldots), (3,5,7,\ldots)]$.

Note that all the above results can be readily extended to an unattacked cycle of length n, $n \geq 2$.

Property 8 (Properties of unattacked cycles)  
For each unattacked cycle, for each argument $A$ of the cycle, $v(A) = [(2,4,6,\ldots), (1,3,5,\ldots)]$.

Example 8 - Attacked cycle (continuation)Consider the following graph:

The rewriting of this graph has been given in Section 3.2.2.

Definition 10 produces:

$v_p(A) = (v_i(D) \oplus 1) \star (v_i(A_1^2) \oplus 1) \star \ldots \star (v_i(A_1^{2n}) \oplus 1) \star \ldots$

$v_i(A) = (v_p(D) \oplus 1) \star(v_p(A_1^2) \oplus 1) \star \ldots \star (v_p(A_1^{2n}) \oplus 1) \star \ldots$

and also

$v(D) = [0^{\infty},()]$

$v(A_n^n) = [(),(1)]$ for each $n \geq 2$

As done in the treatment of Example 7, the formulae giving $v_p(A)$ and $v_i(A)$ can be rewritten in order to bring to light some interesting sequences of tuples.

$x'_k = (v_i(A_{2k-1}^{2k}) \oplus 1) \star \ldots \star (v_i(A_{2k-1}^{2(k+p)}) \oplus 1) \star \ldots$

$y'_k = (1) \star (v_p(A_{2k-1}^{2k}) \oplus 1) \star \ldots \star (v_p(A_{2k-1}^{2(k+p)}) \oplus 1) \star \ldots$

Then, it is easy to prove that $v_p(A) = x'_1$ and for each $k \geq 1$, $x'_k = (x'_{k+1} \oplus 2)$.

Similarly, $v_i(A) = y'_1$ and for each $k \geq 1$, $y'_k = (1) \star (y'_{k+1} \oplus 2)$.

The first equation enables to prove that $x'_1$ is the empty tuple²¹.

The second equation has already been solved and produces $y'_1 = (1,3,5,\ldots)$.

So, $v(A) = [(), (1,3,5,\ldots)]$. For $B$, we can reason as for $A$, and we have $v(B) = [(2,4,6,\ldots),()]$. Then, $v(C) = [(2,4,6,\ldots),()]$, $v(E) = [(),(3,5,7\ldots)]$.

Notation: in order to simplify the writing, we will not repeat the values inside the tuples (we will just indicate under each value how many times it appears). For example:

$$[(2,4,4,6,6,6,8,8,8,8\ldots),(3,5,5,7,7,7,9,9,9,9\ldots)]$$

will be denoted by

$$[(2,\underbrace{4}_{2},\underbrace{6}_{3},\underbrace{8}_{4},... ...nderbrace{5}_{2},\underbrace{7}_{3},\underbrace{9}_{4},\ldots)]$$

Conclusion about cycles

Cycles are expensive since all the values obtained are infinite.

In appendix B, we introduce an algorithm for computing these tupled values. It uses a process of value propagation and is parameterised by a maximum ``number of runs through a cycle''. This number will be used in order to stop the propagation mechanism and to obtain finite (thus incomplete) tupled values.