206.41/53.74 YES 206.41/53.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 206.41/53.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 206.41/53.74 206.41/53.74 206.41/53.74 Termination of the given RelTRS could be proven: 206.41/53.74 206.41/53.74 (0) RelTRS 206.41/53.74 (1) RelTRS Reverse [EQUIVALENT, 0 ms] 206.41/53.74 (2) RelTRS 206.41/53.74 (3) RootLabelingProof [EQUIVALENT, 0 ms] 206.41/53.74 (4) RelTRS 206.41/53.74 (5) RelTRSRRRProof [EQUIVALENT, 754 ms] 206.41/53.74 (6) RelTRS 206.41/53.74 (7) RelTRSRRRProof [EQUIVALENT, 386 ms] 206.41/53.74 (8) RelTRS 206.41/53.74 (9) RIsEmptyProof [EQUIVALENT, 0 ms] 206.41/53.74 (10) YES 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (0) 206.41/53.74 Obligation: 206.41/53.74 Relative term rewrite system: 206.41/53.74 The relative TRS consists of the following R rules: 206.41/53.74 206.41/53.74 a(a(b(b(a(a(x1)))))) -> a(a(b(b(b(b(a(a(x1)))))))) 206.41/53.74 b(b(a(a(b(b(x1)))))) -> b(b(a(a(a(a(b(b(x1)))))))) 206.41/53.74 206.41/53.74 The relative TRS consists of the following S rules: 206.41/53.74 206.41/53.74 a(a(x1)) -> a(a(a(a(a(a(x1)))))) 206.41/53.74 b(b(x1)) -> b(b(b(b(b(b(x1)))))) 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (1) RelTRS Reverse (EQUIVALENT) 206.41/53.74 We have reversed the following relative TRS [REVERSE]: 206.41/53.74 The set of rules R is 206.41/53.74 a(a(b(b(a(a(x1)))))) -> a(a(b(b(b(b(a(a(x1)))))))) 206.41/53.74 b(b(a(a(b(b(x1)))))) -> b(b(a(a(a(a(b(b(x1)))))))) 206.41/53.74 206.41/53.74 The set of rules S is 206.41/53.74 a(a(x1)) -> a(a(a(a(a(a(x1)))))) 206.41/53.74 b(b(x1)) -> b(b(b(b(b(b(x1)))))) 206.41/53.74 206.41/53.74 We have obtained the following relative TRS: 206.41/53.74 The set of rules R is 206.41/53.74 a(a(b(b(a(a(x1)))))) -> a(a(b(b(b(b(a(a(x1)))))))) 206.41/53.74 b(b(a(a(b(b(x1)))))) -> b(b(a(a(a(a(b(b(x1)))))))) 206.41/53.74 206.41/53.74 The set of rules S is 206.41/53.74 a(a(x1)) -> a(a(a(a(a(a(x1)))))) 206.41/53.74 b(b(x1)) -> b(b(b(b(b(b(x1)))))) 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (2) 206.41/53.74 Obligation: 206.41/53.74 Relative term rewrite system: 206.41/53.74 The relative TRS consists of the following R rules: 206.41/53.74 206.41/53.74 a(a(b(b(a(a(x1)))))) -> a(a(b(b(b(b(a(a(x1)))))))) 206.41/53.74 b(b(a(a(b(b(x1)))))) -> b(b(a(a(a(a(b(b(x1)))))))) 206.41/53.74 206.41/53.74 The relative TRS consists of the following S rules: 206.41/53.74 206.41/53.74 a(a(x1)) -> a(a(a(a(a(a(x1)))))) 206.41/53.74 b(b(x1)) -> b(b(b(b(b(b(x1)))))) 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (3) RootLabelingProof (EQUIVALENT) 206.41/53.74 We used plain root labeling [ROOTLAB] with the following heuristic: 206.41/53.74 LabelAll: All function symbols get labeled 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (4) 206.41/53.74 Obligation: 206.41/53.74 Relative term rewrite system: 206.41/53.74 The relative TRS consists of the following R rules: 206.41/53.74 206.41/53.74 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))) 206.41/53.74 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))) 206.41/53.74 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 206.41/53.74 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 206.41/53.74 206.41/53.74 The relative TRS consists of the following S rules: 206.41/53.74 206.41/53.74 a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) 206.41/53.74 a_{a_1}(a_{b_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) 206.41/53.74 b_{b_1}(b_{a_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 206.41/53.74 b_{b_1}(b_{b_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 206.41/53.74 206.41/53.74 206.41/53.74 ---------------------------------------- 206.41/53.74 206.41/53.74 (5) RelTRSRRRProof (EQUIVALENT) 206.41/53.74 We used the following monotonic ordering for rule removal: 206.41/53.74 Matrix interpretation [MATRO] to (N^3, +, *, >=, >) : 206.41/53.74 206.41/53.74 <<< 206.41/53.74 POL(a_{a_1}(x_1)) = [[0], [1], [1]] + [[1, 0, 0], [0, 0, 0], [0, 0, 0]] * x_1 206.41/53.74 >>> 206.41/53.74 206.41/53.74 <<< 206.41/53.74 POL(a_{b_1}(x_1)) = [[0], [0], [0]] + [[1, 0, 1], [0, 0, 0], [0, 0, 0]] * x_1 206.41/53.74 >>> 206.41/53.74 206.41/53.74 <<< 206.41/53.74 POL(b_{b_1}(x_1)) = [[0], [0], [0]] + [[1, 0, 0], [0, 0, 0], [0, 1, 0]] * x_1 206.41/53.74 >>> 206.41/53.74 206.41/53.74 <<< 206.41/53.74 POL(b_{a_1}(x_1)) = [[0], [0], [0]] + [[1, 0, 0], [0, 1, 1], [0, 0, 0]] * x_1 206.41/53.74 >>> 206.41/53.74 206.41/53.74 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 206.41/53.74 Rules from R: 206.41/53.74 206.41/53.74 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))) 206.41/53.74 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))) 206.41/53.75 Rules from S: 206.41/53.75 none 206.41/53.75 206.41/53.75 206.41/53.75 206.41/53.75 206.41/53.75 ---------------------------------------- 206.41/53.75 206.41/53.75 (6) 206.41/53.75 Obligation: 206.41/53.75 Relative term rewrite system: 206.41/53.75 The relative TRS consists of the following R rules: 206.41/53.75 206.41/53.75 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 206.41/53.75 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 206.41/53.75 206.41/53.75 The relative TRS consists of the following S rules: 206.41/53.75 206.41/53.75 a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) 206.41/53.75 a_{a_1}(a_{b_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) 206.41/53.75 b_{b_1}(b_{a_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 206.41/53.75 b_{b_1}(b_{b_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 206.41/53.75 206.41/53.75 206.41/53.75 ---------------------------------------- 206.41/53.75 206.41/53.75 (7) RelTRSRRRProof (EQUIVALENT) 206.41/53.75 We used the following monotonic ordering for rule removal: 206.41/53.75 Matrix interpretation [MATRO] to (N^3, +, *, >=, >) : 206.41/53.75 206.41/53.75 <<< 206.41/53.75 POL(b_{b_1}(x_1)) = [[0], [0], [0]] + [[1, 0, 0], [0, 0, 1], [0, 0, 0]] * x_1 206.41/53.75 >>> 206.41/53.75 206.41/53.75 <<< 206.41/53.75 POL(b_{a_1}(x_1)) = [[0], [0], [1]] + [[1, 0, 1], [0, 0, 0], [0, 0, 1]] * x_1 206.41/53.75 >>> 206.41/53.75 206.41/53.75 <<< 206.41/53.75 POL(a_{a_1}(x_1)) = [[0], [0], [0]] + [[1, 0, 0], [0, 0, 0], [0, 1, 0]] * x_1 206.41/53.75 >>> 206.41/53.75 206.41/53.75 <<< 206.41/53.75 POL(a_{b_1}(x_1)) = [[0], [1], [0]] + [[1, 0, 0], [0, 1, 0], [0, 0, 0]] * x_1 206.41/53.75 >>> 206.41/53.75 206.41/53.75 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 206.41/53.75 Rules from R: 206.41/53.75 206.41/53.75 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 206.41/53.75 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 206.41/53.75 Rules from S: 206.41/53.75 none 206.41/53.75 206.41/53.75 206.41/53.75 206.41/53.75 206.41/53.75 ---------------------------------------- 206.41/53.75 206.41/53.75 (8) 206.41/53.75 Obligation: 206.41/53.75 Relative term rewrite system: 206.41/53.75 R is empty. 206.41/53.75 The relative TRS consists of the following S rules: 206.41/53.75 206.41/53.75 a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) 206.41/53.75 a_{a_1}(a_{b_1}(x1)) -> a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) 206.41/53.75 b_{b_1}(b_{a_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 206.41/53.75 b_{b_1}(b_{b_1}(x1)) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 206.41/53.75 206.41/53.75 206.41/53.75 ---------------------------------------- 206.41/53.75 206.41/53.75 (9) RIsEmptyProof (EQUIVALENT) 206.41/53.75 The TRS R is empty. Hence, termination is trivially proven. 206.41/53.75 ---------------------------------------- 206.41/53.75 206.41/53.75 (10) 206.41/53.75 YES 206.83/53.80 EOF