/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 246 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) QDPOrderProof [EQUIVALENT, 227 ms] (11) QDP (12) DependencyGraphProof [EQUIVALENT, 0 ms] (13) TRUE (14) QDP (15) QDPOrderProof [EQUIVALENT, 63 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 92 ms] (18) QDP (19) QDPOrderProof [EQUIVALENT, 114 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 125 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) AND (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) QDPOrderProof [EQUIVALENT, 84 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 253 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 110 ms] (36) QDP (37) DependencyGraphProof [EQUIVALENT, 0 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 109 ms] (40) QDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] (46) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__TAKE(0, IL) -> A__UTAKE1(a__isNatIList(IL)) A__TAKE(0, IL) -> A__ISNATILIST(IL) A__TAKE(s(M), cons(N, IL)) -> A__UTAKE2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) A__UTAKE2(tt, M, N, IL) -> MARK(N) A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__LENGTH(cons(N, L)) -> A__ISNAT(N) A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) A__ULENGTH(tt, L) -> MARK(L) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(length(X)) -> A__LENGTH(mark(X)) MARK(length(X)) -> MARK(X) MARK(zeros) -> A__ZEROS MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) MARK(take(X1, X2)) -> MARK(X1) MARK(take(X1, X2)) -> MARK(X2) MARK(uTake1(X)) -> A__UTAKE1(mark(X)) MARK(uTake1(X)) -> MARK(X) MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) MARK(uLength(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(length(X)) -> A__LENGTH(mark(X)) A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__LENGTH(cons(N, L)) -> A__ISNAT(N) A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) A__ULENGTH(tt, L) -> MARK(L) MARK(length(X)) -> MARK(X) MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) A__TAKE(0, IL) -> A__ISNATILIST(IL) A__TAKE(s(M), cons(N, IL)) -> A__UTAKE2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) A__UTAKE2(tt, M, N, IL) -> MARK(N) MARK(take(X1, X2)) -> MARK(X1) MARK(take(X1, X2)) -> MARK(X2) MARK(uTake1(X)) -> MARK(X) MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) MARK(uLength(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__LENGTH(cons(N, L)) -> A__ISNAT(N) A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) A__ULENGTH(tt, L) -> MARK(L) MARK(length(X)) -> MARK(X) MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) A__TAKE(0, IL) -> A__ISNATILIST(IL) A__TAKE(s(M), cons(N, IL)) -> A__UTAKE2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) MARK(take(X1, X2)) -> MARK(X1) MARK(take(X1, X2)) -> MARK(X2) MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) MARK(uLength(X1, X2)) -> MARK(X1) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = 2x_2 POL( A__LENGTH_1(x_1) ) = x_1 + 2 POL( A__TAKE_2(x_1, x_2) ) = 2x_2 + 1 POL( A__ULENGTH_2(x_1, x_2) ) = x_2 + 2 POL( A__UTAKE2_4(x_1, ..., x_4) ) = x_3 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 0 POL( a__isNatIList_1(x_1) ) = 0 POL( a__isNatList_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = x_1 + x_2 POL( a__isNat_1(x_1) ) = 0 POL( take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( isNatList_1(x_1) ) = 0 POL( isNat_1(x_1) ) = 0 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = x_1 + 2 POL( a__length_1(x_1) ) = x_1 + 2 POL( zeros ) = 0 POL( a__zeros ) = 0 POL( a__take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( uTake1_1(x_1) ) = x_1 POL( a__uTake1_1(x_1) ) = x_1 POL( uTake2_4(x_1, ..., x_4) ) = x_1 + x_2 + x_3 + 2x_4 + 2 POL( a__uTake2_4(x_1, ..., x_4) ) = x_1 + x_2 + x_3 + 2x_4 + 2 POL( uLength_2(x_1, x_2) ) = x_1 + x_2 + 2 POL( a__uLength_2(x_1, x_2) ) = x_1 + x_2 + 2 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 POL( A__ISNATILIST_1(x_1) ) = 0 POL( A__ISNATLIST_1(x_1) ) = 0 POL( A__ISNAT_1(x_1) ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__and(X1, X2) -> and(X1, X2) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(length(X)) -> A__LENGTH(mark(X)) A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) A__UTAKE2(tt, M, N, IL) -> MARK(N) MARK(uTake1(X)) -> MARK(X) MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(A__ULENGTH(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(tt) = [[5A]] >>> <<< POL(A__LENGTH(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(mark(x_1)) = [[1A]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__and(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__isNat(x_1)) = [[0A]] + [[2A]] * x_1 >>> <<< POL(a__isNatList(x_1)) = [[4A]] + [[1A]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[5A]] + [[1A]] * x_1 >>> <<< POL(a__isNatIList(x_1)) = [[5A]] + [[1A]] * x_1 >>> <<< POL(take(x_1, x_2)) = [[4A]] + [[3A]] * x_1 + [[0A]] * x_2 >>> <<< POL(isNatList(x_1)) = [[4A]] + [[1A]] * x_1 >>> <<< POL(isNat(x_1)) = [[0A]] + [[2A]] * x_1 >>> <<< POL(s(x_1)) = [[2A]] + [[1A]] * x_1 >>> <<< POL(length(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(a__length(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(zeros) = [[0A]] >>> <<< POL(a__zeros) = [[1A]] >>> <<< POL(a__take(x_1, x_2)) = [[4A]] + [[3A]] * x_1 + [[0A]] * x_2 >>> <<< POL(uTake1(x_1)) = [[4A]] + [[-I]] * x_1 >>> <<< POL(a__uTake1(x_1)) = [[4A]] + [[-I]] * x_1 >>> <<< POL(uTake2(x_1, x_2, x_3, x_4)) = [[5A]] + [[-I]] * x_1 + [[4A]] * x_2 + [[-I]] * x_3 + [[1A]] * x_4 >>> <<< POL(a__uTake2(x_1, x_2, x_3, x_4)) = [[5A]] + [[-I]] * x_1 + [[4A]] * x_2 + [[-I]] * x_3 + [[1A]] * x_4 >>> <<< POL(uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(a__uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 >>> <<< POL(0) = [[3A]] >>> <<< POL(nil) = [[4A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__and(X1, X2) -> and(X1, X2) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (13) TRUE ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(uTake1(X)) -> MARK(X) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(cons(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = x_2 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 0 POL( a__isNatIList_1(x_1) ) = 0 POL( a__isNatList_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = 2x_1 + 2 POL( a__isNat_1(x_1) ) = 0 POL( take_2(x_1, x_2) ) = x_2 POL( isNatList_1(x_1) ) = 0 POL( isNat_1(x_1) ) = 0 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = 2 POL( a__length_1(x_1) ) = 2 POL( zeros ) = 2 POL( a__zeros ) = 2 POL( a__take_2(x_1, x_2) ) = x_2 POL( uTake1_1(x_1) ) = x_1 POL( a__uTake1_1(x_1) ) = x_1 POL( uTake2_4(x_1, ..., x_4) ) = 2x_3 + 2 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_3 + 2 POL( uLength_2(x_1, x_2) ) = 2 POL( a__uLength_2(x_1, x_2) ) = 2 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 POL( A__ISNATILIST_1(x_1) ) = 0 POL( A__ISNATLIST_1(x_1) ) = 0 POL( A__ISNAT_1(x_1) ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(uTake1(X)) -> MARK(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(uTake1(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = 2x_2 + 2 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 0 POL( a__isNatIList_1(x_1) ) = 0 POL( a__isNatList_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = max{0, -2} POL( a__isNat_1(x_1) ) = 0 POL( take_2(x_1, x_2) ) = 2 POL( isNatList_1(x_1) ) = 0 POL( isNat_1(x_1) ) = 0 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = 0 POL( a__length_1(x_1) ) = max{0, -2} POL( zeros ) = 0 POL( a__zeros ) = 0 POL( a__take_2(x_1, x_2) ) = 2 POL( uTake1_1(x_1) ) = 2x_1 + 1 POL( a__uTake1_1(x_1) ) = 2x_1 + 1 POL( uTake2_4(x_1, ..., x_4) ) = 0 POL( a__uTake2_4(x_1, ..., x_4) ) = 0 POL( uLength_2(x_1, x_2) ) = 0 POL( a__uLength_2(x_1, x_2) ) = max{0, -2} POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 + 2 POL( A__ISNATILIST_1(x_1) ) = 2 POL( A__ISNATLIST_1(x_1) ) = 2 POL( A__ISNAT_1(x_1) ) = 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = 2x_2 + 2 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = 2x_1 + x_2 POL( a__and_2(x_1, x_2) ) = 2x_1 + x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = x_1 POL( a__isNatIList_1(x_1) ) = x_1 POL( a__isNatList_1(x_1) ) = x_1 POL( cons_2(x_1, x_2) ) = 2x_1 + x_2 POL( a__isNat_1(x_1) ) = x_1 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 POL( isNatList_1(x_1) ) = x_1 POL( isNat_1(x_1) ) = x_1 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = 2x_1 POL( a__length_1(x_1) ) = 2x_1 POL( zeros ) = 0 POL( a__zeros ) = 0 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 POL( uTake1_1(x_1) ) = 0 POL( a__uTake1_1(x_1) ) = max{0, -2} POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 1 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 1 POL( uLength_2(x_1, x_2) ) = 2x_2 POL( a__uLength_2(x_1, x_2) ) = 2x_2 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = 2x_1 + 2 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 POL( A__ISNATLIST_1(x_1) ) = 2x_1 + 2 POL( A__ISNAT_1(x_1) ) = 2x_1 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNAT(length(L)) -> A__ISNATLIST(L) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__ISNAT(length(L)) -> A__ISNATLIST(L) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = x_2 + 2 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = x_1 + x_2 POL( a__and_2(x_1, x_2) ) = x_1 + x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 2x_1 POL( a__isNatIList_1(x_1) ) = 2x_1 POL( a__isNatList_1(x_1) ) = x_1 POL( cons_2(x_1, x_2) ) = x_1 + x_2 POL( a__isNat_1(x_1) ) = x_1 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( isNatList_1(x_1) ) = x_1 POL( isNat_1(x_1) ) = x_1 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = x_1 + 1 POL( a__length_1(x_1) ) = x_1 + 1 POL( zeros ) = 0 POL( a__zeros ) = 0 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( uTake1_1(x_1) ) = 0 POL( a__uTake1_1(x_1) ) = max{0, -2} POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 POL( uLength_2(x_1, x_2) ) = x_2 + 1 POL( a__uLength_2(x_1, x_2) ) = x_2 + 1 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 + 2 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 POL( A__ISNATLIST_1(x_1) ) = x_1 + 2 POL( A__ISNAT_1(x_1) ) = x_1 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) A__ISNAT(s(N)) -> A__ISNAT(N) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (24) Complex Obligation (AND) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: A__ISNAT(s(N)) -> A__ISNAT(N) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: A__ISNAT(s(N)) -> A__ISNAT(N) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *A__ISNAT(s(N)) -> A__ISNAT(N) The graph contains the following edges 1 > 1 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATILIST(IL) -> A__ISNATLIST(IL) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__ISNATILIST(IL) -> A__ISNATLIST(IL) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = x_2 POL( mark_1(x_1) ) = x_1 POL( and_2(x_1, x_2) ) = x_1 + x_2 POL( a__and_2(x_1, x_2) ) = x_1 + x_2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 2x_1 + 2 POL( a__isNatIList_1(x_1) ) = 2x_1 + 2 POL( a__isNatList_1(x_1) ) = x_1 POL( cons_2(x_1, x_2) ) = 2x_1 + x_2 POL( a__isNat_1(x_1) ) = 2x_1 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( isNatList_1(x_1) ) = x_1 POL( isNat_1(x_1) ) = 2x_1 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = 2x_1 POL( a__length_1(x_1) ) = 2x_1 POL( zeros ) = 0 POL( a__zeros ) = 0 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( uTake1_1(x_1) ) = 0 POL( a__uTake1_1(x_1) ) = max{0, -2} POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 POL( uLength_2(x_1, x_2) ) = 2x_2 POL( a__uLength_2(x_1, x_2) ) = 2x_2 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 POL( A__ISNATLIST_1(x_1) ) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(and(X1, X2)) -> MARK(X1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(A__AND(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(tt) = [[0A]] >>> <<< POL(isNatIList(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__ISNATILIST(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(A__ISNATLIST(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__isNat(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__isNatList(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__isNatIList(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(isNatList(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(s(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(a__and(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(take(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(isNat(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(length(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__length(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(zeros) = [[1A]] >>> <<< POL(a__zeros) = [[1A]] >>> <<< POL(a__take(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 >>> <<< POL(uTake1(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(a__uTake1(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(uTake2(x_1, x_2, x_3, x_4)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 + [[0A]] * x_4 >>> <<< POL(a__uTake2(x_1, x_2, x_3, x_4)) = [[0A]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 + [[0A]] * x_4 >>> <<< POL(uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(a__uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[0A]] >>> <<< POL(nil) = [[0A]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> MARK(X2) MARK(isNatIList(X)) -> A__ISNATILIST(X) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(and(X1, X2)) -> MARK(X2) A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = x_2 + 1 POL( mark_1(x_1) ) = x_1 + 1 POL( and_2(x_1, x_2) ) = x_2 + 1 POL( a__and_2(x_1, x_2) ) = x_2 + 1 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = x_1 POL( a__isNatIList_1(x_1) ) = x_1 POL( a__isNatList_1(x_1) ) = x_1 POL( cons_2(x_1, x_2) ) = x_2 + 1 POL( a__isNat_1(x_1) ) = x_1 POL( take_2(x_1, x_2) ) = x_2 + 1 POL( isNatList_1(x_1) ) = x_1 POL( isNat_1(x_1) ) = x_1 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = x_1 POL( a__length_1(x_1) ) = x_1 POL( zeros ) = 0 POL( a__zeros ) = 1 POL( a__take_2(x_1, x_2) ) = x_2 + 1 POL( uTake1_1(x_1) ) = 0 POL( a__uTake1_1(x_1) ) = max{0, -2} POL( uTake2_4(x_1, ..., x_4) ) = x_4 + 1 POL( a__uTake2_4(x_1, ..., x_4) ) = x_4 + 2 POL( uLength_2(x_1, x_2) ) = x_2 POL( a__uLength_2(x_1, x_2) ) = x_2 + 1 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = x_1 + 1 POL( A__ISNATILIST_1(x_1) ) = x_1 + 1 POL( A__ISNATLIST_1(x_1) ) = x_1 + 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) A__AND(tt, T) -> MARK(T) MARK(isNatIList(X)) -> A__ISNATILIST(X) MARK(isNatList(X)) -> A__ISNATLIST(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( A__AND_2(x_1, x_2) ) = 2x_2 POL( mark_1(x_1) ) = x_1 + 1 POL( and_2(x_1, x_2) ) = x_2 + 2 POL( a__and_2(x_1, x_2) ) = x_2 + 2 POL( tt ) = 0 POL( isNatIList_1(x_1) ) = 2x_1 POL( a__isNatIList_1(x_1) ) = 2x_1 POL( a__isNatList_1(x_1) ) = 2x_1 POL( cons_2(x_1, x_2) ) = x_2 + 1 POL( a__isNat_1(x_1) ) = 2x_1 POL( take_2(x_1, x_2) ) = x_2 + 1 POL( isNatList_1(x_1) ) = 2x_1 POL( isNat_1(x_1) ) = 2x_1 POL( s_1(x_1) ) = x_1 POL( length_1(x_1) ) = x_1 POL( a__length_1(x_1) ) = x_1 POL( zeros ) = 0 POL( a__zeros ) = 1 POL( a__take_2(x_1, x_2) ) = x_2 + 1 POL( uTake1_1(x_1) ) = 0 POL( a__uTake1_1(x_1) ) = 0 POL( uTake2_4(x_1, ..., x_4) ) = x_4 + 2 POL( a__uTake2_4(x_1, ..., x_4) ) = x_4 + 2 POL( uLength_2(x_1, x_2) ) = x_2 POL( a__uLength_2(x_1, x_2) ) = x_2 + 1 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = 2x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) a__and(tt, T) -> mark(T) mark(isNatIList(X)) -> a__isNatIList(X) a__isNatIList(IL) -> a__isNatList(IL) a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__and(X1, X2) -> and(X1, X2) a__isNatIList(zeros) -> tt a__isNatIList(X) -> isNatIList(X) a__isNatList(nil) -> tt a__isNatList(X) -> isNatList(X) a__isNat(0) -> tt a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__take(X1, X2) -> take(X1, X2) a__uTake1(tt) -> nil a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) a__uLength(tt, L) -> s(a__length(mark(L))) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__zeros -> cons(0, zeros) a__zeros -> zeros ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: A__AND(tt, T) -> MARK(T) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MARK(s(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (46) YES