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