9.88/3.42 YES 9.88/3.43 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 9.88/3.43 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.88/3.43 9.88/3.43 9.88/3.43 Termination of the given RelTRS could be proven: 9.88/3.43 9.88/3.43 (0) RelTRS 9.88/3.43 (1) RelTRSRRRProof [EQUIVALENT, 62 ms] 9.88/3.43 (2) RelTRS 9.88/3.43 (3) RelTRSRRRProof [EQUIVALENT, 0 ms] 9.88/3.43 (4) RelTRS 9.88/3.43 (5) RelTRSRRRProof [EQUIVALENT, 6 ms] 9.88/3.43 (6) RelTRS 9.88/3.43 (7) RelTRSRRRProof [EQUIVALENT, 0 ms] 9.88/3.43 (8) RelTRS 9.88/3.43 (9) RelTRSRRRProof [EQUIVALENT, 43 ms] 9.88/3.43 (10) RelTRS 9.88/3.43 (11) RelTRSRRRProof [EQUIVALENT, 19 ms] 9.88/3.43 (12) RelTRS 9.88/3.43 (13) RelTRSRRRProof [EQUIVALENT, 15 ms] 9.88/3.43 (14) RelTRS 9.88/3.43 (15) RelTRSRRRProof [EQUIVALENT, 14 ms] 9.88/3.43 (16) RelTRS 9.88/3.43 (17) RIsEmptyProof [EQUIVALENT, 0 ms] 9.88/3.43 (18) YES 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (0) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(nil, k) -> k 9.88/3.43 app(l, nil) -> l 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 plus(0, y) -> y 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l)))) 9.88/3.43 pred(cons(s(x), nil)) -> cons(x, nil) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (1) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Polynomial interpretation [POLO]: 9.88/3.43 9.88/3.43 POL(0) = 1 9.88/3.43 POL(app(x_1, x_2)) = x_1 + x_2 9.88/3.43 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(nil) = 0 9.88/3.43 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(pred(x_1)) = 1 + x_1 9.88/3.43 POL(s(x_1)) = 1 + x_1 9.88/3.43 POL(sum(x_1)) = x_1 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 plus(0, y) -> y 9.88/3.43 pred(cons(s(x), nil)) -> cons(x, nil) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (2) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(nil, k) -> k 9.88/3.43 app(l, nil) -> l 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l)))) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (3) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Polynomial interpretation [POLO]: 9.88/3.43 9.88/3.43 POL(0) = 1 9.88/3.43 POL(app(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(nil) = 0 9.88/3.43 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(pred(x_1)) = 1 + x_1 9.88/3.43 POL(s(x_1)) = 1 + x_1 9.88/3.43 POL(sum(x_1)) = x_1 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 app(nil, k) -> k 9.88/3.43 app(l, nil) -> l 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (4) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l)))) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (5) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Polynomial interpretation [POLO]: 9.88/3.43 9.88/3.43 POL(0) = 1 9.88/3.43 POL(app(x_1, x_2)) = x_1 + x_2 9.88/3.43 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(nil) = 0 9.88/3.43 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(pred(x_1)) = x_1 9.88/3.43 POL(s(x_1)) = x_1 9.88/3.43 POL(sum(x_1)) = x_1 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l)))) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (6) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (7) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Polynomial interpretation [POLO]: 9.88/3.43 9.88/3.43 POL(app(x_1, x_2)) = x_1 + x_2 9.88/3.43 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 9.88/3.43 POL(nil) = 0 9.88/3.43 POL(plus(x_1, x_2)) = x_1 + x_2 9.88/3.43 POL(s(x_1)) = x_1 9.88/3.43 POL(sum(x_1)) = x_1 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (8) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (9) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(app(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(cons(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(sum(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(nil) = [[0], [0]] 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(plus(x_1, x_2)) = [[1], [1]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(s(x_1)) = [[1], [1]] + [[1, 0], [0, 1]] * x_1 9.88/3.43 >>> 9.88/3.43 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 plus(s(x), y) -> s(plus(x, y)) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (10) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (11) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(app(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(cons(x_1, x_2)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(sum(x_1)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(nil) = [[0], [0]] 9.88/3.43 >>> 9.88/3.43 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 app(cons(x, l), k) -> cons(x, app(l, k)) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (12) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (13) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(sum(x_1)) = [[1], [1]] + [[1, 0], [0, 0]] * x_1 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(cons(x_1, x_2)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(nil) = [[0], [0]] 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(app(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 sum(cons(x, nil)) -> cons(x, nil) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (14) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 The relative TRS consists of the following R rules: 9.88/3.43 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (15) RelTRSRRRProof (EQUIVALENT) 9.88/3.43 We used the following monotonic ordering for rule removal: 9.88/3.43 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(sum(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(app(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 <<< 9.88/3.43 POL(cons(x_1, x_2)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 9.88/3.43 >>> 9.88/3.43 9.88/3.43 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 9.88/3.43 Rules from R: 9.88/3.43 9.88/3.43 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 9.88/3.43 Rules from S: 9.88/3.43 none 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (16) 9.88/3.43 Obligation: 9.88/3.43 Relative term rewrite system: 9.88/3.43 R is empty. 9.88/3.43 The relative TRS consists of the following S rules: 9.88/3.43 9.88/3.43 cons(x, cons(y, l)) -> cons(y, cons(x, l)) 9.88/3.43 9.88/3.43 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (17) RIsEmptyProof (EQUIVALENT) 9.88/3.43 The TRS R is empty. Hence, termination is trivially proven. 9.88/3.43 ---------------------------------------- 9.88/3.43 9.88/3.43 (18) 9.88/3.43 YES 9.94/3.51 EOF