2.79/1.47 YES 2.92/1.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 2.92/1.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 2.92/1.48 2.92/1.48 2.92/1.48 Termination of the given CSR could be proven: 2.92/1.48 2.92/1.48 (0) CSR 2.92/1.48 (1) CSRInnermostProof [EQUIVALENT, 0 ms] 2.92/1.48 (2) CSR 2.92/1.48 (3) CSDependencyPairsProof [EQUIVALENT, 0 ms] 2.92/1.48 (4) QCSDP 2.92/1.48 (5) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 2.92/1.48 (6) AND 2.92/1.48 (7) QCSDP 2.92/1.48 (8) QCSDPSubtermProof [EQUIVALENT, 14 ms] 2.92/1.48 (9) QCSDP 2.92/1.48 (10) PIsEmptyProof [EQUIVALENT, 0 ms] 2.92/1.48 (11) YES 2.92/1.48 (12) QCSDP 2.92/1.48 (13) QCSDPSubtermProof [EQUIVALENT, 0 ms] 2.92/1.48 (14) QCSDP 2.92/1.48 (15) PIsEmptyProof [EQUIVALENT, 0 ms] 2.92/1.48 (16) YES 2.92/1.48 (17) QCSDP 2.92/1.48 (18) QCSDPSubtermProof [EQUIVALENT, 0 ms] 2.92/1.48 (19) QCSDP 2.92/1.48 (20) PIsEmptyProof [EQUIVALENT, 0 ms] 2.92/1.48 (21) YES 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (0) 2.92/1.48 Obligation: 2.92/1.48 Context-sensitive rewrite system: 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The replacement map contains the following entries: 2.92/1.48 2.92/1.48 f: {1} 2.92/1.48 cons: {1} 2.92/1.48 g: {1} 2.92/1.48 0: empty set 2.92/1.48 s: {1} 2.92/1.48 sel: {1, 2} 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (1) CSRInnermostProof (EQUIVALENT) 2.92/1.48 The CSR is orthogonal. By [CS_Inn] we can switch to innermost. 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (2) 2.92/1.48 Obligation: 2.92/1.48 Context-sensitive rewrite system: 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The replacement map contains the following entries: 2.92/1.48 2.92/1.48 f: {1} 2.92/1.48 cons: {1} 2.92/1.48 g: {1} 2.92/1.48 0: empty set 2.92/1.48 s: {1} 2.92/1.48 sel: {1, 2} 2.92/1.48 2.92/1.48 2.92/1.48 Innermost Strategy. 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (3) CSDependencyPairsProof (EQUIVALENT) 2.92/1.48 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (4) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2, G_1, SEL_2, F_1} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 The symbols in {U_1} are not replacing on any position. 2.92/1.48 2.92/1.48 The ordinary context-sensitive dependency pairs DP_o are: 2.92/1.48 G(s(X)) -> G(X) 2.92/1.48 SEL(s(X), cons(Y, Z)) -> SEL(X, Z) 2.92/1.48 2.92/1.48 The collapsing dependency pairs are DP_c: 2.92/1.48 SEL(s(X), cons(Y, Z)) -> Z 2.92/1.48 2.92/1.48 2.92/1.48 The hidden terms of R are: 2.92/1.48 2.92/1.48 f(g(x0)) 2.92/1.48 g(x0) 2.92/1.48 2.92/1.48 Every hiding context is built from: 2.92/1.48 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@4582c1ae 2.92/1.48 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@77b370ce 2.92/1.48 2.92/1.48 Hence, the new unhiding pairs DP_u are : 2.92/1.48 SEL(s(X), cons(Y, Z)) -> U(Z) 2.92/1.48 U(g(x_0)) -> U(x_0) 2.92/1.48 U(f(x_0)) -> U(x_0) 2.92/1.48 U(f(g(x0))) -> F(g(x0)) 2.92/1.48 U(g(x0)) -> G(x0) 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (5) QCSDependencyGraphProof (EQUIVALENT) 2.92/1.48 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 3 less nodes. 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (6) 2.92/1.48 Complex Obligation (AND) 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (7) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2, G_1} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 2.92/1.48 G(s(X)) -> G(X) 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (8) QCSDPSubtermProof (EQUIVALENT) 2.92/1.48 We use the subterm processor [DA_EMMES]. 2.92/1.48 2.92/1.48 2.92/1.48 The following pairs can be oriented strictly and are deleted. 2.92/1.48 2.92/1.48 G(s(X)) -> G(X) 2.92/1.48 The remaining pairs can at least be oriented weakly. 2.92/1.48 none 2.92/1.48 Used ordering: Combined order from the following AFS and order. 2.92/1.48 G(x1) = x1 2.92/1.48 2.92/1.48 2.92/1.48 Subterm Order 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (9) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 none 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (10) PIsEmptyProof (EQUIVALENT) 2.92/1.48 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (11) 2.92/1.48 YES 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (12) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 The symbols in {U_1} are not replacing on any position. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 2.92/1.48 U(g(x_0)) -> U(x_0) 2.92/1.48 U(f(x_0)) -> U(x_0) 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (13) QCSDPSubtermProof (EQUIVALENT) 2.92/1.48 We use the subterm processor [DA_EMMES]. 2.92/1.48 2.92/1.48 2.92/1.48 The following pairs can be oriented strictly and are deleted. 2.92/1.48 2.92/1.48 U(g(x_0)) -> U(x_0) 2.92/1.48 U(f(x_0)) -> U(x_0) 2.92/1.48 The remaining pairs can at least be oriented weakly. 2.92/1.48 none 2.92/1.48 Used ordering: Combined order from the following AFS and order. 2.92/1.48 U(x1) = x1 2.92/1.48 2.92/1.48 2.92/1.48 Subterm Order 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (14) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 none 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (15) PIsEmptyProof (EQUIVALENT) 2.92/1.48 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (16) 2.92/1.48 YES 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (17) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2, SEL_2} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 2.92/1.48 SEL(s(X), cons(Y, Z)) -> SEL(X, Z) 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (18) QCSDPSubtermProof (EQUIVALENT) 2.92/1.48 We use the subterm processor [DA_EMMES]. 2.92/1.48 2.92/1.48 2.92/1.48 The following pairs can be oriented strictly and are deleted. 2.92/1.48 2.92/1.48 SEL(s(X), cons(Y, Z)) -> SEL(X, Z) 2.92/1.48 The remaining pairs can at least be oriented weakly. 2.92/1.48 none 2.92/1.48 Used ordering: Combined order from the following AFS and order. 2.92/1.48 SEL(x1, x2) = x1 2.92/1.48 2.92/1.48 2.92/1.48 Subterm Order 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (19) 2.92/1.48 Obligation: 2.92/1.48 Q-restricted context-sensitive dependency pair problem: 2.92/1.48 The symbols in {f_1, g_1, s_1, sel_2} are replacing on all positions. 2.92/1.48 For all symbols f in {cons_2} we have mu(f) = {1}. 2.92/1.48 2.92/1.48 The TRS P consists of the following rules: 2.92/1.48 none 2.92/1.48 2.92/1.48 The TRS R consists of the following rules: 2.92/1.48 2.92/1.48 f(X) -> cons(X, f(g(X))) 2.92/1.48 g(0) -> s(0) 2.92/1.48 g(s(X)) -> s(s(g(X))) 2.92/1.48 sel(0, cons(X, Y)) -> X 2.92/1.48 sel(s(X), cons(Y, Z)) -> sel(X, Z) 2.92/1.48 2.92/1.48 The set Q consists of the following terms: 2.92/1.48 2.92/1.48 f(x0) 2.92/1.48 g(0) 2.92/1.48 g(s(x0)) 2.92/1.48 sel(0, cons(x0, x1)) 2.92/1.48 sel(s(x0), cons(x1, x2)) 2.92/1.48 2.92/1.48 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (20) PIsEmptyProof (EQUIVALENT) 2.92/1.48 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 2.92/1.48 ---------------------------------------- 2.92/1.48 2.92/1.48 (21) 2.92/1.48 YES 2.92/1.51 EOF