60.57/16.48 YES 66.48/17.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 66.48/17.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 66.48/17.97 66.48/17.97 66.48/17.97 Termination w.r.t. Q of the given QTRS could be proven: 66.48/17.97 66.48/17.97 (0) QTRS 66.48/17.97 (1) DependencyPairsProof [EQUIVALENT, 87 ms] 66.48/17.97 (2) QDP 66.48/17.97 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 66.48/17.97 (4) QDP 66.48/17.97 (5) QDPOrderProof [EQUIVALENT, 252 ms] 66.48/17.97 (6) QDP 66.48/17.97 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 66.48/17.97 (8) AND 66.48/17.97 (9) QDP 66.48/17.97 (10) QDPQMonotonicMRRProof [EQUIVALENT, 71 ms] 66.48/17.97 (11) QDP 66.48/17.97 (12) QDPQMonotonicMRRProof [EQUIVALENT, 38 ms] 66.48/17.97 (13) QDP 66.48/17.97 (14) QDPOrderProof [EQUIVALENT, 91 ms] 66.48/17.97 (15) QDP 66.48/17.97 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 66.48/17.97 (17) TRUE 66.48/17.97 (18) QDP 66.48/17.97 (19) QDPOrderProof [EQUIVALENT, 92 ms] 66.48/17.97 (20) QDP 66.48/17.97 (21) QDPOrderProof [EQUIVALENT, 43 ms] 66.48/17.97 (22) QDP 66.48/17.97 (23) QDPOrderProof [EQUIVALENT, 38 ms] 66.48/17.97 (24) QDP 66.48/17.97 (25) QDPOrderProof [EQUIVALENT, 104 ms] 66.48/17.97 (26) QDP 66.48/17.97 (27) DependencyGraphProof [EQUIVALENT, 0 ms] 66.48/17.97 (28) AND 66.48/17.97 (29) QDP 66.48/17.97 (30) UsableRulesProof [EQUIVALENT, 0 ms] 66.48/17.97 (31) QDP 66.48/17.97 (32) QReductionProof [EQUIVALENT, 0 ms] 66.48/17.97 (33) QDP 66.48/17.97 (34) QDPSizeChangeProof [EQUIVALENT, 0 ms] 66.48/17.97 (35) YES 66.48/17.97 (36) QDP 66.48/17.97 (37) QDPOrderProof [EQUIVALENT, 91 ms] 66.48/17.97 (38) QDP 66.48/17.97 (39) QDPQMonotonicMRRProof [EQUIVALENT, 103 ms] 66.48/17.97 (40) QDP 66.48/17.97 (41) QDPQMonotonicMRRProof [EQUIVALENT, 118 ms] 66.48/17.97 (42) QDP 66.48/17.97 (43) QDPOrderProof [EQUIVALENT, 297 ms] 66.48/17.97 (44) QDP 66.48/17.97 (45) QDPOrderProof [EQUIVALENT, 87 ms] 66.48/17.97 (46) QDP 66.48/17.97 (47) DependencyGraphProof [EQUIVALENT, 0 ms] 66.48/17.97 (48) QDP 66.48/17.97 (49) QDPQMonotonicMRRProof [EQUIVALENT, 77 ms] 66.48/17.97 (50) QDP 66.48/17.97 (51) UsableRulesProof [EQUIVALENT, 0 ms] 66.48/17.97 (52) QDP 66.48/17.97 (53) QReductionProof [EQUIVALENT, 0 ms] 66.48/17.97 (54) QDP 66.48/17.97 (55) QDPSizeChangeProof [EQUIVALENT, 0 ms] 66.48/17.97 (56) YES 66.48/17.97 66.48/17.97 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (0) 66.48/17.97 Obligation: 66.48/17.97 Q restricted rewrite system: 66.48/17.97 The TRS R consists of the following rules: 66.48/17.97 66.48/17.97 a__and(tt, T) -> mark(T) 66.48/17.97 a__isNatIList(IL) -> a__isNatList(IL) 66.48/17.97 a__isNat(0) -> tt 66.48/17.97 a__isNat(s(N)) -> a__isNat(N) 66.48/17.97 a__isNat(length(L)) -> a__isNatList(L) 66.48/17.97 a__isNatIList(zeros) -> tt 66.48/17.97 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__isNatList(nil) -> tt 66.48/17.97 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.48/17.97 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__zeros -> cons(0, zeros) 66.48/17.97 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.48/17.97 a__uTake1(tt) -> nil 66.48/17.97 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) 66.48/17.97 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.48/17.97 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.48/17.97 a__uLength(tt, L) -> s(a__length(mark(L))) 66.48/17.97 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.48/17.97 mark(isNatIList(X)) -> a__isNatIList(X) 66.48/17.97 mark(isNatList(X)) -> a__isNatList(X) 66.48/17.97 mark(isNat(X)) -> a__isNat(X) 66.48/17.97 mark(length(X)) -> a__length(mark(X)) 66.48/17.97 mark(zeros) -> a__zeros 66.48/17.97 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.48/17.97 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.48/17.97 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.48/17.97 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.48/17.97 mark(tt) -> tt 66.48/17.97 mark(0) -> 0 66.48/17.97 mark(s(X)) -> s(mark(X)) 66.48/17.97 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.48/17.97 mark(nil) -> nil 66.48/17.97 a__and(X1, X2) -> and(X1, X2) 66.48/17.97 a__isNatIList(X) -> isNatIList(X) 66.48/17.97 a__isNatList(X) -> isNatList(X) 66.48/17.97 a__isNat(X) -> isNat(X) 66.48/17.97 a__length(X) -> length(X) 66.48/17.97 a__zeros -> zeros 66.48/17.97 a__take(X1, X2) -> take(X1, X2) 66.48/17.97 a__uTake1(X) -> uTake1(X) 66.48/17.97 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.48/17.97 a__uLength(X1, X2) -> uLength(X1, X2) 66.48/17.97 66.48/17.97 The set Q consists of the following terms: 66.48/17.97 66.48/17.97 a__isNatIList(x0) 66.48/17.97 a__zeros 66.48/17.97 mark(and(x0, x1)) 66.48/17.97 mark(isNatIList(x0)) 66.48/17.97 mark(isNatList(x0)) 66.48/17.97 mark(isNat(x0)) 66.48/17.97 mark(length(x0)) 66.48/17.97 mark(zeros) 66.48/17.97 mark(take(x0, x1)) 66.48/17.97 mark(uTake1(x0)) 66.48/17.97 mark(uTake2(x0, x1, x2, x3)) 66.48/17.97 mark(uLength(x0, x1)) 66.48/17.97 mark(tt) 66.48/17.97 mark(0) 66.48/17.97 mark(s(x0)) 66.48/17.97 mark(cons(x0, x1)) 66.48/17.97 mark(nil) 66.48/17.97 a__and(x0, x1) 66.48/17.97 a__isNatList(x0) 66.48/17.97 a__isNat(x0) 66.48/17.97 a__length(x0) 66.48/17.97 a__take(x0, x1) 66.48/17.97 a__uTake1(x0) 66.48/17.97 a__uTake2(x0, x1, x2, x3) 66.48/17.97 a__uLength(x0, x1) 66.48/17.97 66.48/17.97 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (1) DependencyPairsProof (EQUIVALENT) 66.48/17.97 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (2) 66.48/17.97 Obligation: 66.48/17.97 Q DP problem: 66.48/17.97 The TRS P consists of the following rules: 66.48/17.97 66.48/17.97 A__AND(tt, T) -> MARK(T) 66.48/17.97 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.48/17.97 A__ISNAT(s(N)) -> A__ISNAT(N) 66.48/17.97 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 A__TAKE(0, IL) -> A__UTAKE1(a__isNatIList(IL)) 66.48/17.97 A__TAKE(0, IL) -> A__ISNATILIST(IL) 66.48/17.97 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) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 A__UTAKE2(tt, M, N, IL) -> MARK(N) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNAT(N) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 66.48/17.97 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.48/17.97 A__ULENGTH(tt, L) -> MARK(L) 66.48/17.97 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.48/17.97 MARK(and(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(and(X1, X2)) -> MARK(X2) 66.48/17.97 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.48/17.97 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.48/17.97 MARK(isNat(X)) -> A__ISNAT(X) 66.48/17.97 MARK(length(X)) -> A__LENGTH(mark(X)) 66.48/17.97 MARK(length(X)) -> MARK(X) 66.48/17.97 MARK(zeros) -> A__ZEROS 66.48/17.97 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X2) 66.48/17.97 MARK(uTake1(X)) -> A__UTAKE1(mark(X)) 66.48/17.97 MARK(uTake1(X)) -> MARK(X) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) 66.48/17.97 MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) 66.48/17.97 MARK(uLength(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(s(X)) -> MARK(X) 66.48/17.97 MARK(cons(X1, X2)) -> MARK(X1) 66.48/17.97 66.48/17.97 The TRS R consists of the following rules: 66.48/17.97 66.48/17.97 a__and(tt, T) -> mark(T) 66.48/17.97 a__isNatIList(IL) -> a__isNatList(IL) 66.48/17.97 a__isNat(0) -> tt 66.48/17.97 a__isNat(s(N)) -> a__isNat(N) 66.48/17.97 a__isNat(length(L)) -> a__isNatList(L) 66.48/17.97 a__isNatIList(zeros) -> tt 66.48/17.97 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__isNatList(nil) -> tt 66.48/17.97 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.48/17.97 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__zeros -> cons(0, zeros) 66.48/17.97 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.48/17.97 a__uTake1(tt) -> nil 66.48/17.97 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) 66.48/17.97 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.48/17.97 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.48/17.97 a__uLength(tt, L) -> s(a__length(mark(L))) 66.48/17.97 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.48/17.97 mark(isNatIList(X)) -> a__isNatIList(X) 66.48/17.97 mark(isNatList(X)) -> a__isNatList(X) 66.48/17.97 mark(isNat(X)) -> a__isNat(X) 66.48/17.97 mark(length(X)) -> a__length(mark(X)) 66.48/17.97 mark(zeros) -> a__zeros 66.48/17.97 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.48/17.97 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.48/17.97 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.48/17.97 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.48/17.97 mark(tt) -> tt 66.48/17.97 mark(0) -> 0 66.48/17.97 mark(s(X)) -> s(mark(X)) 66.48/17.97 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.48/17.97 mark(nil) -> nil 66.48/17.97 a__and(X1, X2) -> and(X1, X2) 66.48/17.97 a__isNatIList(X) -> isNatIList(X) 66.48/17.97 a__isNatList(X) -> isNatList(X) 66.48/17.97 a__isNat(X) -> isNat(X) 66.48/17.97 a__length(X) -> length(X) 66.48/17.97 a__zeros -> zeros 66.48/17.97 a__take(X1, X2) -> take(X1, X2) 66.48/17.97 a__uTake1(X) -> uTake1(X) 66.48/17.97 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.48/17.97 a__uLength(X1, X2) -> uLength(X1, X2) 66.48/17.97 66.48/17.97 The set Q consists of the following terms: 66.48/17.97 66.48/17.97 a__isNatIList(x0) 66.48/17.97 a__zeros 66.48/17.97 mark(and(x0, x1)) 66.48/17.97 mark(isNatIList(x0)) 66.48/17.97 mark(isNatList(x0)) 66.48/17.97 mark(isNat(x0)) 66.48/17.97 mark(length(x0)) 66.48/17.97 mark(zeros) 66.48/17.97 mark(take(x0, x1)) 66.48/17.97 mark(uTake1(x0)) 66.48/17.97 mark(uTake2(x0, x1, x2, x3)) 66.48/17.97 mark(uLength(x0, x1)) 66.48/17.97 mark(tt) 66.48/17.97 mark(0) 66.48/17.97 mark(s(x0)) 66.48/17.97 mark(cons(x0, x1)) 66.48/17.97 mark(nil) 66.48/17.97 a__and(x0, x1) 66.48/17.97 a__isNatList(x0) 66.48/17.97 a__isNat(x0) 66.48/17.97 a__length(x0) 66.48/17.97 a__take(x0, x1) 66.48/17.97 a__uTake1(x0) 66.48/17.97 a__uTake2(x0, x1, x2, x3) 66.48/17.97 a__uLength(x0, x1) 66.48/17.97 66.48/17.97 We have to consider all minimal (P,Q,R)-chains. 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (3) DependencyGraphProof (EQUIVALENT) 66.48/17.97 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (4) 66.48/17.97 Obligation: 66.48/17.97 Q DP problem: 66.48/17.97 The TRS P consists of the following rules: 66.48/17.97 66.48/17.97 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.48/17.97 A__AND(tt, T) -> MARK(T) 66.48/17.97 MARK(and(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(and(X1, X2)) -> MARK(X2) 66.48/17.97 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.48/17.97 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.48/17.97 A__ISNAT(s(N)) -> A__ISNAT(N) 66.48/17.97 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.48/17.97 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.48/17.97 MARK(isNat(X)) -> A__ISNAT(X) 66.48/17.97 MARK(length(X)) -> A__LENGTH(mark(X)) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.48/17.97 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNAT(N) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 66.48/17.97 A__ULENGTH(tt, L) -> MARK(L) 66.48/17.97 MARK(length(X)) -> MARK(X) 66.48/17.97 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 66.48/17.97 A__TAKE(0, IL) -> A__ISNATILIST(IL) 66.48/17.97 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) 66.48/17.97 A__UTAKE2(tt, M, N, IL) -> MARK(N) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X2) 66.48/17.97 MARK(uTake1(X)) -> MARK(X) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) 66.48/17.97 MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) 66.48/17.97 MARK(uLength(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(s(X)) -> MARK(X) 66.48/17.97 MARK(cons(X1, X2)) -> MARK(X1) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 66.48/17.97 The TRS R consists of the following rules: 66.48/17.97 66.48/17.97 a__and(tt, T) -> mark(T) 66.48/17.97 a__isNatIList(IL) -> a__isNatList(IL) 66.48/17.97 a__isNat(0) -> tt 66.48/17.97 a__isNat(s(N)) -> a__isNat(N) 66.48/17.97 a__isNat(length(L)) -> a__isNatList(L) 66.48/17.97 a__isNatIList(zeros) -> tt 66.48/17.97 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__isNatList(nil) -> tt 66.48/17.97 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.48/17.97 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 a__zeros -> cons(0, zeros) 66.48/17.97 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.48/17.97 a__uTake1(tt) -> nil 66.48/17.97 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) 66.48/17.97 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.48/17.97 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.48/17.97 a__uLength(tt, L) -> s(a__length(mark(L))) 66.48/17.97 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.48/17.97 mark(isNatIList(X)) -> a__isNatIList(X) 66.48/17.97 mark(isNatList(X)) -> a__isNatList(X) 66.48/17.97 mark(isNat(X)) -> a__isNat(X) 66.48/17.97 mark(length(X)) -> a__length(mark(X)) 66.48/17.97 mark(zeros) -> a__zeros 66.48/17.97 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.48/17.97 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.48/17.97 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.48/17.97 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.48/17.97 mark(tt) -> tt 66.48/17.97 mark(0) -> 0 66.48/17.97 mark(s(X)) -> s(mark(X)) 66.48/17.97 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.48/17.97 mark(nil) -> nil 66.48/17.97 a__and(X1, X2) -> and(X1, X2) 66.48/17.97 a__isNatIList(X) -> isNatIList(X) 66.48/17.97 a__isNatList(X) -> isNatList(X) 66.48/17.97 a__isNat(X) -> isNat(X) 66.48/17.97 a__length(X) -> length(X) 66.48/17.97 a__zeros -> zeros 66.48/17.97 a__take(X1, X2) -> take(X1, X2) 66.48/17.97 a__uTake1(X) -> uTake1(X) 66.48/17.97 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.48/17.97 a__uLength(X1, X2) -> uLength(X1, X2) 66.48/17.97 66.48/17.97 The set Q consists of the following terms: 66.48/17.97 66.48/17.97 a__isNatIList(x0) 66.48/17.97 a__zeros 66.48/17.97 mark(and(x0, x1)) 66.48/17.97 mark(isNatIList(x0)) 66.48/17.97 mark(isNatList(x0)) 66.48/17.97 mark(isNat(x0)) 66.48/17.97 mark(length(x0)) 66.48/17.97 mark(zeros) 66.48/17.97 mark(take(x0, x1)) 66.48/17.97 mark(uTake1(x0)) 66.48/17.97 mark(uTake2(x0, x1, x2, x3)) 66.48/17.97 mark(uLength(x0, x1)) 66.48/17.97 mark(tt) 66.48/17.97 mark(0) 66.48/17.97 mark(s(x0)) 66.48/17.97 mark(cons(x0, x1)) 66.48/17.97 mark(nil) 66.48/17.97 a__and(x0, x1) 66.48/17.97 a__isNatList(x0) 66.48/17.97 a__isNat(x0) 66.48/17.97 a__length(x0) 66.48/17.97 a__take(x0, x1) 66.48/17.97 a__uTake1(x0) 66.48/17.97 a__uTake2(x0, x1, x2, x3) 66.48/17.97 a__uLength(x0, x1) 66.48/17.97 66.48/17.97 We have to consider all minimal (P,Q,R)-chains. 66.48/17.97 ---------------------------------------- 66.48/17.97 66.48/17.97 (5) QDPOrderProof (EQUIVALENT) 66.48/17.97 We use the reduction pair processor [LPAR04,JAR06]. 66.48/17.97 66.48/17.97 66.48/17.97 The following pairs can be oriented strictly and are deleted. 66.48/17.97 66.48/17.97 A__LENGTH(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNAT(N) 66.48/17.97 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 66.48/17.97 A__ULENGTH(tt, L) -> MARK(L) 66.48/17.97 MARK(length(X)) -> MARK(X) 66.48/17.97 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 66.48/17.97 A__TAKE(0, IL) -> A__ISNATILIST(IL) 66.48/17.97 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) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X1) 66.48/17.97 MARK(take(X1, X2)) -> MARK(X2) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> A__UTAKE2(mark(X1), X2, X3, X4) 66.48/17.97 MARK(uTake2(X1, X2, X3, X4)) -> MARK(X1) 66.48/17.97 MARK(uLength(X1, X2)) -> MARK(X1) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(M) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNAT(N) 66.48/17.97 A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) 66.48/17.97 The remaining pairs can at least be oriented weakly. 66.48/17.97 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.48/17.97 66.48/17.97 POL( A__AND_2(x_1, x_2) ) = 2x_2 66.48/17.97 POL( A__LENGTH_1(x_1) ) = x_1 + 2 66.48/17.97 POL( A__TAKE_2(x_1, x_2) ) = 2x_2 + 1 66.48/17.97 POL( A__ULENGTH_2(x_1, x_2) ) = x_2 + 2 66.48/17.97 POL( A__UTAKE2_4(x_1, ..., x_4) ) = x_3 66.48/17.97 POL( mark_1(x_1) ) = x_1 66.48/17.97 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 66.48/17.97 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 66.48/17.97 POL( tt ) = 0 66.48/17.97 POL( isNatIList_1(x_1) ) = 0 66.48/17.97 POL( a__isNatIList_1(x_1) ) = 0 66.48/17.97 POL( a__isNatList_1(x_1) ) = 0 66.48/17.97 POL( cons_2(x_1, x_2) ) = x_1 + x_2 66.48/17.97 POL( a__isNat_1(x_1) ) = 0 66.48/17.97 POL( take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 66.48/17.97 POL( isNatList_1(x_1) ) = 0 66.48/17.97 POL( isNat_1(x_1) ) = 0 66.48/17.97 POL( s_1(x_1) ) = x_1 66.48/17.97 POL( length_1(x_1) ) = x_1 + 2 66.48/17.97 POL( a__length_1(x_1) ) = x_1 + 2 66.48/17.97 POL( zeros ) = 0 66.48/17.97 POL( a__zeros ) = 0 66.48/17.97 POL( a__take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 66.48/17.97 POL( uTake1_1(x_1) ) = x_1 66.48/17.97 POL( a__uTake1_1(x_1) ) = x_1 66.48/17.97 POL( uTake2_4(x_1, ..., x_4) ) = x_1 + x_2 + x_3 + 2x_4 + 2 66.76/18.00 POL( a__uTake2_4(x_1, ..., x_4) ) = x_1 + x_2 + x_3 + 2x_4 + 2 66.76/18.00 POL( uLength_2(x_1, x_2) ) = x_1 + x_2 + 2 66.76/18.00 POL( a__uLength_2(x_1, x_2) ) = x_1 + x_2 + 2 66.76/18.00 POL( 0 ) = 0 66.76/18.00 POL( nil ) = 0 66.76/18.00 POL( MARK_1(x_1) ) = x_1 66.76/18.00 POL( A__ISNATILIST_1(x_1) ) = 0 66.76/18.00 POL( A__ISNATLIST_1(x_1) ) = 0 66.76/18.00 POL( A__ISNAT_1(x_1) ) = 0 66.76/18.00 66.76/18.00 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.00 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.00 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) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__zeros -> zeros 66.76/18.00 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (6) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.00 A__AND(tt, T) -> MARK(T) 66.76/18.00 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.00 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.00 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.00 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.00 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.00 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.00 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.00 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.00 MARK(length(X)) -> A__LENGTH(mark(X)) 66.76/18.00 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.76/18.00 A__UTAKE2(tt, M, N, IL) -> MARK(N) 66.76/18.00 MARK(uTake1(X)) -> MARK(X) 66.76/18.00 MARK(uLength(X1, X2)) -> A__ULENGTH(mark(X1), X2) 66.76/18.00 MARK(s(X)) -> MARK(X) 66.76/18.00 MARK(cons(X1, X2)) -> MARK(X1) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (7) DependencyGraphProof (EQUIVALENT) 66.76/18.00 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (8) 66.76/18.00 Complex Obligation (AND) 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (9) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.76/18.00 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (10) QDPQMonotonicMRRProof (EQUIVALENT) 66.76/18.00 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 66.76/18.00 66.76/18.00 66.76/18.00 Strictly oriented rules of the TRS R: 66.76/18.00 66.76/18.00 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.00 66.76/18.00 Used ordering: Polynomial interpretation [POLO]: 66.76/18.00 66.76/18.00 POL(0) = 0 66.76/18.00 POL(A__LENGTH(x_1)) = 2*x_1 66.76/18.00 POL(A__ULENGTH(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(a__isNat(x_1)) = 0 66.76/18.00 POL(a__isNatIList(x_1)) = 0 66.76/18.00 POL(a__isNatList(x_1)) = 0 66.76/18.00 POL(a__length(x_1)) = x_1 66.76/18.00 POL(a__take(x_1, x_2)) = 2 + x_1 + x_2 66.76/18.00 POL(a__uLength(x_1, x_2)) = x_1 + x_2 66.76/18.00 POL(a__uTake1(x_1)) = 2*x_1 66.76/18.00 POL(a__uTake2(x_1, x_2, x_3, x_4)) = 2 + x_1 + x_2 + x_3 + x_4 66.76/18.00 POL(a__zeros) = 0 66.76/18.00 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(cons(x_1, x_2)) = x_1 + x_2 66.76/18.00 POL(isNat(x_1)) = 0 66.76/18.00 POL(isNatIList(x_1)) = 0 66.76/18.00 POL(isNatList(x_1)) = 0 66.76/18.00 POL(length(x_1)) = x_1 66.76/18.00 POL(mark(x_1)) = x_1 66.76/18.00 POL(nil) = 0 66.76/18.00 POL(s(x_1)) = x_1 66.76/18.00 POL(take(x_1, x_2)) = 2 + x_1 + x_2 66.76/18.00 POL(tt) = 0 66.76/18.00 POL(uLength(x_1, x_2)) = x_1 + x_2 66.76/18.00 POL(uTake1(x_1)) = 2*x_1 66.76/18.00 POL(uTake2(x_1, x_2, x_3, x_4)) = 2 + x_1 + x_2 + x_3 + x_4 66.76/18.00 POL(zeros) = 0 66.76/18.00 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (11) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.76/18.00 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (12) QDPQMonotonicMRRProof (EQUIVALENT) 66.76/18.00 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 66.76/18.00 66.76/18.00 66.76/18.00 Strictly oriented rules of the TRS R: 66.76/18.00 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 66.76/18.00 Used ordering: Polynomial interpretation [POLO]: 66.76/18.00 66.76/18.00 POL(0) = 0 66.76/18.00 POL(A__LENGTH(x_1)) = 2*x_1 66.76/18.00 POL(A__ULENGTH(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(a__isNat(x_1)) = 0 66.76/18.00 POL(a__isNatIList(x_1)) = 0 66.76/18.00 POL(a__isNatList(x_1)) = 0 66.76/18.00 POL(a__length(x_1)) = x_1 66.76/18.00 POL(a__take(x_1, x_2)) = x_1 + x_2 66.76/18.00 POL(a__uLength(x_1, x_2)) = x_1 + 2*x_2 66.76/18.00 POL(a__uTake1(x_1)) = 2 + 2*x_1 66.76/18.00 POL(a__uTake2(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + x_3 + 2*x_4 66.76/18.00 POL(a__zeros) = 0 66.76/18.00 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.00 POL(cons(x_1, x_2)) = x_1 + 2*x_2 66.76/18.00 POL(isNat(x_1)) = 0 66.76/18.00 POL(isNatIList(x_1)) = 0 66.76/18.00 POL(isNatList(x_1)) = 0 66.76/18.00 POL(length(x_1)) = x_1 66.76/18.00 POL(mark(x_1)) = x_1 66.76/18.00 POL(nil) = 0 66.76/18.00 POL(s(x_1)) = 2*x_1 66.76/18.00 POL(take(x_1, x_2)) = x_1 + x_2 66.76/18.00 POL(tt) = 0 66.76/18.00 POL(uLength(x_1, x_2)) = x_1 + 2*x_2 66.76/18.00 POL(uTake1(x_1)) = 2 + 2*x_1 66.76/18.00 POL(uTake2(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + x_3 + 2*x_4 66.76/18.00 POL(zeros) = 0 66.76/18.00 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (13) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.76/18.00 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (14) QDPOrderProof (EQUIVALENT) 66.76/18.00 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.00 66.76/18.00 66.76/18.00 The following pairs can be oriented strictly and are deleted. 66.76/18.00 66.76/18.00 A__LENGTH(cons(N, L)) -> A__ULENGTH(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 The remaining pairs can at least be oriented weakly. 66.76/18.00 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(A__ULENGTH(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[1A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(tt) = [[2A]] 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(A__LENGTH(x_1)) = [[3A]] + [[1A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(mark(x_1)) = [[1A]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(cons(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__and(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[0A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__isNat(x_1)) = [[1A]] + [[1A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__isNatList(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(and(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(isNatIList(x_1)) = [[-I]] + [[2A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__isNatIList(x_1)) = [[0A]] + [[2A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(take(x_1, x_2)) = [[3A]] + [[2A]] * x_1 + [[2A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(isNatList(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(isNat(x_1)) = [[0A]] + [[1A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(s(x_1)) = [[2A]] + [[1A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(length(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__length(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(zeros) = [[0A]] 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__zeros) = [[1A]] 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__take(x_1, x_2)) = [[3A]] + [[2A]] * x_1 + [[2A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(uTake1(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__uTake1(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(uTake2(x_1, x_2, x_3, x_4)) = [[4A]] + [[-I]] * x_1 + [[3A]] * x_2 + [[-I]] * x_3 + [[3A]] * x_4 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__uTake2(x_1, x_2, x_3, x_4)) = [[4A]] + [[-I]] * x_1 + [[3A]] * x_2 + [[-I]] * x_3 + [[3A]] * x_4 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(a__uLength(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(0) = [[1A]] 66.76/18.00 >>> 66.76/18.00 66.76/18.00 <<< 66.76/18.00 POL(nil) = [[2A]] 66.76/18.00 >>> 66.76/18.00 66.76/18.00 66.76/18.00 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.00 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 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) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__zeros -> zeros 66.76/18.00 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (15) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 A__ULENGTH(tt, L) -> A__LENGTH(mark(L)) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (16) DependencyGraphProof (EQUIVALENT) 66.76/18.00 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (17) 66.76/18.00 TRUE 66.76/18.00 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (18) 66.76/18.00 Obligation: 66.76/18.00 Q DP problem: 66.76/18.00 The TRS P consists of the following rules: 66.76/18.00 66.76/18.00 A__AND(tt, T) -> MARK(T) 66.76/18.00 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.00 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.00 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.00 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.00 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.00 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.00 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.00 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.76/18.00 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.00 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.00 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.00 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.00 MARK(uTake1(X)) -> MARK(X) 66.76/18.00 MARK(s(X)) -> MARK(X) 66.76/18.00 MARK(cons(X1, X2)) -> MARK(X1) 66.76/18.00 66.76/18.00 The TRS R consists of the following rules: 66.76/18.00 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__zeros -> cons(0, zeros) 66.76/18.00 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 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) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.00 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__zeros -> zeros 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.00 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.00 66.76/18.00 The set Q consists of the following terms: 66.76/18.00 66.76/18.00 a__isNatIList(x0) 66.76/18.00 a__zeros 66.76/18.00 mark(and(x0, x1)) 66.76/18.00 mark(isNatIList(x0)) 66.76/18.00 mark(isNatList(x0)) 66.76/18.00 mark(isNat(x0)) 66.76/18.00 mark(length(x0)) 66.76/18.00 mark(zeros) 66.76/18.00 mark(take(x0, x1)) 66.76/18.00 mark(uTake1(x0)) 66.76/18.00 mark(uTake2(x0, x1, x2, x3)) 66.76/18.00 mark(uLength(x0, x1)) 66.76/18.00 mark(tt) 66.76/18.00 mark(0) 66.76/18.00 mark(s(x0)) 66.76/18.00 mark(cons(x0, x1)) 66.76/18.00 mark(nil) 66.76/18.00 a__and(x0, x1) 66.76/18.00 a__isNatList(x0) 66.76/18.00 a__isNat(x0) 66.76/18.00 a__length(x0) 66.76/18.00 a__take(x0, x1) 66.76/18.00 a__uTake1(x0) 66.76/18.00 a__uTake2(x0, x1, x2, x3) 66.76/18.00 a__uLength(x0, x1) 66.76/18.00 66.76/18.00 We have to consider all minimal (P,Q,R)-chains. 66.76/18.00 ---------------------------------------- 66.76/18.00 66.76/18.00 (19) QDPOrderProof (EQUIVALENT) 66.76/18.00 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.00 66.76/18.00 66.76/18.00 The following pairs can be oriented strictly and are deleted. 66.76/18.00 66.76/18.00 MARK(cons(X1, X2)) -> MARK(X1) 66.76/18.00 The remaining pairs can at least be oriented weakly. 66.76/18.00 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.00 66.76/18.00 POL( A__AND_2(x_1, x_2) ) = x_2 66.76/18.00 POL( mark_1(x_1) ) = x_1 66.76/18.00 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 66.76/18.00 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 66.76/18.00 POL( tt ) = 0 66.76/18.00 POL( isNatIList_1(x_1) ) = 0 66.76/18.00 POL( a__isNatIList_1(x_1) ) = 0 66.76/18.00 POL( a__isNatList_1(x_1) ) = 0 66.76/18.00 POL( cons_2(x_1, x_2) ) = 2x_1 + 2 66.76/18.00 POL( a__isNat_1(x_1) ) = 0 66.76/18.00 POL( take_2(x_1, x_2) ) = x_2 66.76/18.00 POL( isNatList_1(x_1) ) = 0 66.76/18.00 POL( isNat_1(x_1) ) = 0 66.76/18.00 POL( s_1(x_1) ) = x_1 66.76/18.00 POL( length_1(x_1) ) = 2 66.76/18.00 POL( a__length_1(x_1) ) = 2 66.76/18.00 POL( zeros ) = 2 66.76/18.00 POL( a__zeros ) = 2 66.76/18.00 POL( a__take_2(x_1, x_2) ) = x_2 66.76/18.00 POL( uTake1_1(x_1) ) = x_1 66.76/18.00 POL( a__uTake1_1(x_1) ) = x_1 66.76/18.00 POL( uTake2_4(x_1, ..., x_4) ) = 2x_3 + 2 66.76/18.00 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_3 + 2 66.76/18.00 POL( uLength_2(x_1, x_2) ) = 2 66.76/18.00 POL( a__uLength_2(x_1, x_2) ) = 2 66.76/18.00 POL( 0 ) = 0 66.76/18.00 POL( nil ) = 0 66.76/18.00 POL( MARK_1(x_1) ) = x_1 66.76/18.00 POL( A__ISNATILIST_1(x_1) ) = 0 66.76/18.00 POL( A__ISNATLIST_1(x_1) ) = 0 66.76/18.00 POL( A__ISNAT_1(x_1) ) = 0 66.76/18.00 66.76/18.00 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.00 66.76/18.00 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.00 a__and(tt, T) -> mark(T) 66.76/18.00 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.00 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.00 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.00 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.00 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.00 mark(isNat(X)) -> a__isNat(X) 66.76/18.00 a__isNat(s(N)) -> a__isNat(N) 66.76/18.00 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.00 mark(length(X)) -> a__length(mark(X)) 66.76/18.00 mark(zeros) -> a__zeros 66.76/18.00 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.00 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.00 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.00 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.00 mark(tt) -> tt 66.76/18.00 mark(0) -> 0 66.76/18.00 mark(s(X)) -> s(mark(X)) 66.76/18.00 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.00 mark(nil) -> nil 66.76/18.00 a__isNat(0) -> tt 66.76/18.00 a__isNat(X) -> isNat(X) 66.76/18.00 a__isNatList(nil) -> tt 66.76/18.00 a__isNatList(X) -> isNatList(X) 66.76/18.00 a__isNatIList(zeros) -> tt 66.76/18.00 a__isNatIList(X) -> isNatIList(X) 66.76/18.00 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.00 a__and(X1, X2) -> and(X1, X2) 66.76/18.00 a__length(X) -> length(X) 66.76/18.00 a__take(X1, X2) -> take(X1, X2) 66.76/18.00 a__uTake1(tt) -> nil 66.76/18.00 a__uTake1(X) -> uTake1(X) 66.76/18.00 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.01 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.01 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.01 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.01 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.01 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) 66.76/18.01 a__zeros -> cons(0, zeros) 66.76/18.01 a__zeros -> zeros 66.76/18.01 66.76/18.01 66.76/18.01 ---------------------------------------- 66.76/18.01 66.76/18.01 (20) 66.76/18.01 Obligation: 66.76/18.01 Q DP problem: 66.76/18.01 The TRS P consists of the following rules: 66.76/18.01 66.76/18.01 A__AND(tt, T) -> MARK(T) 66.76/18.01 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.01 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.01 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.01 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.01 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.01 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.01 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.01 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.01 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.01 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.01 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.76/18.01 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.76/18.01 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.01 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.01 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.01 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.01 MARK(uTake1(X)) -> MARK(X) 66.76/18.01 MARK(s(X)) -> MARK(X) 66.76/18.01 66.76/18.01 The TRS R consists of the following rules: 66.76/18.01 66.76/18.01 a__and(tt, T) -> mark(T) 66.76/18.01 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.01 a__isNat(0) -> tt 66.76/18.01 a__isNat(s(N)) -> a__isNat(N) 66.76/18.01 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.01 a__isNatIList(zeros) -> tt 66.76/18.01 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 a__isNatList(nil) -> tt 66.76/18.01 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.01 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 a__zeros -> cons(0, zeros) 66.76/18.01 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.01 a__uTake1(tt) -> nil 66.76/18.01 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) 66.76/18.01 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.01 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.01 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.01 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.01 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.01 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.01 mark(isNat(X)) -> a__isNat(X) 66.76/18.01 mark(length(X)) -> a__length(mark(X)) 66.76/18.01 mark(zeros) -> a__zeros 66.76/18.01 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.01 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.01 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.01 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.01 mark(tt) -> tt 66.76/18.01 mark(0) -> 0 66.76/18.01 mark(s(X)) -> s(mark(X)) 66.76/18.01 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.01 mark(nil) -> nil 66.76/18.01 a__and(X1, X2) -> and(X1, X2) 66.76/18.01 a__isNatIList(X) -> isNatIList(X) 66.76/18.01 a__isNatList(X) -> isNatList(X) 66.76/18.01 a__isNat(X) -> isNat(X) 66.76/18.01 a__length(X) -> length(X) 66.76/18.01 a__zeros -> zeros 66.76/18.01 a__take(X1, X2) -> take(X1, X2) 66.76/18.01 a__uTake1(X) -> uTake1(X) 66.76/18.01 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.01 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.01 66.76/18.01 The set Q consists of the following terms: 66.76/18.01 66.76/18.01 a__isNatIList(x0) 66.76/18.01 a__zeros 66.76/18.01 mark(and(x0, x1)) 66.76/18.01 mark(isNatIList(x0)) 66.76/18.01 mark(isNatList(x0)) 66.76/18.01 mark(isNat(x0)) 66.76/18.01 mark(length(x0)) 66.76/18.01 mark(zeros) 66.76/18.01 mark(take(x0, x1)) 66.76/18.01 mark(uTake1(x0)) 66.76/18.01 mark(uTake2(x0, x1, x2, x3)) 66.76/18.01 mark(uLength(x0, x1)) 66.76/18.01 mark(tt) 66.76/18.01 mark(0) 66.76/18.01 mark(s(x0)) 66.76/18.01 mark(cons(x0, x1)) 66.76/18.01 mark(nil) 66.76/18.01 a__and(x0, x1) 66.76/18.01 a__isNatList(x0) 66.76/18.01 a__isNat(x0) 66.76/18.01 a__length(x0) 66.76/18.01 a__take(x0, x1) 66.76/18.01 a__uTake1(x0) 66.76/18.01 a__uTake2(x0, x1, x2, x3) 66.76/18.01 a__uLength(x0, x1) 66.76/18.01 66.76/18.01 We have to consider all minimal (P,Q,R)-chains. 66.76/18.01 ---------------------------------------- 66.76/18.01 66.76/18.01 (21) QDPOrderProof (EQUIVALENT) 66.76/18.01 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.01 66.76/18.01 66.76/18.01 The following pairs can be oriented strictly and are deleted. 66.76/18.01 66.76/18.01 MARK(uTake1(X)) -> MARK(X) 66.76/18.01 The remaining pairs can at least be oriented weakly. 66.76/18.01 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.01 66.76/18.01 POL( A__AND_2(x_1, x_2) ) = 2x_2 + 2 66.76/18.01 POL( mark_1(x_1) ) = x_1 66.76/18.01 POL( and_2(x_1, x_2) ) = x_1 + 2x_2 66.76/18.01 POL( a__and_2(x_1, x_2) ) = x_1 + 2x_2 66.76/18.01 POL( tt ) = 0 66.76/18.01 POL( isNatIList_1(x_1) ) = 0 66.76/18.01 POL( a__isNatIList_1(x_1) ) = 0 66.76/18.01 POL( a__isNatList_1(x_1) ) = 0 66.76/18.01 POL( cons_2(x_1, x_2) ) = max{0, -2} 66.76/18.01 POL( a__isNat_1(x_1) ) = 0 66.76/18.01 POL( take_2(x_1, x_2) ) = 2 66.76/18.01 POL( isNatList_1(x_1) ) = 0 66.76/18.01 POL( isNat_1(x_1) ) = 0 66.76/18.01 POL( s_1(x_1) ) = x_1 66.76/18.01 POL( length_1(x_1) ) = 0 66.76/18.01 POL( a__length_1(x_1) ) = max{0, -2} 66.76/18.01 POL( zeros ) = 0 66.76/18.01 POL( a__zeros ) = 0 66.76/18.01 POL( a__take_2(x_1, x_2) ) = 2 66.76/18.01 POL( uTake1_1(x_1) ) = 2x_1 + 1 66.76/18.01 POL( a__uTake1_1(x_1) ) = 2x_1 + 1 66.76/18.01 POL( uTake2_4(x_1, ..., x_4) ) = 0 66.76/18.01 POL( a__uTake2_4(x_1, ..., x_4) ) = 0 66.76/18.01 POL( uLength_2(x_1, x_2) ) = 0 66.76/18.01 POL( a__uLength_2(x_1, x_2) ) = max{0, -2} 66.76/18.01 POL( 0 ) = 0 66.76/18.01 POL( nil ) = 0 66.76/18.01 POL( MARK_1(x_1) ) = x_1 + 2 66.76/18.01 POL( A__ISNATILIST_1(x_1) ) = 2 66.76/18.01 POL( A__ISNATLIST_1(x_1) ) = 2 66.76/18.01 POL( A__ISNAT_1(x_1) ) = 2 66.76/18.01 66.76/18.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.01 66.76/18.01 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.01 a__and(tt, T) -> mark(T) 66.76/18.01 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.01 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.01 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.01 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.01 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.01 mark(isNat(X)) -> a__isNat(X) 66.76/18.01 a__isNat(s(N)) -> a__isNat(N) 66.76/18.01 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.01 mark(length(X)) -> a__length(mark(X)) 66.76/18.01 mark(zeros) -> a__zeros 66.76/18.01 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.01 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.01 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.01 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.01 mark(tt) -> tt 66.76/18.01 mark(0) -> 0 66.76/18.01 mark(s(X)) -> s(mark(X)) 66.76/18.01 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.01 mark(nil) -> nil 66.76/18.01 a__isNat(0) -> tt 66.76/18.01 a__isNat(X) -> isNat(X) 66.76/18.01 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 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) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__zeros -> zeros 66.76/18.02 66.76/18.02 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (22) 66.76/18.02 Obligation: 66.76/18.02 Q DP problem: 66.76/18.02 The TRS P consists of the following rules: 66.76/18.02 66.76/18.02 A__AND(tt, T) -> MARK(T) 66.76/18.02 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.02 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.02 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.02 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.02 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.02 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.02 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.02 MARK(s(X)) -> MARK(X) 66.76/18.02 66.76/18.02 The TRS R consists of the following rules: 66.76/18.02 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 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) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__zeros -> zeros 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 66.76/18.02 The set Q consists of the following terms: 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.02 a__uTake1(x0) 66.76/18.02 a__uTake2(x0, x1, x2, x3) 66.76/18.02 a__uLength(x0, x1) 66.76/18.02 66.76/18.02 We have to consider all minimal (P,Q,R)-chains. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (23) QDPOrderProof (EQUIVALENT) 66.76/18.02 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.02 66.76/18.02 66.76/18.02 The following pairs can be oriented strictly and are deleted. 66.76/18.02 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__ISNAT(N) 66.76/18.02 A__ISNATLIST(take(N, IL)) -> A__ISNATILIST(IL) 66.76/18.02 The remaining pairs can at least be oriented weakly. 66.76/18.02 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.02 66.76/18.02 POL( A__AND_2(x_1, x_2) ) = 2x_2 + 2 66.76/18.02 POL( mark_1(x_1) ) = x_1 66.76/18.02 POL( and_2(x_1, x_2) ) = 2x_1 + x_2 66.76/18.02 POL( a__and_2(x_1, x_2) ) = 2x_1 + x_2 66.76/18.02 POL( tt ) = 0 66.76/18.02 POL( isNatIList_1(x_1) ) = x_1 66.76/18.02 POL( a__isNatIList_1(x_1) ) = x_1 66.76/18.02 POL( a__isNatList_1(x_1) ) = x_1 66.76/18.02 POL( cons_2(x_1, x_2) ) = 2x_1 + x_2 66.76/18.02 POL( a__isNat_1(x_1) ) = x_1 66.76/18.02 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 66.76/18.02 POL( isNatList_1(x_1) ) = x_1 66.76/18.02 POL( isNat_1(x_1) ) = x_1 66.76/18.02 POL( s_1(x_1) ) = x_1 66.76/18.02 POL( length_1(x_1) ) = 2x_1 66.76/18.02 POL( a__length_1(x_1) ) = 2x_1 66.76/18.02 POL( zeros ) = 0 66.76/18.02 POL( a__zeros ) = 0 66.76/18.02 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 66.76/18.02 POL( uTake1_1(x_1) ) = 0 66.76/18.02 POL( a__uTake1_1(x_1) ) = max{0, -2} 66.76/18.02 POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 1 66.76/18.02 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 1 66.76/18.02 POL( uLength_2(x_1, x_2) ) = 2x_2 66.76/18.02 POL( a__uLength_2(x_1, x_2) ) = 2x_2 66.76/18.02 POL( 0 ) = 0 66.76/18.02 POL( nil ) = 0 66.76/18.02 POL( MARK_1(x_1) ) = 2x_1 + 2 66.76/18.02 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 66.76/18.02 POL( A__ISNATLIST_1(x_1) ) = 2x_1 + 2 66.76/18.02 POL( A__ISNAT_1(x_1) ) = 2x_1 + 2 66.76/18.02 66.76/18.02 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.02 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 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) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__zeros -> zeros 66.76/18.02 66.76/18.02 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (24) 66.76/18.02 Obligation: 66.76/18.02 Q DP problem: 66.76/18.02 The TRS P consists of the following rules: 66.76/18.02 66.76/18.02 A__AND(tt, T) -> MARK(T) 66.76/18.02 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.02 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.02 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.02 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.02 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.02 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.02 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.02 MARK(s(X)) -> MARK(X) 66.76/18.02 66.76/18.02 The TRS R consists of the following rules: 66.76/18.02 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 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) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__zeros -> zeros 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 66.76/18.02 The set Q consists of the following terms: 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.02 a__uTake1(x0) 66.76/18.02 a__uTake2(x0, x1, x2, x3) 66.76/18.02 a__uLength(x0, x1) 66.76/18.02 66.76/18.02 We have to consider all minimal (P,Q,R)-chains. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (25) QDPOrderProof (EQUIVALENT) 66.76/18.02 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.02 66.76/18.02 66.76/18.02 The following pairs can be oriented strictly and are deleted. 66.76/18.02 66.76/18.02 A__ISNAT(length(L)) -> A__ISNATLIST(L) 66.76/18.02 The remaining pairs can at least be oriented weakly. 66.76/18.02 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.02 66.76/18.02 POL( A__AND_2(x_1, x_2) ) = x_2 + 2 66.76/18.02 POL( mark_1(x_1) ) = x_1 66.76/18.02 POL( and_2(x_1, x_2) ) = x_1 + x_2 66.76/18.02 POL( a__and_2(x_1, x_2) ) = x_1 + x_2 66.76/18.02 POL( tt ) = 0 66.76/18.02 POL( isNatIList_1(x_1) ) = 2x_1 66.76/18.02 POL( a__isNatIList_1(x_1) ) = 2x_1 66.76/18.02 POL( a__isNatList_1(x_1) ) = x_1 66.76/18.02 POL( cons_2(x_1, x_2) ) = x_1 + x_2 66.76/18.02 POL( a__isNat_1(x_1) ) = x_1 66.76/18.02 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 66.76/18.02 POL( isNatList_1(x_1) ) = x_1 66.76/18.02 POL( isNat_1(x_1) ) = x_1 66.76/18.02 POL( s_1(x_1) ) = x_1 66.76/18.02 POL( length_1(x_1) ) = x_1 + 1 66.76/18.02 POL( a__length_1(x_1) ) = x_1 + 1 66.76/18.02 POL( zeros ) = 0 66.76/18.02 POL( a__zeros ) = 0 66.76/18.02 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 66.76/18.02 POL( uTake1_1(x_1) ) = 0 66.76/18.02 POL( a__uTake1_1(x_1) ) = max{0, -2} 66.76/18.02 POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 66.76/18.02 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 66.76/18.02 POL( uLength_2(x_1, x_2) ) = x_2 + 1 66.76/18.02 POL( a__uLength_2(x_1, x_2) ) = x_2 + 1 66.76/18.02 POL( 0 ) = 0 66.76/18.02 POL( nil ) = 0 66.76/18.02 POL( MARK_1(x_1) ) = x_1 + 2 66.76/18.02 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 66.76/18.02 POL( A__ISNATLIST_1(x_1) ) = x_1 + 2 66.76/18.02 POL( A__ISNAT_1(x_1) ) = x_1 + 2 66.76/18.02 66.76/18.02 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.02 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 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) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__zeros -> zeros 66.76/18.02 66.76/18.02 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (26) 66.76/18.02 Obligation: 66.76/18.02 Q DP problem: 66.76/18.02 The TRS P consists of the following rules: 66.76/18.02 66.76/18.02 A__AND(tt, T) -> MARK(T) 66.76/18.02 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.02 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.02 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.02 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNAT(N) 66.76/18.02 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.02 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNAT(N) 66.76/18.02 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.02 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.02 MARK(isNat(X)) -> A__ISNAT(X) 66.76/18.02 MARK(s(X)) -> MARK(X) 66.76/18.02 66.76/18.02 The TRS R consists of the following rules: 66.76/18.02 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 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) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__zeros -> zeros 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 66.76/18.02 The set Q consists of the following terms: 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.02 a__uTake1(x0) 66.76/18.02 a__uTake2(x0, x1, x2, x3) 66.76/18.02 a__uLength(x0, x1) 66.76/18.02 66.76/18.02 We have to consider all minimal (P,Q,R)-chains. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (27) DependencyGraphProof (EQUIVALENT) 66.76/18.02 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (28) 66.76/18.02 Complex Obligation (AND) 66.76/18.02 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (29) 66.76/18.02 Obligation: 66.76/18.02 Q DP problem: 66.76/18.02 The TRS P consists of the following rules: 66.76/18.02 66.76/18.02 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.02 66.76/18.02 The TRS R consists of the following rules: 66.76/18.02 66.76/18.02 a__and(tt, T) -> mark(T) 66.76/18.02 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.02 a__isNat(0) -> tt 66.76/18.02 a__isNat(s(N)) -> a__isNat(N) 66.76/18.02 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.02 a__isNatIList(zeros) -> tt 66.76/18.02 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__isNatList(nil) -> tt 66.76/18.02 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.02 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.02 a__zeros -> cons(0, zeros) 66.76/18.02 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.02 a__uTake1(tt) -> nil 66.76/18.02 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) 66.76/18.02 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.02 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.02 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.02 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.02 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.02 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.02 mark(isNat(X)) -> a__isNat(X) 66.76/18.02 mark(length(X)) -> a__length(mark(X)) 66.76/18.02 mark(zeros) -> a__zeros 66.76/18.02 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.02 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.02 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.02 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.02 mark(tt) -> tt 66.76/18.02 mark(0) -> 0 66.76/18.02 mark(s(X)) -> s(mark(X)) 66.76/18.02 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.02 mark(nil) -> nil 66.76/18.02 a__and(X1, X2) -> and(X1, X2) 66.76/18.02 a__isNatIList(X) -> isNatIList(X) 66.76/18.02 a__isNatList(X) -> isNatList(X) 66.76/18.02 a__isNat(X) -> isNat(X) 66.76/18.02 a__length(X) -> length(X) 66.76/18.02 a__zeros -> zeros 66.76/18.02 a__take(X1, X2) -> take(X1, X2) 66.76/18.02 a__uTake1(X) -> uTake1(X) 66.76/18.02 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.02 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.02 66.76/18.02 The set Q consists of the following terms: 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.02 a__uTake1(x0) 66.76/18.02 a__uTake2(x0, x1, x2, x3) 66.76/18.02 a__uLength(x0, x1) 66.76/18.02 66.76/18.02 We have to consider all minimal (P,Q,R)-chains. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (30) UsableRulesProof (EQUIVALENT) 66.76/18.02 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (31) 66.76/18.02 Obligation: 66.76/18.02 Q DP problem: 66.76/18.02 The TRS P consists of the following rules: 66.76/18.02 66.76/18.02 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.02 66.76/18.02 R is empty. 66.76/18.02 The set Q consists of the following terms: 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.02 a__uTake1(x0) 66.76/18.02 a__uTake2(x0, x1, x2, x3) 66.76/18.02 a__uLength(x0, x1) 66.76/18.02 66.76/18.02 We have to consider all minimal (P,Q,R)-chains. 66.76/18.02 ---------------------------------------- 66.76/18.02 66.76/18.02 (32) QReductionProof (EQUIVALENT) 66.76/18.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 66.76/18.02 66.76/18.02 a__isNatIList(x0) 66.76/18.02 a__zeros 66.76/18.02 mark(and(x0, x1)) 66.76/18.02 mark(isNatIList(x0)) 66.76/18.02 mark(isNatList(x0)) 66.76/18.02 mark(isNat(x0)) 66.76/18.02 mark(length(x0)) 66.76/18.02 mark(zeros) 66.76/18.02 mark(take(x0, x1)) 66.76/18.02 mark(uTake1(x0)) 66.76/18.02 mark(uTake2(x0, x1, x2, x3)) 66.76/18.02 mark(uLength(x0, x1)) 66.76/18.02 mark(tt) 66.76/18.02 mark(0) 66.76/18.02 mark(s(x0)) 66.76/18.02 mark(cons(x0, x1)) 66.76/18.02 mark(nil) 66.76/18.02 a__and(x0, x1) 66.76/18.02 a__isNatList(x0) 66.76/18.02 a__isNat(x0) 66.76/18.02 a__length(x0) 66.76/18.02 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (33) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.04 66.76/18.04 R is empty. 66.76/18.04 Q is empty. 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (34) QDPSizeChangeProof (EQUIVALENT) 66.76/18.04 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. 66.76/18.04 66.76/18.04 From the DPs we obtained the following set of size-change graphs: 66.76/18.04 *A__ISNAT(s(N)) -> A__ISNAT(N) 66.76/18.04 The graph contains the following edges 1 > 1 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (35) 66.76/18.04 YES 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (36) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.04 a__uTake1(tt) -> nil 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (37) QDPOrderProof (EQUIVALENT) 66.76/18.04 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.04 66.76/18.04 66.76/18.04 The following pairs can be oriented strictly and are deleted. 66.76/18.04 66.76/18.04 A__ISNATILIST(IL) -> A__ISNATLIST(IL) 66.76/18.04 The remaining pairs can at least be oriented weakly. 66.76/18.04 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.04 66.76/18.04 POL( A__AND_2(x_1, x_2) ) = x_2 66.76/18.04 POL( mark_1(x_1) ) = x_1 66.76/18.04 POL( and_2(x_1, x_2) ) = x_1 + x_2 66.76/18.04 POL( a__and_2(x_1, x_2) ) = x_1 + x_2 66.76/18.04 POL( tt ) = 0 66.76/18.04 POL( isNatIList_1(x_1) ) = 2x_1 + 2 66.76/18.04 POL( a__isNatIList_1(x_1) ) = 2x_1 + 2 66.76/18.04 POL( a__isNatList_1(x_1) ) = x_1 66.76/18.04 POL( cons_2(x_1, x_2) ) = 2x_1 + x_2 66.76/18.04 POL( a__isNat_1(x_1) ) = 2x_1 66.76/18.04 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 66.76/18.04 POL( isNatList_1(x_1) ) = x_1 66.76/18.04 POL( isNat_1(x_1) ) = 2x_1 66.76/18.04 POL( s_1(x_1) ) = x_1 66.76/18.04 POL( length_1(x_1) ) = 2x_1 66.76/18.04 POL( a__length_1(x_1) ) = 2x_1 66.76/18.04 POL( zeros ) = 0 66.76/18.04 POL( a__zeros ) = 0 66.76/18.04 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 66.76/18.04 POL( uTake1_1(x_1) ) = 0 66.76/18.04 POL( a__uTake1_1(x_1) ) = max{0, -2} 66.76/18.04 POL( uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 66.76/18.04 POL( a__uTake2_4(x_1, ..., x_4) ) = 2x_2 + 2x_3 + 2x_4 + 2 66.76/18.04 POL( uLength_2(x_1, x_2) ) = 2x_2 66.76/18.04 POL( a__uLength_2(x_1, x_2) ) = 2x_2 66.76/18.04 POL( 0 ) = 0 66.76/18.04 POL( nil ) = 0 66.76/18.04 POL( MARK_1(x_1) ) = x_1 66.76/18.04 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 66.76/18.04 POL( A__ISNATLIST_1(x_1) ) = x_1 66.76/18.04 66.76/18.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.04 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(tt) -> nil 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.04 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) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__zeros -> zeros 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (38) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.04 a__uTake1(tt) -> nil 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (39) QDPQMonotonicMRRProof (EQUIVALENT) 66.76/18.04 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 66.76/18.04 66.76/18.04 66.76/18.04 Strictly oriented rules of the TRS R: 66.76/18.04 66.76/18.04 a__uTake1(tt) -> nil 66.76/18.04 66.76/18.04 Used ordering: Polynomial interpretation [POLO]: 66.76/18.04 66.76/18.04 POL(0) = 0 66.76/18.04 POL(A__AND(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.04 POL(A__ISNATILIST(x_1)) = 0 66.76/18.04 POL(A__ISNATLIST(x_1)) = 0 66.76/18.04 POL(MARK(x_1)) = 2*x_1 66.76/18.04 POL(a__and(x_1, x_2)) = 2*x_1 + x_2 66.76/18.04 POL(a__isNat(x_1)) = 0 66.76/18.04 POL(a__isNatIList(x_1)) = 0 66.76/18.04 POL(a__isNatList(x_1)) = 0 66.76/18.04 POL(a__length(x_1)) = 2*x_1 66.76/18.04 POL(a__take(x_1, x_2)) = 2 + 2*x_1 + x_2 66.76/18.04 POL(a__uLength(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.04 POL(a__uTake1(x_1)) = 2 + 2*x_1 66.76/18.04 POL(a__uTake2(x_1, x_2, x_3, x_4)) = 2 + x_1 + 2*x_2 + x_3 + x_4 66.76/18.04 POL(a__zeros) = 0 66.76/18.04 POL(and(x_1, x_2)) = 2*x_1 + x_2 66.76/18.04 POL(cons(x_1, x_2)) = x_1 + x_2 66.76/18.04 POL(isNat(x_1)) = 0 66.76/18.04 POL(isNatIList(x_1)) = 0 66.76/18.04 POL(isNatList(x_1)) = 0 66.76/18.04 POL(length(x_1)) = 2*x_1 66.76/18.04 POL(mark(x_1)) = x_1 66.76/18.04 POL(nil) = 0 66.76/18.04 POL(s(x_1)) = x_1 66.76/18.04 POL(take(x_1, x_2)) = 2 + 2*x_1 + x_2 66.76/18.04 POL(tt) = 0 66.76/18.04 POL(uLength(x_1, x_2)) = 2*x_1 + 2*x_2 66.76/18.04 POL(uTake1(x_1)) = 2 + 2*x_1 66.76/18.04 POL(uTake2(x_1, x_2, x_3, x_4)) = 2 + x_1 + 2*x_2 + x_3 + x_4 66.76/18.04 POL(zeros) = 0 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (40) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (41) QDPQMonotonicMRRProof (EQUIVALENT) 66.76/18.04 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 66.76/18.04 66.76/18.04 66.76/18.04 Strictly oriented rules of the TRS R: 66.76/18.04 66.76/18.04 a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) 66.76/18.04 66.76/18.04 Used ordering: Polynomial interpretation [POLO]: 66.76/18.04 66.76/18.04 POL(0) = 0 66.76/18.04 POL(A__AND(x_1, x_2)) = x_1 + x_2 66.76/18.04 POL(A__ISNATILIST(x_1)) = 0 66.76/18.04 POL(A__ISNATLIST(x_1)) = 0 66.76/18.04 POL(MARK(x_1)) = x_1 66.76/18.04 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 66.76/18.04 POL(a__isNat(x_1)) = 0 66.76/18.04 POL(a__isNatIList(x_1)) = 0 66.76/18.04 POL(a__isNatList(x_1)) = 0 66.76/18.04 POL(a__length(x_1)) = x_1 66.76/18.04 POL(a__take(x_1, x_2)) = 2 + x_1 + x_2 66.76/18.04 POL(a__uLength(x_1, x_2)) = x_1 + x_2 66.76/18.04 POL(a__uTake1(x_1)) = 2*x_1 66.76/18.04 POL(a__uTake2(x_1, x_2, x_3, x_4)) = 2 + 2*x_1 + x_2 + x_3 + x_4 66.76/18.04 POL(a__zeros) = 0 66.76/18.04 POL(and(x_1, x_2)) = x_1 + 2*x_2 66.76/18.04 POL(cons(x_1, x_2)) = x_1 + x_2 66.76/18.04 POL(isNat(x_1)) = 0 66.76/18.04 POL(isNatIList(x_1)) = 0 66.76/18.04 POL(isNatList(x_1)) = 0 66.76/18.04 POL(length(x_1)) = x_1 66.76/18.04 POL(mark(x_1)) = x_1 66.76/18.04 POL(nil) = 0 66.76/18.04 POL(s(x_1)) = x_1 66.76/18.04 POL(take(x_1, x_2)) = 2 + x_1 + x_2 66.76/18.04 POL(tt) = 0 66.76/18.04 POL(uLength(x_1, x_2)) = x_1 + x_2 66.76/18.04 POL(uTake1(x_1)) = 2*x_1 66.76/18.04 POL(uTake2(x_1, x_2, x_3, x_4)) = 2 + 2*x_1 + x_2 + x_3 + x_4 66.76/18.04 POL(zeros) = 0 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (42) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (43) QDPOrderProof (EQUIVALENT) 66.76/18.04 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.04 66.76/18.04 66.76/18.04 The following pairs can be oriented strictly and are deleted. 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> MARK(X1) 66.76/18.04 The remaining pairs can at least be oriented weakly. 66.76/18.04 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(and(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(A__AND(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(tt) = [[0A]] 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(isNatIList(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(A__ISNATILIST(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(A__ISNATLIST(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(cons(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__isNat(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__isNatList(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__isNatIList(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(isNatList(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__and(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(take(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(isNat(x_1)) = [[-I]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(length(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__length(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(zeros) = [[2A]] 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__zeros) = [[2A]] 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__take(x_1, x_2)) = [[0A]] + [[1A]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(uTake1(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__uTake1(x_1)) = [[0A]] + [[0A]] * x_1 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(uTake2(x_1, x_2, x_3, x_4)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 + [[0A]] * x_4 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__uTake2(x_1, x_2, x_3, x_4)) = [[-I]] + [[0A]] * x_1 + [[1A]] * x_2 + [[1A]] * x_3 + [[0A]] * x_4 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(uLength(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(a__uLength(x_1, x_2)) = [[0A]] + [[-I]] * x_1 + [[0A]] * x_2 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(0) = [[1A]] 66.76/18.04 >>> 66.76/18.04 66.76/18.04 <<< 66.76/18.04 POL(nil) = [[0A]] 66.76/18.04 >>> 66.76/18.04 66.76/18.04 66.76/18.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.04 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 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) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__zeros -> zeros 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (44) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (45) QDPOrderProof (EQUIVALENT) 66.76/18.04 We use the reduction pair processor [LPAR04,JAR06]. 66.76/18.04 66.76/18.04 66.76/18.04 The following pairs can be oriented strictly and are deleted. 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> MARK(X2) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__ISNATLIST(L) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__AND(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 A__ISNATILIST(cons(N, IL)) -> A__ISNATILIST(IL) 66.76/18.04 MARK(isNatList(X)) -> A__ISNATLIST(X) 66.76/18.04 The remaining pairs can at least be oriented weakly. 66.76/18.04 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 66.76/18.04 66.76/18.04 POL( A__AND_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( mark_1(x_1) ) = x_1 + 1 66.76/18.04 POL( and_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( a__and_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( tt ) = 0 66.76/18.04 POL( isNatIList_1(x_1) ) = x_1 66.76/18.04 POL( a__isNatIList_1(x_1) ) = x_1 66.76/18.04 POL( a__isNatList_1(x_1) ) = x_1 66.76/18.04 POL( cons_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( a__isNat_1(x_1) ) = 2x_1 66.76/18.04 POL( take_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( isNatList_1(x_1) ) = x_1 66.76/18.04 POL( isNat_1(x_1) ) = 2x_1 66.76/18.04 POL( s_1(x_1) ) = x_1 66.76/18.04 POL( length_1(x_1) ) = x_1 66.76/18.04 POL( a__length_1(x_1) ) = x_1 66.76/18.04 POL( zeros ) = 0 66.76/18.04 POL( a__zeros ) = 1 66.76/18.04 POL( a__take_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( uTake1_1(x_1) ) = 1 66.76/18.04 POL( a__uTake1_1(x_1) ) = 2 66.76/18.04 POL( uTake2_4(x_1, ..., x_4) ) = x_4 + 1 66.76/18.04 POL( a__uTake2_4(x_1, ..., x_4) ) = x_4 + 2 66.76/18.04 POL( uLength_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( a__uLength_2(x_1, x_2) ) = x_2 + 1 66.76/18.04 POL( 0 ) = 0 66.76/18.04 POL( nil ) = 0 66.76/18.04 POL( MARK_1(x_1) ) = x_1 + 1 66.76/18.04 POL( A__ISNATILIST_1(x_1) ) = x_1 + 1 66.76/18.04 POL( A__ISNATLIST_1(x_1) ) = x_1 66.76/18.04 66.76/18.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 66.76/18.04 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 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) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 a__zeros -> zeros 66.76/18.04 66.76/18.04 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (46) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(isNatIList(X)) -> A__ISNATILIST(X) 66.76/18.04 A__ISNATLIST(cons(N, L)) -> A__AND(a__isNat(N), a__isNatList(L)) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.04 66.76/18.04 The set Q consists of the following terms: 66.76/18.04 66.76/18.04 a__isNatIList(x0) 66.76/18.04 a__zeros 66.76/18.04 mark(and(x0, x1)) 66.76/18.04 mark(isNatIList(x0)) 66.76/18.04 mark(isNatList(x0)) 66.76/18.04 mark(isNat(x0)) 66.76/18.04 mark(length(x0)) 66.76/18.04 mark(zeros) 66.76/18.04 mark(take(x0, x1)) 66.76/18.04 mark(uTake1(x0)) 66.76/18.04 mark(uTake2(x0, x1, x2, x3)) 66.76/18.04 mark(uLength(x0, x1)) 66.76/18.04 mark(tt) 66.76/18.04 mark(0) 66.76/18.04 mark(s(x0)) 66.76/18.04 mark(cons(x0, x1)) 66.76/18.04 mark(nil) 66.76/18.04 a__and(x0, x1) 66.76/18.04 a__isNatList(x0) 66.76/18.04 a__isNat(x0) 66.76/18.04 a__length(x0) 66.76/18.04 a__take(x0, x1) 66.76/18.04 a__uTake1(x0) 66.76/18.04 a__uTake2(x0, x1, x2, x3) 66.76/18.04 a__uLength(x0, x1) 66.76/18.04 66.76/18.04 We have to consider all minimal (P,Q,R)-chains. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (47) DependencyGraphProof (EQUIVALENT) 66.76/18.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 66.76/18.04 ---------------------------------------- 66.76/18.04 66.76/18.04 (48) 66.76/18.04 Obligation: 66.76/18.04 Q DP problem: 66.76/18.04 The TRS P consists of the following rules: 66.76/18.04 66.76/18.04 A__AND(tt, T) -> MARK(T) 66.76/18.04 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.04 MARK(s(X)) -> MARK(X) 66.76/18.04 66.76/18.04 The TRS R consists of the following rules: 66.76/18.04 66.76/18.04 a__and(tt, T) -> mark(T) 66.76/18.04 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.04 a__isNat(0) -> tt 66.76/18.04 a__isNat(s(N)) -> a__isNat(N) 66.76/18.04 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.04 a__isNatIList(zeros) -> tt 66.76/18.04 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__isNatList(nil) -> tt 66.76/18.04 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.04 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.04 a__zeros -> cons(0, zeros) 66.76/18.04 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) 66.76/18.04 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.04 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.04 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.04 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.04 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.04 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.04 mark(isNat(X)) -> a__isNat(X) 66.76/18.04 mark(length(X)) -> a__length(mark(X)) 66.76/18.04 mark(zeros) -> a__zeros 66.76/18.04 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.04 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.04 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.04 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.04 mark(tt) -> tt 66.76/18.04 mark(0) -> 0 66.76/18.04 mark(s(X)) -> s(mark(X)) 66.76/18.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.04 mark(nil) -> nil 66.76/18.04 a__and(X1, X2) -> and(X1, X2) 66.76/18.04 a__isNatIList(X) -> isNatIList(X) 66.76/18.04 a__isNatList(X) -> isNatList(X) 66.76/18.04 a__isNat(X) -> isNat(X) 66.76/18.04 a__length(X) -> length(X) 66.76/18.04 a__zeros -> zeros 66.76/18.04 a__take(X1, X2) -> take(X1, X2) 66.76/18.04 a__uTake1(X) -> uTake1(X) 66.76/18.04 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.04 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.05 66.76/18.05 The set Q consists of the following terms: 66.76/18.05 66.76/18.05 a__isNatIList(x0) 66.76/18.05 a__zeros 66.76/18.05 mark(and(x0, x1)) 66.76/18.05 mark(isNatIList(x0)) 66.76/18.05 mark(isNatList(x0)) 66.76/18.05 mark(isNat(x0)) 66.76/18.05 mark(length(x0)) 66.76/18.05 mark(zeros) 66.76/18.05 mark(take(x0, x1)) 66.76/18.05 mark(uTake1(x0)) 66.76/18.05 mark(uTake2(x0, x1, x2, x3)) 66.76/18.05 mark(uLength(x0, x1)) 66.76/18.05 mark(tt) 66.76/18.05 mark(0) 66.76/18.05 mark(s(x0)) 66.76/18.05 mark(cons(x0, x1)) 66.76/18.05 mark(nil) 66.76/18.05 a__and(x0, x1) 66.76/18.05 a__isNatList(x0) 66.76/18.05 a__isNat(x0) 66.76/18.05 a__length(x0) 66.76/18.05 a__take(x0, x1) 66.76/18.05 a__uTake1(x0) 66.76/18.05 a__uTake2(x0, x1, x2, x3) 66.76/18.05 a__uLength(x0, x1) 66.76/18.05 66.76/18.05 We have to consider all minimal (P,Q,R)-chains. 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (49) QDPQMonotonicMRRProof (EQUIVALENT) 66.76/18.05 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 66.76/18.05 66.76/18.05 Strictly oriented dependency pairs: 66.76/18.05 66.76/18.05 A__AND(tt, T) -> MARK(T) 66.76/18.05 MARK(and(X1, X2)) -> A__AND(mark(X1), mark(X2)) 66.76/18.05 66.76/18.05 66.76/18.05 Used ordering: Polynomial interpretation [POLO]: 66.76/18.05 66.76/18.05 POL(0) = 2 66.76/18.05 POL(A__AND(x_1, x_2)) = 1 + 2*x_2 66.76/18.05 POL(MARK(x_1)) = 2*x_1 66.76/18.05 POL(a__and(x_1, x_2)) = 2 + x_2 66.76/18.05 POL(a__isNat(x_1)) = 2*x_1 66.76/18.05 POL(a__isNatIList(x_1)) = 2*x_1 66.76/18.05 POL(a__isNatList(x_1)) = 2*x_1 66.76/18.05 POL(a__length(x_1)) = x_1 66.76/18.05 POL(a__take(x_1, x_2)) = 1 + x_2 66.76/18.05 POL(a__uLength(x_1, x_2)) = 1 + x_2 66.76/18.05 POL(a__uTake1(x_1)) = 2 66.76/18.05 POL(a__uTake2(x_1, x_2, x_3, x_4)) = 2 + x_4 66.76/18.05 POL(a__zeros) = 1 66.76/18.05 POL(and(x_1, x_2)) = 2 + x_2 66.76/18.05 POL(cons(x_1, x_2)) = 1 + x_2 66.76/18.05 POL(isNat(x_1)) = 2*x_1 66.76/18.05 POL(isNatIList(x_1)) = 2*x_1 66.76/18.05 POL(isNatList(x_1)) = 2*x_1 66.76/18.05 POL(length(x_1)) = x_1 66.76/18.05 POL(mark(x_1)) = 1 + x_1 66.76/18.05 POL(nil) = 2 66.76/18.05 POL(s(x_1)) = x_1 66.76/18.05 POL(take(x_1, x_2)) = 1 + x_2 66.76/18.05 POL(tt) = 0 66.76/18.05 POL(uLength(x_1, x_2)) = 1 + x_2 66.76/18.05 POL(uTake1(x_1)) = 1 66.76/18.05 POL(uTake2(x_1, x_2, x_3, x_4)) = 1 + x_4 66.76/18.05 POL(zeros) = 0 66.76/18.05 66.76/18.05 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (50) 66.76/18.05 Obligation: 66.76/18.05 Q DP problem: 66.76/18.05 The TRS P consists of the following rules: 66.76/18.05 66.76/18.05 MARK(s(X)) -> MARK(X) 66.76/18.05 66.76/18.05 The TRS R consists of the following rules: 66.76/18.05 66.76/18.05 a__and(tt, T) -> mark(T) 66.76/18.05 a__isNatIList(IL) -> a__isNatList(IL) 66.76/18.05 a__isNat(0) -> tt 66.76/18.05 a__isNat(s(N)) -> a__isNat(N) 66.76/18.05 a__isNat(length(L)) -> a__isNatList(L) 66.76/18.05 a__isNatIList(zeros) -> tt 66.76/18.05 a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.05 a__isNatList(nil) -> tt 66.76/18.05 a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) 66.76/18.05 a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) 66.76/18.05 a__zeros -> cons(0, zeros) 66.76/18.05 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) 66.76/18.05 a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) 66.76/18.05 a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) 66.76/18.05 a__uLength(tt, L) -> s(a__length(mark(L))) 66.76/18.05 mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) 66.76/18.05 mark(isNatIList(X)) -> a__isNatIList(X) 66.76/18.05 mark(isNatList(X)) -> a__isNatList(X) 66.76/18.05 mark(isNat(X)) -> a__isNat(X) 66.76/18.05 mark(length(X)) -> a__length(mark(X)) 66.76/18.05 mark(zeros) -> a__zeros 66.76/18.05 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 66.76/18.05 mark(uTake1(X)) -> a__uTake1(mark(X)) 66.76/18.05 mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) 66.76/18.05 mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) 66.76/18.05 mark(tt) -> tt 66.76/18.05 mark(0) -> 0 66.76/18.05 mark(s(X)) -> s(mark(X)) 66.76/18.05 mark(cons(X1, X2)) -> cons(mark(X1), X2) 66.76/18.05 mark(nil) -> nil 66.76/18.05 a__and(X1, X2) -> and(X1, X2) 66.76/18.05 a__isNatIList(X) -> isNatIList(X) 66.76/18.05 a__isNatList(X) -> isNatList(X) 66.76/18.05 a__isNat(X) -> isNat(X) 66.76/18.05 a__length(X) -> length(X) 66.76/18.05 a__zeros -> zeros 66.76/18.05 a__take(X1, X2) -> take(X1, X2) 66.76/18.05 a__uTake1(X) -> uTake1(X) 66.76/18.05 a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) 66.76/18.05 a__uLength(X1, X2) -> uLength(X1, X2) 66.76/18.05 66.76/18.05 The set Q consists of the following terms: 66.76/18.05 66.76/18.05 a__isNatIList(x0) 66.76/18.05 a__zeros 66.76/18.05 mark(and(x0, x1)) 66.76/18.05 mark(isNatIList(x0)) 66.76/18.05 mark(isNatList(x0)) 66.76/18.05 mark(isNat(x0)) 66.76/18.05 mark(length(x0)) 66.76/18.05 mark(zeros) 66.76/18.05 mark(take(x0, x1)) 66.76/18.05 mark(uTake1(x0)) 66.76/18.05 mark(uTake2(x0, x1, x2, x3)) 66.76/18.05 mark(uLength(x0, x1)) 66.76/18.05 mark(tt) 66.76/18.05 mark(0) 66.76/18.05 mark(s(x0)) 66.76/18.05 mark(cons(x0, x1)) 66.76/18.05 mark(nil) 66.76/18.05 a__and(x0, x1) 66.76/18.05 a__isNatList(x0) 66.76/18.05 a__isNat(x0) 66.76/18.05 a__length(x0) 66.76/18.05 a__take(x0, x1) 66.76/18.05 a__uTake1(x0) 66.76/18.05 a__uTake2(x0, x1, x2, x3) 66.76/18.05 a__uLength(x0, x1) 66.76/18.05 66.76/18.05 We have to consider all minimal (P,Q,R)-chains. 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (51) UsableRulesProof (EQUIVALENT) 66.76/18.05 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (52) 66.76/18.05 Obligation: 66.76/18.05 Q DP problem: 66.76/18.05 The TRS P consists of the following rules: 66.76/18.05 66.76/18.05 MARK(s(X)) -> MARK(X) 66.76/18.05 66.76/18.05 R is empty. 66.76/18.05 The set Q consists of the following terms: 66.76/18.05 66.76/18.05 a__isNatIList(x0) 66.76/18.05 a__zeros 66.76/18.05 mark(and(x0, x1)) 66.76/18.05 mark(isNatIList(x0)) 66.76/18.05 mark(isNatList(x0)) 66.76/18.05 mark(isNat(x0)) 66.76/18.05 mark(length(x0)) 66.76/18.05 mark(zeros) 66.76/18.05 mark(take(x0, x1)) 66.76/18.05 mark(uTake1(x0)) 66.76/18.05 mark(uTake2(x0, x1, x2, x3)) 66.76/18.05 mark(uLength(x0, x1)) 66.76/18.05 mark(tt) 66.76/18.05 mark(0) 66.76/18.05 mark(s(x0)) 66.76/18.05 mark(cons(x0, x1)) 66.76/18.05 mark(nil) 66.76/18.05 a__and(x0, x1) 66.76/18.05 a__isNatList(x0) 66.76/18.05 a__isNat(x0) 66.76/18.05 a__length(x0) 66.76/18.05 a__take(x0, x1) 66.76/18.05 a__uTake1(x0) 66.76/18.05 a__uTake2(x0, x1, x2, x3) 66.76/18.05 a__uLength(x0, x1) 66.76/18.05 66.76/18.05 We have to consider all minimal (P,Q,R)-chains. 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (53) QReductionProof (EQUIVALENT) 66.76/18.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 66.76/18.05 66.76/18.05 a__isNatIList(x0) 66.76/18.05 a__zeros 66.76/18.05 mark(and(x0, x1)) 66.76/18.05 mark(isNatIList(x0)) 66.76/18.05 mark(isNatList(x0)) 66.76/18.05 mark(isNat(x0)) 66.76/18.05 mark(length(x0)) 66.76/18.05 mark(zeros) 66.76/18.05 mark(take(x0, x1)) 66.76/18.05 mark(uTake1(x0)) 66.76/18.05 mark(uTake2(x0, x1, x2, x3)) 66.76/18.05 mark(uLength(x0, x1)) 66.76/18.05 mark(tt) 66.76/18.05 mark(0) 66.76/18.05 mark(s(x0)) 66.76/18.05 mark(cons(x0, x1)) 66.76/18.05 mark(nil) 66.76/18.05 a__and(x0, x1) 66.76/18.05 a__isNatList(x0) 66.76/18.05 a__isNat(x0) 66.76/18.05 a__length(x0) 66.76/18.05 a__take(x0, x1) 66.76/18.05 a__uTake1(x0) 66.76/18.05 a__uTake2(x0, x1, x2, x3) 66.76/18.05 a__uLength(x0, x1) 66.76/18.05 66.76/18.05 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (54) 66.76/18.05 Obligation: 66.76/18.05 Q DP problem: 66.76/18.05 The TRS P consists of the following rules: 66.76/18.05 66.76/18.05 MARK(s(X)) -> MARK(X) 66.76/18.05 66.76/18.05 R is empty. 66.76/18.05 Q is empty. 66.76/18.05 We have to consider all minimal (P,Q,R)-chains. 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (55) QDPSizeChangeProof (EQUIVALENT) 66.76/18.05 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. 66.76/18.05 66.76/18.05 From the DPs we obtained the following set of size-change graphs: 66.76/18.05 *MARK(s(X)) -> MARK(X) 66.76/18.05 The graph contains the following edges 1 > 1 66.76/18.05 66.76/18.05 66.76/18.05 ---------------------------------------- 66.76/18.05 66.76/18.05 (56) 66.76/18.05 YES 67.03/18.13 EOF