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