5.59/2.19 YES 5.59/2.20 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.59/2.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.59/2.20 5.59/2.20 5.59/2.20 Termination of the given CSR could be proven: 5.59/2.20 5.59/2.20 (0) CSR 5.59/2.20 (1) CSDependencyPairsProof [EQUIVALENT, 0 ms] 5.59/2.20 (2) QCSDP 5.59/2.20 (3) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.59/2.20 (4) AND 5.59/2.20 (5) QCSDP 5.59/2.20 (6) QCSDPReductionPairProof [EQUIVALENT, 173 ms] 5.59/2.20 (7) QCSDP 5.59/2.20 (8) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.59/2.20 (9) TRUE 5.59/2.20 (10) QCSDP 5.59/2.20 (11) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.59/2.20 (12) QCSDP 5.59/2.20 (13) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.59/2.20 (14) TRUE 5.59/2.20 (15) QCSDP 5.59/2.20 (16) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.59/2.20 (17) QCSDP 5.59/2.20 (18) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.59/2.20 (19) TRUE 5.59/2.20 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (0) 5.59/2.20 Obligation: 5.59/2.20 Context-sensitive rewrite system: 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 The replacement map contains the following entries: 5.59/2.20 5.59/2.20 U11: {1} 5.59/2.20 tt: empty set 5.59/2.20 U21: {1} 5.59/2.20 s: {1} 5.59/2.20 plus: {1, 2} 5.59/2.20 U31: {1} 5.59/2.20 0: empty set 5.59/2.20 U41: {1} 5.59/2.20 x: {1, 2} 5.59/2.20 and: {1} 5.59/2.20 isNat: empty set 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (1) CSDependencyPairsProof (EQUIVALENT) 5.59/2.20 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (2) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2, X_2, U31'_1} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3, U41'_3, AND_2, U11'_2} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1, ISNAT_1, U_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The ordinary context-sensitive dependency pairs DP_o are: 5.59/2.20 U21'(tt, M, N) -> PLUS(N, M) 5.59/2.20 U41'(tt, M, N) -> PLUS(x(N, M), N) 5.59/2.20 U41'(tt, M, N) -> X(N, M) 5.59/2.20 ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(plus(V1, V2)) -> ISNAT(V1) 5.59/2.20 ISNAT(s(V1)) -> ISNAT(V1) 5.59/2.20 ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(x(V1, V2)) -> ISNAT(V1) 5.59/2.20 PLUS(N, 0) -> U11'(isNat(N), N) 5.59/2.20 PLUS(N, 0) -> ISNAT(N) 5.59/2.20 PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 PLUS(N, s(M)) -> AND(isNat(M), isNat(N)) 5.59/2.20 PLUS(N, s(M)) -> ISNAT(M) 5.59/2.20 X(N, 0) -> U31'(isNat(N)) 5.59/2.20 X(N, 0) -> ISNAT(N) 5.59/2.20 X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 X(N, s(M)) -> AND(isNat(M), isNat(N)) 5.59/2.20 X(N, s(M)) -> ISNAT(M) 5.59/2.20 5.59/2.20 The collapsing dependency pairs are DP_c: 5.59/2.20 U11'(tt, N) -> N 5.59/2.20 U21'(tt, M, N) -> N 5.59/2.20 U21'(tt, M, N) -> M 5.59/2.20 U41'(tt, M, N) -> N 5.59/2.20 U41'(tt, M, N) -> M 5.59/2.20 AND(tt, X) -> X 5.59/2.20 5.59/2.20 5.59/2.20 The hidden terms of R are: 5.59/2.20 5.59/2.20 isNat(x0) 5.59/2.20 5.59/2.20 Every hiding context is built from:none 5.59/2.20 5.59/2.20 Hence, the new unhiding pairs DP_u are : 5.59/2.20 U11'(tt, N) -> U(N) 5.59/2.20 U21'(tt, M, N) -> U(N) 5.59/2.20 U21'(tt, M, N) -> U(M) 5.59/2.20 U41'(tt, M, N) -> U(N) 5.59/2.20 U41'(tt, M, N) -> U(M) 5.59/2.20 AND(tt, X) -> U(X) 5.59/2.20 U(isNat(x0)) -> ISNAT(x0) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (3) QCSDependencyGraphProof (EQUIVALENT) 5.59/2.20 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 14 less nodes. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (4) 5.59/2.20 Complex Obligation (AND) 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (5) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, AND_2} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1, U_1, ISNAT_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 AND(tt, X) -> U(X) 5.59/2.20 U(isNat(x0)) -> ISNAT(x0) 5.59/2.20 ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(plus(V1, V2)) -> ISNAT(V1) 5.59/2.20 ISNAT(s(V1)) -> ISNAT(V1) 5.59/2.20 ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(x(V1, V2)) -> ISNAT(V1) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (6) QCSDPReductionPairProof (EQUIVALENT) 5.59/2.20 Using the order 5.59/2.20 5.59/2.20 AND/2)NO,YES( 5.59/2.20 tt/0) 5.59/2.20 U/1)YES( 5.59/2.20 isNat/1(YES) 5.59/2.20 ISNAT/1(YES) 5.59/2.20 plus/2(YES,YES) 5.59/2.20 s/1(YES) 5.59/2.20 x/2(YES,YES) 5.59/2.20 0/0) 5.59/2.20 and/2)NO,YES( 5.59/2.20 U11/2(YES,YES) 5.59/2.20 U21/3(YES,YES,YES) 5.59/2.20 U31/1(NO) 5.59/2.20 U41/3(YES,YES,YES) 5.59/2.20 5.59/2.20 Quasi precedence: 5.59/2.20 [x_2, 0, U31, U41_3] > tt > [plus_2, U21_3] > s_1 > [isNat_1, ISNAT_1] > U11_2 5.59/2.20 5.59/2.20 5.59/2.20 Status: 5.59/2.20 tt: multiset status 5.59/2.20 isNat_1: multiset status 5.59/2.20 ISNAT_1: multiset status 5.59/2.20 plus_2: [1,2] 5.59/2.20 s_1: [1] 5.59/2.20 x_2: [2,1] 5.59/2.20 0: multiset status 5.59/2.20 U11_2: [1,2] 5.59/2.20 U21_3: [3,2,1] 5.59/2.20 U31: [] 5.59/2.20 U41_3: [2,3,1] 5.59/2.20 5.59/2.20 5.59/2.20 5.59/2.20 the following usable rules 5.59/2.20 5.59/2.20 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 and(tt, X) -> X 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 5.59/2.20 5.59/2.20 could all be oriented weakly. 5.59/2.20 5.59/2.20 Furthermore, the pairs 5.59/2.20 5.59/2.20 5.59/2.20 ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(plus(V1, V2)) -> ISNAT(V1) 5.59/2.20 ISNAT(s(V1)) -> ISNAT(V1) 5.59/2.20 ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2)) 5.59/2.20 ISNAT(x(V1, V2)) -> ISNAT(V1) 5.59/2.20 5.59/2.20 5.59/2.20 could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES]. 5.59/2.20 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (7) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, AND_2} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1, U_1, ISNAT_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 AND(tt, X) -> U(X) 5.59/2.20 U(isNat(x0)) -> ISNAT(x0) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (8) QCSDependencyGraphProof (EQUIVALENT) 5.59/2.20 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (9) 5.59/2.20 TRUE 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (10) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 U21'(tt, M, N) -> PLUS(N, M) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (11) QCSDPSubtermProof (EQUIVALENT) 5.59/2.20 We use the subterm processor [DA_EMMES]. 5.59/2.20 5.59/2.20 5.59/2.20 The following pairs can be oriented strictly and are deleted. 5.59/2.20 5.59/2.20 PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 The remaining pairs can at least be oriented weakly. 5.59/2.20 5.59/2.20 U21'(tt, M, N) -> PLUS(N, M) 5.59/2.20 Used ordering: Combined order from the following AFS and order. 5.59/2.20 U21'(x1, x2, x3) = x2 5.59/2.20 5.59/2.20 PLUS(x1, x2) = x2 5.59/2.20 5.59/2.20 5.59/2.20 Subterm Order 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (12) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 U21'(tt, M, N) -> PLUS(N, M) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (13) QCSDependencyGraphProof (EQUIVALENT) 5.59/2.20 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 1 less node. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (14) 5.59/2.20 TRUE 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (15) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2, X_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, U41'_3} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 U41'(tt, M, N) -> X(N, M) 5.59/2.20 X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (16) QCSDPSubtermProof (EQUIVALENT) 5.59/2.20 We use the subterm processor [DA_EMMES]. 5.59/2.20 5.59/2.20 5.59/2.20 The following pairs can be oriented strictly and are deleted. 5.59/2.20 5.59/2.20 X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N) 5.59/2.20 The remaining pairs can at least be oriented weakly. 5.59/2.20 5.59/2.20 U41'(tt, M, N) -> X(N, M) 5.59/2.20 Used ordering: Combined order from the following AFS and order. 5.59/2.20 X(x1, x2) = x2 5.59/2.20 5.59/2.20 U41'(x1, x2, x3) = x2 5.59/2.20 5.59/2.20 5.59/2.20 Subterm Order 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (17) 5.59/2.20 Obligation: 5.59/2.20 Q-restricted context-sensitive dependency pair problem: 5.59/2.20 The symbols in {s_1, plus_2, U31_1, x_2, X_2} are replacing on all positions. 5.59/2.20 For all symbols f in {U11_2, U21_3, U41_3, and_2, U41'_3} we have mu(f) = {1}. 5.59/2.20 The symbols in {isNat_1} are not replacing on any position. 5.59/2.20 5.59/2.20 The TRS P consists of the following rules: 5.59/2.20 5.59/2.20 U41'(tt, M, N) -> X(N, M) 5.59/2.20 5.59/2.20 The TRS R consists of the following rules: 5.59/2.20 5.59/2.20 U11(tt, N) -> N 5.59/2.20 U21(tt, M, N) -> s(plus(N, M)) 5.59/2.20 U31(tt) -> 0 5.59/2.20 U41(tt, M, N) -> plus(x(N, M), N) 5.59/2.20 and(tt, X) -> X 5.59/2.20 isNat(0) -> tt 5.59/2.20 isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 isNat(s(V1)) -> isNat(V1) 5.59/2.20 isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2)) 5.59/2.20 plus(N, 0) -> U11(isNat(N), N) 5.59/2.20 plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N) 5.59/2.20 x(N, 0) -> U31(isNat(N)) 5.59/2.20 x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N) 5.59/2.20 5.59/2.20 Q is empty. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (18) QCSDependencyGraphProof (EQUIVALENT) 5.59/2.20 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 1 less node. 5.59/2.20 5.59/2.20 ---------------------------------------- 5.59/2.20 5.59/2.20 (19) 5.59/2.20 TRUE 5.80/2.27 EOF