29.40/9.24 YES 29.69/9.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 29.69/9.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 29.69/9.29 29.69/9.29 29.69/9.29 Termination of the given RelTRS could be proven: 29.69/9.29 29.69/9.29 (0) RelTRS 29.69/9.29 (1) RelTRSRRRProof [EQUIVALENT, 66 ms] 29.69/9.29 (2) RelTRS 29.69/9.29 (3) RelTRSRRRProof [EQUIVALENT, 75 ms] 29.69/9.29 (4) RelTRS 29.69/9.29 (5) RelTRSRRRProof [EQUIVALENT, 36 ms] 29.69/9.29 (6) RelTRS 29.69/9.29 (7) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 192 ms] 29.69/9.29 (8) RelTRS 29.69/9.29 (9) RelTRSRRRProof [EQUIVALENT, 0 ms] 29.69/9.29 (10) RelTRS 29.69/9.29 (11) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 112 ms] 29.69/9.29 (12) RelTRS 29.69/9.29 (13) RelTRSRRRProof [EQUIVALENT, 14 ms] 29.69/9.29 (14) RelTRS 29.69/9.29 (15) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 56 ms] 29.69/9.29 (16) RelTRS 29.69/9.29 (17) RelTRSRRRProof [EQUIVALENT, 40 ms] 29.69/9.29 (18) RelTRS 29.69/9.29 (19) RIsEmptyProof [EQUIVALENT, 0 ms] 29.69/9.29 (20) YES 29.69/9.29 29.69/9.29 29.69/9.29 ---------------------------------------- 29.69/9.29 29.69/9.29 (0) 29.69/9.29 Obligation: 29.69/9.29 Relative term rewrite system: 29.69/9.29 The relative TRS consists of the following R rules: 29.69/9.29 29.69/9.29 Tl(O(x), y) -> Wr(check(x), y) 29.69/9.29 Tl(O(x), y) -> Wr(x, check(y)) 29.69/9.29 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, O(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, O(y)) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tl(B, y) -> Wr(check(B), y) 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 Tr(x, B) -> Wl(x, check(B)) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(O(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(O(x), y) -> Wl(x, check(y)) 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, O(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, O(y)) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 Wr(x, ok(y)) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (1) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Polynomial interpretation [POLO]: 29.69/9.30 29.69/9.30 POL(B) = 0 29.69/9.30 POL(N(x_1)) = x_1 29.69/9.30 POL(O(x_1)) = 1 + x_1 29.69/9.30 POL(Tl(x_1, x_2)) = x_1 + x_2 29.69/9.30 POL(Tr(x_1, x_2)) = x_1 + x_2 29.69/9.30 POL(Wl(x_1, x_2)) = x_1 + x_2 29.69/9.30 POL(Wr(x_1, x_2)) = x_1 + x_2 29.69/9.30 POL(check(x_1)) = x_1 29.69/9.30 POL(ok(x_1)) = x_1 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tl(O(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(O(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, O(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, O(y)) -> Wl(x, check(y)) 29.69/9.30 Rules from S: 29.69/9.30 29.69/9.30 Tl(O(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(O(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, O(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, O(y)) -> Wr(x, check(y)) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (2) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tl(B, y) -> Wr(check(B), y) 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 Tr(x, B) -> Wl(x, check(B)) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 Wr(x, ok(y)) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (3) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tl(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(N(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wr(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(check(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tr(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wl(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(B) = [[0], [1]] 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(O(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(ok(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tr(x, B) -> Wl(x, check(B)) 29.69/9.30 Rules from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (4) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tl(B, y) -> Wr(check(B), y) 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 Wr(x, ok(y)) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (5) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tl(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(N(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wr(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(check(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tr(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wl(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(B) = [[0], [1]] 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(O(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(ok(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tl(B, y) -> Wr(check(B), y) 29.69/9.30 Rules from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (6) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 Wr(x, ok(y)) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (7) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 29.69/9.30 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We use semantic labelling over boolean tuples of size 1. 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We used the following model: 29.69/9.30 29.69/9.30 Tl_2: component 1: OR[] 29.69/9.30 29.69/9.30 N_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Wl_2: component 1: OR[] 29.69/9.30 29.69/9.30 check_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Tr_2: component 1: OR[] 29.69/9.30 29.69/9.30 Wr_2: component 1: OR[] 29.69/9.30 29.69/9.30 B_0: component 1: OR[] 29.69/9.30 29.69/9.30 O_1: component 1: AND[] 29.69/9.30 29.69/9.30 ok_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelling function was: 29.69/9.30 29.69/9.30 Tl_2:component 1: AND[x_1^1] 29.69/9.30 29.69/9.30 N_1:component 1: XOR[x_1^1] 29.69/9.30 29.69/9.30 Wl_2:component 1: XOR[-x_2^1] 29.69/9.30 29.69/9.30 check_1:component 1: XOR[] 29.69/9.30 29.69/9.30 Tr_2:component 1: OR[] 29.69/9.30 29.69/9.30 Wr_2:component 1: AND[-x_2^1] 29.69/9.30 29.69/9.30 B_0:component 1: AND[] 29.69/9.30 29.69/9.30 O_1:component 1: OR[] 29.69/9.30 29.69/9.30 ok_1:component 1: XOR[-x_1^1] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelled system was: 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wl^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wl^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wl^[t](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wl^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wl^[t](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wl^[f](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[t]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[t]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]B^[t] -> ^[f]N^[f](^[f]B^[t]) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]O^[f](^[f]x)) -> ^[t]ok^[f](^[t]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]Wl^[t](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]Tl^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[f](^[f]ok^[t](^[f]x), ^[t]y) -> ^[f]Tl^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[t](^[t]ok^[f](^[t]x), ^[f]y) -> ^[f]Tl^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[f](^[t]ok^[f](^[t]x), ^[t]y) -> ^[f]Tl^[t](^[t]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[t](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tl^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tl^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[t](^[t]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tl^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wl^[f](^[t]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tl^[t](^[t]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[t](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]Tr^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[f](^[f]ok^[t](^[f]x), ^[t]y) -> ^[f]Tr^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[t](^[t]ok^[f](^[t]x), ^[f]y) -> ^[f]Tr^[f](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[f](^[t]ok^[f](^[t]x), ^[t]y) -> ^[f]Tr^[f](^[t]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[t](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tr^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Wr^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tr^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]O^[f](^[f]x)) -> ^[t]O^[f](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]O^[f](^[t]x)) -> ^[t]O^[f](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]N^[f](^[f]x)) -> ^[f]N^[f](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]N^[t](^[t]x)) -> ^[t]N^[t](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[t]O^[f](^[f]ok^[t](^[f]x)) -> ^[t]ok^[f](^[t]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]O^[f](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]O^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]N^[f](^[f]ok^[t](^[f]x)) -> ^[f]ok^[t](^[f]N^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]N^[t](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]N^[t](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wr^[t](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wr^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wr^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wr^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wr^[t](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wr^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wr^[t](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wr^[f](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[t]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[t]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]B^[t], ^[f]y) -> ^[f]Wr^[t](^[f]B^[t], ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[f]Tl^[f](^[f]B^[t], ^[t]y) -> ^[f]Wr^[f](^[f]B^[t], ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[f]x, ^[f]B^[t]) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]B^[t]) 29.69/9.30 29.69/9.30 ^[f]Tr^[f](^[t]x, ^[f]B^[t]) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]B^[t]) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our polynomial interpretation was: 29.69/9.30 29.69/9.30 P(Tl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(N^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(N^[true])(x_1) = 1 + 1*x_1 29.69/9.30 29.69/9.30 P(Wl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(check^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(check^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(B^[false])() = 0 29.69/9.30 29.69/9.30 P(B^[true])() = 0 29.69/9.30 29.69/9.30 P(O^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(O^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[true])(x_1) = 1 + 1*x_1 29.69/9.30 29.69/9.30 29.69/9.30 The following rules were deleted from R: 29.69/9.30 none 29.69/9.30 29.69/9.30 The following rules were deleted from S: 29.69/9.30 29.69/9.30 Wr(x, ok(y)) -> Tr(x, y) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (8) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (9) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tl(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(N(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wr(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(check(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tr(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wl(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(B) = [[0], [1]] 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(O(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(ok(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tl(B, y) -> Wr(B, check(y)) 29.69/9.30 Rules from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (10) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (11) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 29.69/9.30 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We use semantic labelling over boolean tuples of size 1. 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We used the following model: 29.69/9.30 29.69/9.30 Tl_2: component 1: AND[] 29.69/9.30 29.69/9.30 N_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Wl_2: component 1: AND[] 29.69/9.30 29.69/9.30 check_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Tr_2: component 1: AND[] 29.69/9.30 29.69/9.30 Wr_2: component 1: AND[] 29.69/9.30 29.69/9.30 B_0: component 1: AND[] 29.69/9.30 29.69/9.30 O_1: component 1: OR[] 29.69/9.30 29.69/9.30 ok_1: component 1: OR[] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelling function was: 29.69/9.30 29.69/9.30 Tl_2:component 1: XOR[-x_2^1] 29.69/9.30 29.69/9.30 N_1:component 1: XOR[-x_1^1] 29.69/9.30 29.69/9.30 Wl_2:component 1: AND[x_1^1] 29.69/9.30 29.69/9.30 check_1:component 1: OR[] 29.69/9.30 29.69/9.30 Tr_2:component 1: XOR[x_2^1] 29.69/9.30 29.69/9.30 Wr_2:component 1: AND[-x_1^1, x_2^1] 29.69/9.30 29.69/9.30 B_0:component 1: XOR[] 29.69/9.30 29.69/9.30 O_1:component 1: OR[] 29.69/9.30 29.69/9.30 ok_1:component 1: XOR[] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelled system was: 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[f](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[t](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[t](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[t](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[t](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]B^[f] -> ^[t]N^[f](^[t]B^[f]) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tl^[t](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[f]ok^[f](^[f]x), ^[t]y) -> ^[t]Tl^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[f]x, ^[f]ok^[f](^[t]y)) -> ^[t]Tl^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[t]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[t]x, ^[f]ok^[f](^[t]y)) -> ^[t]Tl^[f](^[t]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Wr^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tr^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wr^[t](^[f]ok^[f](^[f]x), ^[t]y) -> ^[t]Tr^[t](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]O^[f](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[t]x)) -> ^[f]O^[f](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]N^[t](^[f]x)) -> ^[f]N^[t](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]N^[f](^[t]x)) -> ^[t]N^[f](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]O^[f](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]N^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]N^[t](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]N^[t](^[f]ok^[f](^[t]x)) -> ^[f]ok^[f](^[t]N^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wr^[t](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wr^[t](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wr^[f](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[f](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[f](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[t](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[t](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[f]x, ^[t]B^[f]) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]B^[f]) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]B^[f]) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]B^[f]) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our polynomial interpretation was: 29.69/9.30 29.69/9.30 P(Tl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(N^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(N^[true])(x_1) = 1 + 1*x_1 29.69/9.30 29.69/9.30 P(Wl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(check^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(check^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(B^[false])() = 0 29.69/9.30 29.69/9.30 P(B^[true])() = 0 29.69/9.30 29.69/9.30 P(O^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(O^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 29.69/9.30 The following rules were deleted from R: 29.69/9.30 29.69/9.30 Tr(x, N(y)) -> Wl(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wl(x, check(y)) 29.69/9.30 29.69/9.30 The following rules were deleted from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (12) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (13) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tl(x_1, x_2)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(N(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wr(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(check(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Tr(x_1, x_2)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(B) = [[0], [0]] 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(Wl(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(O(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 <<< 29.69/9.30 POL(ok(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 29.69/9.30 >>> 29.69/9.30 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(x, check(y)) 29.69/9.30 Rules from S: 29.69/9.30 29.69/9.30 Tr(x, N(y)) -> Wr(x, check(y)) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (14) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (15) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 29.69/9.30 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We use semantic labelling over boolean tuples of size 1. 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 We used the following model: 29.69/9.30 29.69/9.30 Tl_2: component 1: AND[] 29.69/9.30 29.69/9.30 N_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Wl_2: component 1: AND[] 29.69/9.30 29.69/9.30 check_1: component 1: OR[x_1^1] 29.69/9.30 29.69/9.30 Tr_2: component 1: AND[] 29.69/9.30 29.69/9.30 Wr_2: component 1: AND[] 29.69/9.30 29.69/9.30 B_0: component 1: AND[] 29.69/9.30 29.69/9.30 O_1: component 1: OR[] 29.69/9.30 29.69/9.30 ok_1: component 1: OR[] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelling function was: 29.69/9.30 29.69/9.30 Tl_2:component 1: XOR[x_1^1] 29.69/9.30 29.69/9.30 N_1:component 1: OR[-x_1^1] 29.69/9.30 29.69/9.30 Wl_2:component 1: XOR[-x_1^1] 29.69/9.30 29.69/9.30 check_1:component 1: OR[] 29.69/9.30 29.69/9.30 Tr_2:component 1: XOR[x_1^1] 29.69/9.30 29.69/9.30 Wr_2:component 1: XOR[] 29.69/9.30 29.69/9.30 B_0:component 1: AND[] 29.69/9.30 29.69/9.30 O_1:component 1: OR[] 29.69/9.30 29.69/9.30 ok_1:component 1: XOR[x_1^1] 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our labelled system was: 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[t](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[f](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[t](^[f]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[t](^[f]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[f](^[t]x, ^[f]check^[f](^[f]y)) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[f](^[t]x, ^[t]check^[f](^[t]y)) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y) 29.69/9.30 29.69/9.30 ^[t]B^[t] -> ^[t]N^[f](^[t]B^[t]) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tl^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[f]ok^[t](^[t]x), ^[f]y) -> ^[t]Tl^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[t](^[f]x, ^[f]ok^[t](^[t]y)) -> ^[t]Tl^[f](^[f]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[t]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wl^[f](^[t]x, ^[f]ok^[t](^[t]y)) -> ^[t]Tl^[t](^[t]x, ^[t]y) 29.69/9.30 29.69/9.30 ^[t]Wr^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tr^[f](^[f]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Wr^[f](^[f]ok^[t](^[t]x), ^[f]y) -> ^[t]Tr^[t](^[t]x, ^[f]y) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]O^[f](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]O^[f](^[t]x)) -> ^[f]O^[f](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]check^[f](^[f]N^[t](^[f]x)) -> ^[f]N^[t](^[f]check^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[t]check^[f](^[t]N^[f](^[t]x)) -> ^[t]N^[f](^[t]check^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]O^[f](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]O^[f](^[f]ok^[t](^[t]x)) -> ^[f]ok^[f](^[f]O^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[f]N^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]N^[t](^[f]x)) 29.69/9.30 29.69/9.30 ^[f]N^[t](^[f]ok^[t](^[t]x)) -> ^[f]ok^[t](^[t]N^[f](^[t]x)) 29.69/9.30 29.69/9.30 ^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y) 29.69/9.30 29.69/9.30 ^[t]Tr^[f](^[f]x, ^[t]B^[t]) -> ^[t]Wl^[t](^[f]check^[f](^[f]x), ^[t]B^[t]) 29.69/9.30 29.69/9.30 ^[t]Tr^[t](^[t]x, ^[t]B^[t]) -> ^[t]Wl^[f](^[t]check^[f](^[t]x), ^[t]B^[t]) 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 Our polynomial interpretation was: 29.69/9.30 29.69/9.30 P(Tl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tl^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(N^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(N^[true])(x_1) = 1 + 1*x_1 29.69/9.30 29.69/9.30 P(Wl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(check^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(check^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Tr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(Wr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 29.69/9.30 29.69/9.30 P(B^[false])() = 0 29.69/9.30 29.69/9.30 P(B^[true])() = 0 29.69/9.30 29.69/9.30 P(O^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(O^[true])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[false])(x_1) = 0 + 1*x_1 29.69/9.30 29.69/9.30 P(ok^[true])(x_1) = 1 + 1*x_1 29.69/9.30 29.69/9.30 29.69/9.30 The following rules were deleted from R: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wr(check(x), y) 29.69/9.30 29.69/9.30 The following rules were deleted from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (16) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 The relative TRS consists of the following R rules: 29.69/9.30 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (17) RelTRSRRRProof (EQUIVALENT) 29.69/9.30 We used the following monotonic ordering for rule removal: 29.69/9.30 Tr/2(YES,YES) 29.69/9.30 B/0) 29.69/9.30 Wl/2(YES,YES) 29.69/9.30 check/1)YES( 29.69/9.30 Tl/2(YES,YES) 29.69/9.30 N/1)YES( 29.69/9.30 Wr/2(YES,YES) 29.69/9.30 O/1)YES( 29.69/9.30 ok/1)YES( 29.69/9.30 29.69/9.30 Quasi precedence: 29.69/9.30 [Tr_2, Wr_2] > [Wl_2, Tl_2] 29.69/9.30 B > [Wl_2, Tl_2] 29.69/9.30 29.69/9.30 29.69/9.30 Status: 29.69/9.30 Tr_2: multiset status 29.69/9.30 B: multiset status 29.69/9.30 Wl_2: multiset status 29.69/9.30 Tl_2: multiset status 29.69/9.30 Wr_2: multiset status 29.69/9.30 29.69/9.30 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 29.69/9.30 Rules from R: 29.69/9.30 29.69/9.30 Tr(x, B) -> Wl(check(x), B) 29.69/9.30 Rules from S: 29.69/9.30 none 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (18) 29.69/9.30 Obligation: 29.69/9.30 Relative term rewrite system: 29.69/9.30 R is empty. 29.69/9.30 The relative TRS consists of the following S rules: 29.69/9.30 29.69/9.30 Tl(N(x), y) -> Wl(check(x), y) 29.69/9.30 Tl(N(x), y) -> Wl(x, check(y)) 29.69/9.30 Tr(x, N(y)) -> Wr(check(x), y) 29.69/9.30 B -> N(B) 29.69/9.30 check(O(x)) -> ok(O(x)) 29.69/9.30 Wl(ok(x), y) -> Tl(x, y) 29.69/9.30 Wl(x, ok(y)) -> Tl(x, y) 29.69/9.30 Wr(ok(x), y) -> Tr(x, y) 29.69/9.30 check(O(x)) -> O(check(x)) 29.69/9.30 check(N(x)) -> N(check(x)) 29.69/9.30 O(ok(x)) -> ok(O(x)) 29.69/9.30 N(ok(x)) -> ok(N(x)) 29.69/9.30 29.69/9.30 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (19) RIsEmptyProof (EQUIVALENT) 29.69/9.30 The TRS R is empty. Hence, termination is trivially proven. 29.69/9.30 ---------------------------------------- 29.69/9.30 29.69/9.30 (20) 29.69/9.30 YES 31.46/11.18 EOF