3.02/1.35 YES 3.02/1.36 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.02/1.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.02/1.36 3.02/1.36 3.02/1.36 Termination of the given CSR could be proven: 3.02/1.36 3.02/1.36 (0) CSR 3.02/1.36 (1) CSRRRRProof [EQUIVALENT, 71 ms] 3.02/1.36 (2) CSR 3.02/1.36 (3) CSDependencyPairsProof [EQUIVALENT, 0 ms] 3.02/1.36 (4) QCSDP 3.02/1.36 (5) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 3.02/1.36 (6) TRUE 3.02/1.36 3.02/1.36 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (0) 3.02/1.36 Obligation: 3.02/1.36 Context-sensitive rewrite system: 3.02/1.36 The TRS R consists of the following rules: 3.02/1.36 3.02/1.36 f(X, X) -> f(a, b) 3.02/1.36 b -> a 3.02/1.36 3.02/1.36 The replacement map contains the following entries: 3.02/1.36 3.02/1.36 f: {1} 3.02/1.36 a: empty set 3.02/1.36 b: empty set 3.02/1.36 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (1) CSRRRRProof (EQUIVALENT) 3.02/1.36 The following CSR is given: Context-sensitive rewrite system: 3.02/1.36 The TRS R consists of the following rules: 3.02/1.36 3.02/1.36 f(X, X) -> f(a, b) 3.02/1.36 b -> a 3.02/1.36 3.02/1.36 The replacement map contains the following entries: 3.02/1.36 3.02/1.36 f: {1} 3.02/1.36 a: empty set 3.02/1.36 b: empty set 3.02/1.36 Used ordering: 3.02/1.36 Polynomial interpretation [POLO]: 3.02/1.36 3.02/1.36 POL(a) = 0 3.02/1.36 POL(b) = 2 3.02/1.36 POL(f(x_1, x_2)) = x_1 3.02/1.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.02/1.36 3.02/1.36 b -> a 3.02/1.36 3.02/1.36 3.02/1.36 3.02/1.36 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (2) 3.02/1.36 Obligation: 3.02/1.36 Context-sensitive rewrite system: 3.02/1.36 The TRS R consists of the following rules: 3.02/1.36 3.02/1.36 f(X, X) -> f(a, b) 3.02/1.36 3.02/1.36 The replacement map contains the following entries: 3.02/1.36 3.02/1.36 f: {1} 3.02/1.36 a: empty set 3.02/1.36 b: empty set 3.02/1.36 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (3) CSDependencyPairsProof (EQUIVALENT) 3.02/1.36 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (4) 3.02/1.36 Obligation: 3.02/1.36 Q-restricted context-sensitive dependency pair problem: 3.02/1.36 For all symbols f in {f_2, F_2} we have mu(f) = {1}. 3.02/1.36 3.02/1.36 The ordinary context-sensitive dependency pairs DP_o are: 3.02/1.36 F(X, X) -> F(a, b) 3.02/1.36 3.02/1.36 The TRS R consists of the following rules: 3.02/1.36 3.02/1.36 f(X, X) -> f(a, b) 3.02/1.36 3.02/1.36 Q is empty. 3.02/1.36 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (5) QCSDependencyGraphProof (EQUIVALENT) 3.02/1.36 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs. 3.02/1.36 The rules F(z0, z0) -> F(a, b) and F(x0, x0) -> F(a, b) form no chain, because ECap^mu(F(a, b)) = F(a, b) does not unify with F(x0, x0). 3.02/1.36 ---------------------------------------- 3.02/1.36 3.02/1.36 (6) 3.02/1.36 TRUE 3.13/1.39 EOF