3.12/1.46 YES 3.12/1.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 3.12/1.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.12/1.47 3.12/1.47 3.12/1.47 Termination of the given CSR could be proven: 3.12/1.47 3.12/1.47 (0) CSR 3.12/1.47 (1) CSRInnermostProof [EQUIVALENT, 0 ms] 3.12/1.47 (2) CSR 3.12/1.47 (3) CSDependencyPairsProof [EQUIVALENT, 0 ms] 3.12/1.47 (4) QCSDP 3.12/1.47 (5) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 3.12/1.47 (6) AND 3.12/1.47 (7) QCSDP 3.12/1.47 (8) QCSDPSubtermProof [EQUIVALENT, 0 ms] 3.12/1.47 (9) QCSDP 3.12/1.47 (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 3.12/1.47 (11) TRUE 3.12/1.47 (12) QCSDP 3.12/1.47 (13) QCSDPSubtermProof [EQUIVALENT, 0 ms] 3.12/1.47 (14) QCSDP 3.12/1.47 (15) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 3.12/1.47 (16) TRUE 3.12/1.47 3.12/1.47 3.12/1.47 ---------------------------------------- 3.12/1.47 3.12/1.47 (0) 3.12/1.47 Obligation: 3.12/1.47 Context-sensitive rewrite system: 3.12/1.47 The TRS R consists of the following rules: 3.12/1.47 3.12/1.47 U11(tt, M, N) -> U12(tt, M, N) 3.12/1.47 U12(tt, M, N) -> s(plus(N, M)) 3.12/1.47 U21(tt, M, N) -> U22(tt, M, N) 3.12/1.47 U22(tt, M, N) -> plus(x(N, M), N) 3.12/1.47 plus(N, 0) -> N 3.12/1.47 plus(N, s(M)) -> U11(tt, M, N) 3.12/1.47 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The replacement map contains the following entries: 3.16/1.49 3.16/1.49 U11: {1} 3.16/1.49 tt: empty set 3.16/1.49 U12: {1} 3.16/1.49 s: {1} 3.16/1.49 plus: {1, 2} 3.16/1.49 U21: {1} 3.16/1.49 U22: {1} 3.16/1.49 x: {1, 2} 3.16/1.49 0: empty set 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (1) CSRInnermostProof (EQUIVALENT) 3.16/1.49 The CSR is orthogonal. By [CS_Inn] we can switch to innermost. 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (2) 3.16/1.49 Obligation: 3.16/1.49 Context-sensitive rewrite system: 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The replacement map contains the following entries: 3.16/1.49 3.16/1.49 U11: {1} 3.16/1.49 tt: empty set 3.16/1.49 U12: {1} 3.16/1.49 s: {1} 3.16/1.49 plus: {1, 2} 3.16/1.49 U21: {1} 3.16/1.49 U22: {1} 3.16/1.49 x: {1, 2} 3.16/1.49 0: empty set 3.16/1.49 3.16/1.49 3.16/1.49 Innermost Strategy. 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (3) CSDependencyPairsProof (EQUIVALENT) 3.16/1.49 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (4) 3.16/1.49 Obligation: 3.16/1.49 Q-restricted context-sensitive dependency pair problem: 3.16/1.49 The symbols in {s_1, plus_2, x_2, PLUS_2, X_2} are replacing on all positions. 3.16/1.49 For all symbols f in {U11_3, U12_3, U21_3, U22_3, U12'_3, U11'_3, U22'_3, U21'_3} we have mu(f) = {1}. 3.16/1.49 The symbols in {U_1} are not replacing on any position. 3.16/1.49 3.16/1.49 The ordinary context-sensitive dependency pairs DP_o are: 3.16/1.49 U11'(tt, M, N) -> U12'(tt, M, N) 3.16/1.49 U12'(tt, M, N) -> PLUS(N, M) 3.16/1.49 U21'(tt, M, N) -> U22'(tt, M, N) 3.16/1.49 U22'(tt, M, N) -> PLUS(x(N, M), N) 3.16/1.49 U22'(tt, M, N) -> X(N, M) 3.16/1.49 PLUS(N, s(M)) -> U11'(tt, M, N) 3.16/1.49 X(N, s(M)) -> U21'(tt, M, N) 3.16/1.49 3.16/1.49 The collapsing dependency pairs are DP_c: 3.16/1.49 U12'(tt, M, N) -> N 3.16/1.49 U12'(tt, M, N) -> M 3.16/1.49 U22'(tt, M, N) -> N 3.16/1.49 U22'(tt, M, N) -> M 3.16/1.49 3.16/1.49 3.16/1.49 The hidden terms of R are: 3.16/1.49 none 3.16/1.49 3.16/1.49 Every hiding context is built from:none 3.16/1.49 3.16/1.49 Hence, the new unhiding pairs DP_u are : 3.16/1.49 U12'(tt, M, N) -> U(N) 3.16/1.49 U12'(tt, M, N) -> U(M) 3.16/1.49 U22'(tt, M, N) -> U(N) 3.16/1.49 U22'(tt, M, N) -> U(M) 3.16/1.49 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The set Q consists of the following terms: 3.16/1.49 3.16/1.49 U11(tt, x0, x1) 3.16/1.49 U12(tt, x0, x1) 3.16/1.49 U21(tt, x0, x1) 3.16/1.49 U22(tt, x0, x1) 3.16/1.49 plus(x0, 0) 3.16/1.49 plus(x0, s(x1)) 3.16/1.49 x(x0, 0) 3.16/1.49 x(x0, s(x1)) 3.16/1.49 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (5) QCSDependencyGraphProof (EQUIVALENT) 3.16/1.49 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs with 5 less nodes. 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (6) 3.16/1.49 Complex Obligation (AND) 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (7) 3.16/1.49 Obligation: 3.16/1.49 Q-restricted context-sensitive dependency pair problem: 3.16/1.49 The symbols in {s_1, plus_2, x_2, PLUS_2} are replacing on all positions. 3.16/1.49 For all symbols f in {U11_3, U12_3, U21_3, U22_3, U12'_3, U11'_3} we have mu(f) = {1}. 3.16/1.49 3.16/1.49 The TRS P consists of the following rules: 3.16/1.49 3.16/1.49 U12'(tt, M, N) -> PLUS(N, M) 3.16/1.49 PLUS(N, s(M)) -> U11'(tt, M, N) 3.16/1.49 U11'(tt, M, N) -> U12'(tt, M, N) 3.16/1.49 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The set Q consists of the following terms: 3.16/1.49 3.16/1.49 U11(tt, x0, x1) 3.16/1.49 U12(tt, x0, x1) 3.16/1.49 U21(tt, x0, x1) 3.16/1.49 U22(tt, x0, x1) 3.16/1.49 plus(x0, 0) 3.16/1.49 plus(x0, s(x1)) 3.16/1.49 x(x0, 0) 3.16/1.49 x(x0, s(x1)) 3.16/1.49 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (8) QCSDPSubtermProof (EQUIVALENT) 3.16/1.49 We use the subterm processor [DA_EMMES]. 3.16/1.49 3.16/1.49 3.16/1.49 The following pairs can be oriented strictly and are deleted. 3.16/1.49 3.16/1.49 PLUS(N, s(M)) -> U11'(tt, M, N) 3.16/1.49 The remaining pairs can at least be oriented weakly. 3.16/1.49 3.16/1.49 U12'(tt, M, N) -> PLUS(N, M) 3.16/1.49 U11'(tt, M, N) -> U12'(tt, M, N) 3.16/1.49 Used ordering: Combined order from the following AFS and order. 3.16/1.49 PLUS(x1, x2) = x2 3.16/1.49 3.16/1.49 U12'(x1, x2, x3) = x2 3.16/1.49 3.16/1.49 U11'(x1, x2, x3) = x2 3.16/1.49 3.16/1.49 3.16/1.49 Subterm Order 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (9) 3.16/1.49 Obligation: 3.16/1.49 Q-restricted context-sensitive dependency pair problem: 3.16/1.49 The symbols in {s_1, plus_2, x_2, PLUS_2} are replacing on all positions. 3.16/1.49 For all symbols f in {U11_3, U12_3, U21_3, U22_3, U12'_3, U11'_3} we have mu(f) = {1}. 3.16/1.49 3.16/1.49 The TRS P consists of the following rules: 3.16/1.49 3.16/1.49 U12'(tt, M, N) -> PLUS(N, M) 3.16/1.49 U11'(tt, M, N) -> U12'(tt, M, N) 3.16/1.49 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The set Q consists of the following terms: 3.16/1.49 3.16/1.49 U11(tt, x0, x1) 3.16/1.49 U12(tt, x0, x1) 3.16/1.49 U21(tt, x0, x1) 3.16/1.49 U22(tt, x0, x1) 3.16/1.49 plus(x0, 0) 3.16/1.49 plus(x0, s(x1)) 3.16/1.49 x(x0, 0) 3.16/1.49 x(x0, s(x1)) 3.16/1.49 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (10) QCSDependencyGraphProof (EQUIVALENT) 3.16/1.49 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (11) 3.16/1.49 TRUE 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (12) 3.16/1.49 Obligation: 3.16/1.49 Q-restricted context-sensitive dependency pair problem: 3.16/1.49 The symbols in {s_1, plus_2, x_2, X_2} are replacing on all positions. 3.16/1.49 For all symbols f in {U11_3, U12_3, U21_3, U22_3, U22'_3, U21'_3} we have mu(f) = {1}. 3.16/1.49 3.16/1.49 The TRS P consists of the following rules: 3.16/1.49 3.16/1.49 U22'(tt, M, N) -> X(N, M) 3.16/1.49 X(N, s(M)) -> U21'(tt, M, N) 3.16/1.49 U21'(tt, M, N) -> U22'(tt, M, N) 3.16/1.49 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The set Q consists of the following terms: 3.16/1.49 3.16/1.49 U11(tt, x0, x1) 3.16/1.49 U12(tt, x0, x1) 3.16/1.49 U21(tt, x0, x1) 3.16/1.49 U22(tt, x0, x1) 3.16/1.49 plus(x0, 0) 3.16/1.49 plus(x0, s(x1)) 3.16/1.49 x(x0, 0) 3.16/1.49 x(x0, s(x1)) 3.16/1.49 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (13) QCSDPSubtermProof (EQUIVALENT) 3.16/1.49 We use the subterm processor [DA_EMMES]. 3.16/1.49 3.16/1.49 3.16/1.49 The following pairs can be oriented strictly and are deleted. 3.16/1.49 3.16/1.49 X(N, s(M)) -> U21'(tt, M, N) 3.16/1.49 The remaining pairs can at least be oriented weakly. 3.16/1.49 3.16/1.49 U22'(tt, M, N) -> X(N, M) 3.16/1.49 U21'(tt, M, N) -> U22'(tt, M, N) 3.16/1.49 Used ordering: Combined order from the following AFS and order. 3.16/1.49 X(x1, x2) = x2 3.16/1.49 3.16/1.49 U22'(x1, x2, x3) = x2 3.16/1.49 3.16/1.49 U21'(x1, x2, x3) = x2 3.16/1.49 3.16/1.49 3.16/1.49 Subterm Order 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (14) 3.16/1.49 Obligation: 3.16/1.49 Q-restricted context-sensitive dependency pair problem: 3.16/1.49 The symbols in {s_1, plus_2, x_2, X_2} are replacing on all positions. 3.16/1.49 For all symbols f in {U11_3, U12_3, U21_3, U22_3, U22'_3, U21'_3} we have mu(f) = {1}. 3.16/1.49 3.16/1.49 The TRS P consists of the following rules: 3.16/1.49 3.16/1.49 U22'(tt, M, N) -> X(N, M) 3.16/1.49 U21'(tt, M, N) -> U22'(tt, M, N) 3.16/1.49 3.16/1.49 The TRS R consists of the following rules: 3.16/1.49 3.16/1.49 U11(tt, M, N) -> U12(tt, M, N) 3.16/1.49 U12(tt, M, N) -> s(plus(N, M)) 3.16/1.49 U21(tt, M, N) -> U22(tt, M, N) 3.16/1.49 U22(tt, M, N) -> plus(x(N, M), N) 3.16/1.49 plus(N, 0) -> N 3.16/1.49 plus(N, s(M)) -> U11(tt, M, N) 3.16/1.49 x(N, 0) -> 0 3.16/1.49 x(N, s(M)) -> U21(tt, M, N) 3.16/1.49 3.16/1.49 The set Q consists of the following terms: 3.16/1.49 3.16/1.49 U11(tt, x0, x1) 3.16/1.49 U12(tt, x0, x1) 3.16/1.49 U21(tt, x0, x1) 3.16/1.49 U22(tt, x0, x1) 3.16/1.49 plus(x0, 0) 3.16/1.49 plus(x0, s(x1)) 3.16/1.49 x(x0, 0) 3.16/1.49 x(x0, s(x1)) 3.16/1.49 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (15) QCSDependencyGraphProof (EQUIVALENT) 3.16/1.49 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 3.16/1.49 3.16/1.49 ---------------------------------------- 3.16/1.49 3.16/1.49 (16) 3.16/1.49 TRUE 3.16/1.50 EOF