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