TRS: { sum(0()) -> 0(), sum(s(x)) -> +(sum(x), s(x)), sum1(0()) -> 0(), sum1(s(x)) -> s(+(sum1(x), +(x, x)))} POP* + Boolean Semantic Labelling: Normal positions: pi(sum1_sl=1) = [1], pi(sum1_sl=0) = [1], pi(sum_sl=1) = [1], pi(sum_sl=0) = [1] Safe positions: pi(s_sl=1) = [1], pi(s_sl=0) = [1], pi(+_sl=1) = [1,2], pi(+_sl=0) = [1,2] Precedence: sum_sl=1 > sum_sl=0, sum_sl=1 > +_sl=0, sum1_sl=1 > sum1_sl=0, sum1_sl=1 > s_sl=0, sum1_sl=1 > +_sl=0 empty Interpretation: 0^(0): | 0 sum^(1): 0 | 0 1 | 0 +^(2): 00 | 0 01 | 0 10 | 0 11 | 0 s^(1): 0 | 1 1 | 1 sum1^(1): 0 | 0 1 | 1 Labelling: 0^(0): | 0 sum^(1): 0 | 0 1 | 1 +^(2): 00 | 0 01 | 0 10 | 0 11 | 0 s^(1): 0 | 0 1 | 0 sum1^(1): 0 | 0 1 | 1 Labelled predicative System: { sum_sl=0(0_sl=0();) -> 0_sl=0(), sum_sl=1(s_sl=0(;x);) -> +_sl=0(;sum_sl=0(x;),s_sl=0(;x)), sum_sl=1(s_sl=0(;x);) -> +_sl=0(;sum_sl=1(x;),s_sl=0(;x)), sum1_sl=0(0_sl=0();) -> 0_sl=0(), sum1_sl=1(s_sl=0(;x);) -> s_sl=0(;+_sl=0(;sum1_sl=0(x;),+_sl=0(;x,x))), sum1_sl=1(s_sl=0(;x);) -> s_sl=0(;+_sl=0(;sum1_sl=1(x;),+_sl=0(;x,x)))} Qed