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