3.27/1.36 YES 3.27/1.36 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.27/1.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.27/1.36 3.27/1.36 3.27/1.36 Termination of the given CSR could be proven: 3.27/1.36 3.27/1.36 (0) CSR 3.27/1.36 (1) CSRRRRProof [EQUIVALENT, 65 ms] 3.27/1.36 (2) CSR 3.27/1.36 (3) CSRRRRProof [EQUIVALENT, 0 ms] 3.27/1.36 (4) CSR 3.27/1.36 (5) CSRRRRProof [EQUIVALENT, 0 ms] 3.27/1.36 (6) CSR 3.27/1.36 (7) RisEmptyProof [EQUIVALENT, 0 ms] 3.27/1.36 (8) YES 3.27/1.36 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (0) 3.27/1.36 Obligation: 3.27/1.36 Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 c(X) -> d(X) 3.27/1.36 h(X) -> c(d(X)) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 d: empty set 3.27/1.36 h: {1} 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (1) CSRRRRProof (EQUIVALENT) 3.27/1.36 The following CSR is given: Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 c(X) -> d(X) 3.27/1.36 h(X) -> c(d(X)) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 d: empty set 3.27/1.36 h: {1} 3.27/1.36 Used ordering: 3.27/1.36 Polynomial interpretation [POLO]: 3.27/1.36 3.27/1.36 POL(c(x_1)) = x_1 3.27/1.36 POL(d(x_1)) = x_1 3.27/1.36 POL(f(x_1)) = 1 + x_1 3.27/1.36 POL(g(x_1)) = x_1 3.27/1.36 POL(h(x_1)) = 1 + x_1 3.27/1.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.27/1.36 3.27/1.36 h(X) -> c(d(X)) 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (2) 3.27/1.36 Obligation: 3.27/1.36 Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 c(X) -> d(X) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 d: empty set 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (3) CSRRRRProof (EQUIVALENT) 3.27/1.36 The following CSR is given: Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 c(X) -> d(X) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 d: empty set 3.27/1.36 Used ordering: 3.27/1.36 Polynomial interpretation [POLO]: 3.27/1.36 3.27/1.36 POL(c(x_1)) = 2 + 2*x_1 3.27/1.36 POL(d(x_1)) = 2*x_1 3.27/1.36 POL(f(x_1)) = 2 + 2*x_1 3.27/1.36 POL(g(x_1)) = 0 3.27/1.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.27/1.36 3.27/1.36 c(X) -> d(X) 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (4) 3.27/1.36 Obligation: 3.27/1.36 Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (5) CSRRRRProof (EQUIVALENT) 3.27/1.36 The following CSR is given: Context-sensitive rewrite system: 3.27/1.36 The TRS R consists of the following rules: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 3.27/1.36 The replacement map contains the following entries: 3.27/1.36 3.27/1.36 f: {1} 3.27/1.36 c: empty set 3.27/1.36 g: empty set 3.27/1.36 Used ordering: 3.27/1.36 Polynomial interpretation [POLO]: 3.27/1.36 3.27/1.36 POL(c(x_1)) = 0 3.27/1.36 POL(f(x_1)) = 1 + 2*x_1 3.27/1.36 POL(g(x_1)) = 0 3.27/1.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.27/1.36 3.27/1.36 f(f(X)) -> c(f(g(f(X)))) 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (6) 3.27/1.36 Obligation: 3.27/1.36 Context-sensitive rewrite system: 3.27/1.36 R is empty. 3.27/1.36 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (7) RisEmptyProof (EQUIVALENT) 3.27/1.36 The CSR R is empty. Hence, termination is trivially proven. 3.27/1.36 ---------------------------------------- 3.27/1.36 3.27/1.36 (8) 3.27/1.36 YES 3.27/1.38 EOF