89.97/23.85 YES 98.35/25.98 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 98.35/25.98 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 98.35/25.98 98.35/25.98 98.35/25.98 Termination of the given RelTRS could be proven: 98.35/25.98 98.35/25.98 (0) RelTRS 98.35/25.98 (1) RelTRS Reverse [EQUIVALENT, 0 ms] 98.35/25.98 (2) RelTRS 98.35/25.98 (3) RelTRSRRRProof [EQUIVALENT, 51 ms] 98.35/25.98 (4) RelTRS 98.35/25.98 (5) RelTRSRRRProof [EQUIVALENT, 2898 ms] 98.35/25.98 (6) RelTRS 98.35/25.98 (7) RelTRSRRRProof [EQUIVALENT, 5 ms] 98.35/25.98 (8) RelTRS 98.35/25.98 (9) RelTRSRRRProof [EQUIVALENT, 498 ms] 98.35/25.98 (10) RelTRS 98.35/25.98 (11) RelTRSRRRProof [EQUIVALENT, 279 ms] 98.35/25.98 (12) RelTRS 98.35/25.98 (13) RelTRSRRRProof [EQUIVALENT, 887 ms] 98.35/25.98 (14) RelTRS 98.35/25.98 (15) RIsEmptyProof [EQUIVALENT, 0 ms] 98.35/25.98 (16) YES 98.35/25.98 98.35/25.98 98.35/25.98 ---------------------------------------- 98.35/25.98 98.35/25.98 (0) 98.35/25.98 Obligation: 98.35/25.98 Relative term rewrite system: 98.35/25.98 The relative TRS consists of the following R rules: 98.35/25.98 98.35/25.98 d(d(n(n(x1)))) -> d(d(x1)) 98.35/25.98 d(d(o(o(x1)))) -> d(d(x1)) 98.35/25.98 o(o(u(u(x1)))) -> u(u(x1)) 98.35/25.98 98.35/25.98 The relative TRS consists of the following S rules: 98.35/25.98 98.35/25.98 t(t(u(u(x1)))) -> t(t(c(c(d(d(x1)))))) 98.35/25.98 d(d(f(f(x1)))) -> f(f(d(d(x1)))) 98.35/25.98 d(d(g(g(x1)))) -> u(u(g(g(x1)))) 98.35/26.00 f(f(u(u(x1)))) -> u(u(f(f(x1)))) 98.35/26.00 n(n(u(u(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> f(f(n(n(x1)))) 98.35/26.00 t(t(x1)) -> t(t(c(c(n(n(x1)))))) 98.35/26.00 c(c(n(n(x1)))) -> n(n(c(c(x1)))) 98.35/26.00 c(c(o(o(x1)))) -> o(o(c(c(x1)))) 98.35/26.00 c(c(o(o(x1)))) -> o(o(x1)) 98.35/26.00 c(c(f(f(x1)))) -> f(f(c(c(x1)))) 98.35/26.00 c(c(u(u(x1)))) -> u(u(c(c(x1)))) 98.35/26.00 c(c(d(d(x1)))) -> d(d(c(c(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (1) RelTRS Reverse (EQUIVALENT) 98.35/26.00 We have reversed the following relative TRS [REVERSE]: 98.35/26.00 The set of rules R is 98.35/26.00 d(d(n(n(x1)))) -> d(d(x1)) 98.35/26.00 d(d(o(o(x1)))) -> d(d(x1)) 98.35/26.00 o(o(u(u(x1)))) -> u(u(x1)) 98.35/26.00 98.35/26.00 The set of rules S is 98.35/26.00 t(t(u(u(x1)))) -> t(t(c(c(d(d(x1)))))) 98.35/26.00 d(d(f(f(x1)))) -> f(f(d(d(x1)))) 98.35/26.00 d(d(g(g(x1)))) -> u(u(g(g(x1)))) 98.35/26.00 f(f(u(u(x1)))) -> u(u(f(f(x1)))) 98.35/26.00 n(n(u(u(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> f(f(n(n(x1)))) 98.35/26.00 t(t(x1)) -> t(t(c(c(n(n(x1)))))) 98.35/26.00 c(c(n(n(x1)))) -> n(n(c(c(x1)))) 98.35/26.00 c(c(o(o(x1)))) -> o(o(c(c(x1)))) 98.35/26.00 c(c(o(o(x1)))) -> o(o(x1)) 98.35/26.00 c(c(f(f(x1)))) -> f(f(c(c(x1)))) 98.35/26.00 c(c(u(u(x1)))) -> u(u(c(c(x1)))) 98.35/26.00 c(c(d(d(x1)))) -> d(d(c(c(x1)))) 98.35/26.00 98.35/26.00 We have obtained the following relative TRS: 98.35/26.00 The set of rules R is 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 o(o(d(d(x1)))) -> d(d(x1)) 98.35/26.00 u(u(o(o(x1)))) -> u(u(x1)) 98.35/26.00 98.35/26.00 The set of rules S is 98.35/26.00 u(u(t(t(x1)))) -> d(d(c(c(t(t(x1)))))) 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 g(g(d(d(x1)))) -> g(g(u(u(x1)))) 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (2) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 o(o(d(d(x1)))) -> d(d(x1)) 98.35/26.00 u(u(o(o(x1)))) -> u(u(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 u(u(t(t(x1)))) -> d(d(c(c(t(t(x1)))))) 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 g(g(d(d(x1)))) -> g(g(u(u(x1)))) 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (3) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Polynomial interpretation [POLO]: 98.35/26.00 98.35/26.00 POL(c(x_1)) = x_1 98.35/26.00 POL(d(x_1)) = 1 + x_1 98.35/26.00 POL(f(x_1)) = x_1 98.35/26.00 POL(g(x_1)) = x_1 98.35/26.00 POL(n(x_1)) = x_1 98.35/26.00 POL(o(x_1)) = 1 + x_1 98.35/26.00 POL(t(x_1)) = x_1 98.35/26.00 POL(u(x_1)) = 1 + x_1 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 98.35/26.00 o(o(d(d(x1)))) -> d(d(x1)) 98.35/26.00 u(u(o(o(x1)))) -> u(u(x1)) 98.35/26.00 Rules from S: 98.35/26.00 none 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (4) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 u(u(t(t(x1)))) -> d(d(c(c(t(t(x1)))))) 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 g(g(d(d(x1)))) -> g(g(u(u(x1)))) 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (5) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(n(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(d(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(u(x_1)) = [[1], [0]] + [[1, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(t(x_1)) = [[0], [1]] + [[2, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(c(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(f(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(g(x_1)) = [[0], [0]] + [[2, 1], [0, 2]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(o(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 none 98.35/26.00 Rules from S: 98.35/26.00 98.35/26.00 u(u(t(t(x1)))) -> d(d(c(c(t(t(x1)))))) 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (6) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 g(g(d(d(x1)))) -> g(g(u(u(x1)))) 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (7) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Polynomial interpretation [POLO]: 98.35/26.00 98.35/26.00 POL(c(x_1)) = x_1 98.35/26.00 POL(d(x_1)) = 1 + x_1 98.35/26.00 POL(f(x_1)) = x_1 98.35/26.00 POL(g(x_1)) = x_1 98.35/26.00 POL(n(x_1)) = x_1 98.35/26.00 POL(o(x_1)) = x_1 98.35/26.00 POL(t(x_1)) = x_1 98.35/26.00 POL(u(x_1)) = x_1 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 none 98.35/26.00 Rules from S: 98.35/26.00 98.35/26.00 g(g(d(d(x1)))) -> g(g(u(u(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (8) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (9) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(n(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(d(x_1)) = [[2], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(f(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(u(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(t(x_1)) = [[0], [0]] + [[1, 0], [0, 2]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(c(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(o(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 none 98.35/26.00 Rules from S: 98.35/26.00 98.35/26.00 f(f(d(d(x1)))) -> d(d(f(f(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (10) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (11) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(n(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(d(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(u(x_1)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(f(x_1)) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(t(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(c(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(o(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 none 98.35/26.00 Rules from S: 98.35/26.00 98.35/26.00 u(u(f(f(x1)))) -> f(f(u(u(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (12) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 The relative TRS consists of the following R rules: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (13) RelTRSRRRProof (EQUIVALENT) 98.35/26.00 We used the following monotonic ordering for rule removal: 98.35/26.00 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(n(x_1)) = [[0], [0]] + [[1, 2], [0, 2]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(d(x_1)) = [[0], [1]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(u(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(f(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(t(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(c(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 <<< 98.35/26.00 POL(o(x_1)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 98.35/26.00 >>> 98.35/26.00 98.35/26.00 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 98.35/26.00 Rules from R: 98.35/26.00 98.35/26.00 n(n(d(d(x1)))) -> d(d(x1)) 98.35/26.00 Rules from S: 98.35/26.00 none 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (14) 98.35/26.00 Obligation: 98.35/26.00 Relative term rewrite system: 98.35/26.00 R is empty. 98.35/26.00 The relative TRS consists of the following S rules: 98.35/26.00 98.35/26.00 u(u(n(n(x1)))) -> u(u(x1)) 98.35/26.00 f(f(x1)) -> n(n(f(f(x1)))) 98.35/26.00 t(t(x1)) -> n(n(c(c(t(t(x1)))))) 98.35/26.00 n(n(c(c(x1)))) -> c(c(n(n(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> c(c(o(o(x1)))) 98.35/26.00 o(o(c(c(x1)))) -> o(o(x1)) 98.35/26.00 f(f(c(c(x1)))) -> c(c(f(f(x1)))) 98.35/26.00 u(u(c(c(x1)))) -> c(c(u(u(x1)))) 98.35/26.00 d(d(c(c(x1)))) -> c(c(d(d(x1)))) 98.35/26.00 98.35/26.00 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (15) RIsEmptyProof (EQUIVALENT) 98.35/26.00 The TRS R is empty. Hence, termination is trivially proven. 98.35/26.00 ---------------------------------------- 98.35/26.00 98.35/26.00 (16) 98.35/26.00 YES 98.61/26.08 EOF