25.16/7.59 YES 34.93/10.06 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 34.93/10.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 34.93/10.06 34.93/10.06 34.93/10.06 Termination w.r.t. Q of the given QTRS could be proven: 34.93/10.06 34.93/10.06 (0) QTRS 34.93/10.06 (1) DependencyPairsProof [EQUIVALENT, 70 ms] 34.93/10.06 (2) QDP 34.93/10.06 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 34.93/10.06 (4) AND 34.93/10.06 (5) QDP 34.93/10.06 (6) UsableRulesProof [EQUIVALENT, 0 ms] 34.93/10.06 (7) QDP 34.93/10.06 (8) QReductionProof [EQUIVALENT, 7 ms] 34.93/10.06 (9) QDP 34.93/10.06 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 34.93/10.06 (11) YES 34.93/10.06 (12) QDP 34.93/10.06 (13) QDPOrderProof [EQUIVALENT, 338 ms] 34.93/10.06 (14) QDP 34.93/10.06 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 34.93/10.06 (16) AND 34.93/10.06 (17) QDP 34.93/10.06 (18) QDPOrderProof [EQUIVALENT, 131 ms] 34.93/10.06 (19) QDP 34.93/10.06 (20) DependencyGraphProof [EQUIVALENT, 0 ms] 34.93/10.06 (21) QDP 34.93/10.06 (22) UsableRulesProof [EQUIVALENT, 0 ms] 34.93/10.06 (23) QDP 34.93/10.06 (24) QReductionProof [EQUIVALENT, 0 ms] 34.93/10.06 (25) QDP 34.93/10.07 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 34.93/10.07 (27) YES 34.93/10.07 (28) QDP 34.93/10.07 (29) QDPQMonotonicMRRProof [EQUIVALENT, 77 ms] 34.93/10.07 (30) QDP 34.93/10.07 (31) QDPQMonotonicMRRProof [EQUIVALENT, 199 ms] 34.93/10.07 (32) QDP 34.93/10.07 (33) QDPOrderProof [EQUIVALENT, 81 ms] 34.93/10.07 (34) QDP 34.93/10.07 (35) DependencyGraphProof [EQUIVALENT, 0 ms] 34.93/10.07 (36) TRUE 34.93/10.07 34.93/10.07 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (0) 34.93/10.07 Obligation: 34.93/10.07 Q restricted rewrite system: 34.93/10.07 The TRS R consists of the following rules: 34.93/10.07 34.93/10.07 a__zeros -> cons(0, zeros) 34.93/10.07 a__U11(tt) -> tt 34.93/10.07 a__U21(tt) -> tt 34.93/10.07 a__U31(tt) -> tt 34.93/10.07 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.07 a__U42(tt) -> tt 34.93/10.07 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.07 a__U52(tt) -> tt 34.93/10.07 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.07 a__U62(tt) -> tt 34.93/10.07 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.07 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.07 a__U81(tt) -> nil 34.93/10.07 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.07 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.07 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.07 a__isNat(0) -> tt 34.93/10.07 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.07 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.07 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.07 a__isNatIList(zeros) -> tt 34.93/10.07 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.07 a__isNatList(nil) -> tt 34.93/10.07 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.07 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.07 a__length(nil) -> 0 34.93/10.07 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.07 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.07 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.07 mark(zeros) -> a__zeros 34.93/10.07 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.07 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.07 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.07 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.07 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.07 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.07 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.07 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.07 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.07 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.07 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.07 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.07 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.07 mark(isNat(X)) -> a__isNat(X) 34.93/10.07 mark(length(X)) -> a__length(mark(X)) 34.93/10.07 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.07 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.07 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.07 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.07 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.07 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.07 mark(0) -> 0 34.93/10.07 mark(tt) -> tt 34.93/10.07 mark(s(X)) -> s(mark(X)) 34.93/10.07 mark(nil) -> nil 34.93/10.07 a__zeros -> zeros 34.93/10.07 a__U11(X) -> U11(X) 34.93/10.07 a__U21(X) -> U21(X) 34.93/10.07 a__U31(X) -> U31(X) 34.93/10.07 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.07 a__U42(X) -> U42(X) 34.93/10.07 a__isNatIList(X) -> isNatIList(X) 34.93/10.07 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.07 a__U52(X) -> U52(X) 34.93/10.07 a__isNatList(X) -> isNatList(X) 34.93/10.07 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.07 a__U62(X) -> U62(X) 34.93/10.07 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.07 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.07 a__isNat(X) -> isNat(X) 34.93/10.07 a__length(X) -> length(X) 34.93/10.07 a__U81(X) -> U81(X) 34.93/10.07 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.07 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.07 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.07 a__take(X1, X2) -> take(X1, X2) 34.93/10.07 34.93/10.07 The set Q consists of the following terms: 34.93/10.07 34.93/10.07 a__zeros 34.93/10.07 a__isNatIList(x0) 34.93/10.07 mark(zeros) 34.93/10.07 mark(U11(x0)) 34.93/10.07 mark(U21(x0)) 34.93/10.07 mark(U31(x0)) 34.93/10.07 mark(U41(x0, x1)) 34.93/10.07 mark(U42(x0)) 34.93/10.07 mark(isNatIList(x0)) 34.93/10.07 mark(U51(x0, x1)) 34.93/10.07 mark(U52(x0)) 34.93/10.07 mark(isNatList(x0)) 34.93/10.07 mark(U61(x0, x1)) 34.93/10.07 mark(U62(x0)) 34.93/10.07 mark(U71(x0, x1, x2)) 34.93/10.07 mark(U72(x0, x1)) 34.93/10.07 mark(isNat(x0)) 34.93/10.07 mark(length(x0)) 34.93/10.07 mark(U81(x0)) 34.93/10.07 mark(U91(x0, x1, x2, x3)) 34.93/10.07 mark(U92(x0, x1, x2, x3)) 34.93/10.07 mark(U93(x0, x1, x2, x3)) 34.93/10.07 mark(take(x0, x1)) 34.93/10.07 mark(cons(x0, x1)) 34.93/10.07 mark(0) 34.93/10.07 mark(tt) 34.93/10.07 mark(s(x0)) 34.93/10.07 mark(nil) 34.93/10.07 a__U11(x0) 34.93/10.07 a__U21(x0) 34.93/10.07 a__U31(x0) 34.93/10.07 a__U41(x0, x1) 34.93/10.07 a__U42(x0) 34.93/10.07 a__U51(x0, x1) 34.93/10.07 a__U52(x0) 34.93/10.07 a__isNatList(x0) 34.93/10.07 a__U61(x0, x1) 34.93/10.07 a__U62(x0) 34.93/10.07 a__U71(x0, x1, x2) 34.93/10.07 a__U72(x0, x1) 34.93/10.07 a__isNat(x0) 34.93/10.07 a__length(x0) 34.93/10.07 a__U81(x0) 34.93/10.07 a__U91(x0, x1, x2, x3) 34.93/10.07 a__U92(x0, x1, x2, x3) 34.93/10.07 a__U93(x0, x1, x2, x3) 34.93/10.07 a__take(x0, x1) 34.93/10.07 34.93/10.07 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (1) DependencyPairsProof (EQUIVALENT) 34.93/10.07 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (2) 34.93/10.07 Obligation: 34.93/10.07 Q DP problem: 34.93/10.07 The TRS P consists of the following rules: 34.93/10.07 34.93/10.07 A__U41(tt, V2) -> A__U42(a__isNatIList(V2)) 34.93/10.07 A__U41(tt, V2) -> A__ISNATILIST(V2) 34.93/10.07 A__U51(tt, V2) -> A__U52(a__isNatList(V2)) 34.93/10.07 A__U51(tt, V2) -> A__ISNATLIST(V2) 34.93/10.07 A__U61(tt, V2) -> A__U62(a__isNatIList(V2)) 34.93/10.07 A__U61(tt, V2) -> A__ISNATILIST(V2) 34.93/10.07 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 34.93/10.07 A__U71(tt, L, N) -> A__ISNAT(N) 34.93/10.07 A__U72(tt, L) -> A__LENGTH(mark(L)) 34.93/10.07 A__U72(tt, L) -> MARK(L) 34.93/10.07 A__U91(tt, IL, M, N) -> A__U92(a__isNat(M), IL, M, N) 34.93/10.07 A__U91(tt, IL, M, N) -> A__ISNAT(M) 34.93/10.07 A__U92(tt, IL, M, N) -> A__U93(a__isNat(N), IL, M, N) 34.93/10.07 A__U92(tt, IL, M, N) -> A__ISNAT(N) 34.93/10.07 A__U93(tt, IL, M, N) -> MARK(N) 34.93/10.07 A__ISNAT(length(V1)) -> A__U11(a__isNatList(V1)) 34.93/10.07 A__ISNAT(length(V1)) -> A__ISNATLIST(V1) 34.93/10.07 A__ISNAT(s(V1)) -> A__U21(a__isNat(V1)) 34.93/10.07 A__ISNAT(s(V1)) -> A__ISNAT(V1) 34.93/10.07 A__ISNATILIST(V) -> A__U31(a__isNatList(V)) 34.93/10.07 A__ISNATILIST(V) -> A__ISNATLIST(V) 34.93/10.07 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__isNat(V1), V2) 34.93/10.07 A__ISNATILIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__isNat(V1), V2) 34.93/10.07 A__ISNATLIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 A__ISNATLIST(take(V1, V2)) -> A__U61(a__isNat(V1), V2) 34.93/10.07 A__ISNATLIST(take(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 34.93/10.07 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 34.93/10.07 A__TAKE(0, IL) -> A__U81(a__isNatIList(IL)) 34.93/10.07 A__TAKE(0, IL) -> A__ISNATILIST(IL) 34.93/10.07 A__TAKE(s(M), cons(N, IL)) -> A__U91(a__isNatIList(IL), IL, M, N) 34.93/10.07 A__TAKE(s(M), cons(N, IL)) -> A__ISNATILIST(IL) 34.93/10.07 MARK(zeros) -> A__ZEROS 34.93/10.07 MARK(U11(X)) -> A__U11(mark(X)) 34.93/10.07 MARK(U11(X)) -> MARK(X) 34.93/10.07 MARK(U21(X)) -> A__U21(mark(X)) 34.93/10.07 MARK(U21(X)) -> MARK(X) 34.93/10.07 MARK(U31(X)) -> A__U31(mark(X)) 34.93/10.07 MARK(U31(X)) -> MARK(X) 34.93/10.07 MARK(U41(X1, X2)) -> A__U41(mark(X1), X2) 34.93/10.07 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(U42(X)) -> A__U42(mark(X)) 34.93/10.07 MARK(U42(X)) -> MARK(X) 34.93/10.07 MARK(isNatIList(X)) -> A__ISNATILIST(X) 34.93/10.07 MARK(U51(X1, X2)) -> A__U51(mark(X1), X2) 34.93/10.07 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(U52(X)) -> A__U52(mark(X)) 34.93/10.07 MARK(U52(X)) -> MARK(X) 34.93/10.07 MARK(isNatList(X)) -> A__ISNATLIST(X) 34.93/10.07 MARK(U61(X1, X2)) -> A__U61(mark(X1), X2) 34.93/10.07 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(U62(X)) -> A__U62(mark(X)) 34.93/10.07 MARK(U62(X)) -> MARK(X) 34.93/10.07 MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) 34.93/10.07 MARK(U71(X1, X2, X3)) -> MARK(X1) 34.93/10.07 MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) 34.93/10.07 MARK(U72(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(isNat(X)) -> A__ISNAT(X) 34.93/10.07 MARK(length(X)) -> A__LENGTH(mark(X)) 34.93/10.07 MARK(length(X)) -> MARK(X) 34.93/10.07 MARK(U81(X)) -> A__U81(mark(X)) 34.93/10.07 MARK(U81(X)) -> MARK(X) 34.93/10.07 MARK(U91(X1, X2, X3, X4)) -> A__U91(mark(X1), X2, X3, X4) 34.93/10.07 MARK(U91(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.07 MARK(U92(X1, X2, X3, X4)) -> A__U92(mark(X1), X2, X3, X4) 34.93/10.07 MARK(U92(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.07 MARK(U93(X1, X2, X3, X4)) -> A__U93(mark(X1), X2, X3, X4) 34.93/10.07 MARK(U93(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.07 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 34.93/10.07 MARK(take(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(take(X1, X2)) -> MARK(X2) 34.93/10.07 MARK(cons(X1, X2)) -> MARK(X1) 34.93/10.07 MARK(s(X)) -> MARK(X) 34.93/10.07 34.93/10.07 The TRS R consists of the following rules: 34.93/10.07 34.93/10.07 a__zeros -> cons(0, zeros) 34.93/10.07 a__U11(tt) -> tt 34.93/10.07 a__U21(tt) -> tt 34.93/10.07 a__U31(tt) -> tt 34.93/10.07 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.07 a__U42(tt) -> tt 34.93/10.07 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.07 a__U52(tt) -> tt 34.93/10.07 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.07 a__U62(tt) -> tt 34.93/10.07 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.07 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.07 a__U81(tt) -> nil 34.93/10.07 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.07 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.07 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.07 a__isNat(0) -> tt 34.93/10.07 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.07 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.07 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.07 a__isNatIList(zeros) -> tt 34.93/10.07 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.07 a__isNatList(nil) -> tt 34.93/10.07 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.07 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.07 a__length(nil) -> 0 34.93/10.07 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.07 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.07 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.07 mark(zeros) -> a__zeros 34.93/10.07 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.07 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.07 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.07 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.07 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.07 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.07 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.07 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.07 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.07 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.07 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.07 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.07 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.07 mark(isNat(X)) -> a__isNat(X) 34.93/10.07 mark(length(X)) -> a__length(mark(X)) 34.93/10.07 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.07 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.07 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.07 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.07 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.07 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.07 mark(0) -> 0 34.93/10.07 mark(tt) -> tt 34.93/10.07 mark(s(X)) -> s(mark(X)) 34.93/10.07 mark(nil) -> nil 34.93/10.07 a__zeros -> zeros 34.93/10.07 a__U11(X) -> U11(X) 34.93/10.07 a__U21(X) -> U21(X) 34.93/10.07 a__U31(X) -> U31(X) 34.93/10.07 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.07 a__U42(X) -> U42(X) 34.93/10.07 a__isNatIList(X) -> isNatIList(X) 34.93/10.07 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.07 a__U52(X) -> U52(X) 34.93/10.07 a__isNatList(X) -> isNatList(X) 34.93/10.07 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.07 a__U62(X) -> U62(X) 34.93/10.07 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.07 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.07 a__isNat(X) -> isNat(X) 34.93/10.07 a__length(X) -> length(X) 34.93/10.07 a__U81(X) -> U81(X) 34.93/10.07 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.07 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.07 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.07 a__take(X1, X2) -> take(X1, X2) 34.93/10.07 34.93/10.07 The set Q consists of the following terms: 34.93/10.07 34.93/10.07 a__zeros 34.93/10.07 a__isNatIList(x0) 34.93/10.07 mark(zeros) 34.93/10.07 mark(U11(x0)) 34.93/10.07 mark(U21(x0)) 34.93/10.07 mark(U31(x0)) 34.93/10.07 mark(U41(x0, x1)) 34.93/10.07 mark(U42(x0)) 34.93/10.07 mark(isNatIList(x0)) 34.93/10.07 mark(U51(x0, x1)) 34.93/10.07 mark(U52(x0)) 34.93/10.07 mark(isNatList(x0)) 34.93/10.07 mark(U61(x0, x1)) 34.93/10.07 mark(U62(x0)) 34.93/10.07 mark(U71(x0, x1, x2)) 34.93/10.07 mark(U72(x0, x1)) 34.93/10.07 mark(isNat(x0)) 34.93/10.07 mark(length(x0)) 34.93/10.07 mark(U81(x0)) 34.93/10.07 mark(U91(x0, x1, x2, x3)) 34.93/10.07 mark(U92(x0, x1, x2, x3)) 34.93/10.07 mark(U93(x0, x1, x2, x3)) 34.93/10.07 mark(take(x0, x1)) 34.93/10.07 mark(cons(x0, x1)) 34.93/10.07 mark(0) 34.93/10.07 mark(tt) 34.93/10.07 mark(s(x0)) 34.93/10.07 mark(nil) 34.93/10.07 a__U11(x0) 34.93/10.07 a__U21(x0) 34.93/10.07 a__U31(x0) 34.93/10.07 a__U41(x0, x1) 34.93/10.07 a__U42(x0) 34.93/10.07 a__U51(x0, x1) 34.93/10.07 a__U52(x0) 34.93/10.07 a__isNatList(x0) 34.93/10.07 a__U61(x0, x1) 34.93/10.07 a__U62(x0) 34.93/10.07 a__U71(x0, x1, x2) 34.93/10.07 a__U72(x0, x1) 34.93/10.07 a__isNat(x0) 34.93/10.07 a__length(x0) 34.93/10.07 a__U81(x0) 34.93/10.07 a__U91(x0, x1, x2, x3) 34.93/10.07 a__U92(x0, x1, x2, x3) 34.93/10.07 a__U93(x0, x1, x2, x3) 34.93/10.07 a__take(x0, x1) 34.93/10.07 34.93/10.07 We have to consider all minimal (P,Q,R)-chains. 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (3) DependencyGraphProof (EQUIVALENT) 34.93/10.07 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 27 less nodes. 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (4) 34.93/10.07 Complex Obligation (AND) 34.93/10.07 34.93/10.07 ---------------------------------------- 34.93/10.07 34.93/10.07 (5) 34.93/10.07 Obligation: 34.93/10.07 Q DP problem: 34.93/10.07 The TRS P consists of the following rules: 34.93/10.07 34.93/10.07 A__U41(tt, V2) -> A__ISNATILIST(V2) 34.93/10.07 A__ISNATILIST(V) -> A__ISNATLIST(V) 34.93/10.07 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__isNat(V1), V2) 34.93/10.07 A__U51(tt, V2) -> A__ISNATLIST(V2) 34.93/10.07 A__ISNATLIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 A__ISNAT(length(V1)) -> A__ISNATLIST(V1) 34.93/10.07 A__ISNATLIST(take(V1, V2)) -> A__U61(a__isNat(V1), V2) 34.93/10.07 A__U61(tt, V2) -> A__ISNATILIST(V2) 34.93/10.07 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__isNat(V1), V2) 34.93/10.07 A__ISNATILIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 A__ISNAT(s(V1)) -> A__ISNAT(V1) 34.93/10.07 A__ISNATLIST(take(V1, V2)) -> A__ISNAT(V1) 34.93/10.07 34.93/10.07 The TRS R consists of the following rules: 34.93/10.07 34.93/10.07 a__zeros -> cons(0, zeros) 34.93/10.07 a__U11(tt) -> tt 34.93/10.07 a__U21(tt) -> tt 34.93/10.07 a__U31(tt) -> tt 34.93/10.07 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.07 a__U42(tt) -> tt 34.93/10.07 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.07 a__U52(tt) -> tt 34.93/10.07 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.07 a__U62(tt) -> tt 34.93/10.07 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.07 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.07 a__U81(tt) -> nil 34.93/10.07 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.07 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.07 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.07 a__isNat(0) -> tt 34.93/10.07 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.07 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.07 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.07 a__isNatIList(zeros) -> tt 34.93/10.07 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__zeros -> zeros 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 a__isNatIList(x0) 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__isNat(x0) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (6) UsableRulesProof (EQUIVALENT) 34.93/10.08 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. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (7) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 A__U41(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 A__ISNATILIST(V) -> A__ISNATLIST(V) 34.93/10.08 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__isNat(V1), V2) 34.93/10.08 A__U51(tt, V2) -> A__ISNATLIST(V2) 34.93/10.08 A__ISNATLIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 A__ISNAT(length(V1)) -> A__ISNATLIST(V1) 34.93/10.08 A__ISNATLIST(take(V1, V2)) -> A__U61(a__isNat(V1), V2) 34.93/10.08 A__U61(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__isNat(V1), V2) 34.93/10.08 A__ISNATILIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 A__ISNAT(s(V1)) -> A__ISNAT(V1) 34.93/10.08 A__ISNATLIST(take(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 a__isNatIList(x0) 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__isNat(x0) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (8) QReductionProof (EQUIVALENT) 34.93/10.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (9) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 A__U41(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 A__ISNATILIST(V) -> A__ISNATLIST(V) 34.93/10.08 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__isNat(V1), V2) 34.93/10.08 A__U51(tt, V2) -> A__ISNATLIST(V2) 34.93/10.08 A__ISNATLIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 A__ISNAT(length(V1)) -> A__ISNATLIST(V1) 34.93/10.08 A__ISNATLIST(take(V1, V2)) -> A__U61(a__isNat(V1), V2) 34.93/10.08 A__U61(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__isNat(V1), V2) 34.93/10.08 A__ISNATILIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 A__ISNAT(s(V1)) -> A__ISNAT(V1) 34.93/10.08 A__ISNATLIST(take(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__isNatIList(x0) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__isNat(x0) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (10) QDPSizeChangeProof (EQUIVALENT) 34.93/10.08 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. 34.93/10.08 34.93/10.08 From the DPs we obtained the following set of size-change graphs: 34.93/10.08 *A__ISNATILIST(cons(V1, V2)) -> A__U41(a__isNat(V1), V2) 34.93/10.08 The graph contains the following edges 1 > 2 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATILIST(V) -> A__ISNATLIST(V) 34.93/10.08 The graph contains the following edges 1 >= 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATILIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 The graph contains the following edges 1 > 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__U51(tt, V2) -> A__ISNATLIST(V2) 34.93/10.08 The graph contains the following edges 2 >= 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNAT(length(V1)) -> A__ISNATLIST(V1) 34.93/10.08 The graph contains the following edges 1 > 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNAT(s(V1)) -> A__ISNAT(V1) 34.93/10.08 The graph contains the following edges 1 > 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATLIST(cons(V1, V2)) -> A__U51(a__isNat(V1), V2) 34.93/10.08 The graph contains the following edges 1 > 2 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATLIST(take(V1, V2)) -> A__U61(a__isNat(V1), V2) 34.93/10.08 The graph contains the following edges 1 > 2 34.93/10.08 34.93/10.08 34.93/10.08 *A__U61(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 The graph contains the following edges 2 >= 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__U41(tt, V2) -> A__ISNATILIST(V2) 34.93/10.08 The graph contains the following edges 2 >= 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATLIST(cons(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 The graph contains the following edges 1 > 1 34.93/10.08 34.93/10.08 34.93/10.08 *A__ISNATLIST(take(V1, V2)) -> A__ISNAT(V1) 34.93/10.08 The graph contains the following edges 1 > 1 34.93/10.08 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (11) 34.93/10.08 YES 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (12) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 MARK(U11(X)) -> MARK(X) 34.93/10.08 MARK(U21(X)) -> MARK(X) 34.93/10.08 MARK(U31(X)) -> MARK(X) 34.93/10.08 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U42(X)) -> MARK(X) 34.93/10.08 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U52(X)) -> MARK(X) 34.93/10.08 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U62(X)) -> MARK(X) 34.93/10.08 MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) 34.93/10.08 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 34.93/10.08 A__U72(tt, L) -> A__LENGTH(mark(L)) 34.93/10.08 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 34.93/10.08 A__U72(tt, L) -> MARK(L) 34.93/10.08 MARK(U71(X1, X2, X3)) -> MARK(X1) 34.93/10.08 MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) 34.93/10.08 MARK(U72(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(length(X)) -> A__LENGTH(mark(X)) 34.93/10.08 MARK(length(X)) -> MARK(X) 34.93/10.08 MARK(U81(X)) -> MARK(X) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> A__U91(mark(X1), X2, X3, X4) 34.93/10.08 A__U91(tt, IL, M, N) -> A__U92(a__isNat(M), IL, M, N) 34.93/10.08 A__U92(tt, IL, M, N) -> A__U93(a__isNat(N), IL, M, N) 34.93/10.08 A__U93(tt, IL, M, N) -> MARK(N) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> A__U92(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> A__U93(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 34.93/10.08 A__TAKE(s(M), cons(N, IL)) -> A__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X2) 34.93/10.08 MARK(cons(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(s(X)) -> MARK(X) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.08 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.08 a__U81(tt) -> nil 34.93/10.08 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.08 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.08 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__zeros -> zeros 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 a__isNatIList(x0) 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__isNat(x0) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (13) QDPOrderProof (EQUIVALENT) 34.93/10.08 We use the reduction pair processor [LPAR04,JAR06]. 34.93/10.08 34.93/10.08 34.93/10.08 The following pairs can be oriented strictly and are deleted. 34.93/10.08 34.93/10.08 MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) 34.93/10.08 MARK(U71(X1, X2, X3)) -> MARK(X1) 34.93/10.08 MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) 34.93/10.08 MARK(U72(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(length(X)) -> A__LENGTH(mark(X)) 34.93/10.08 MARK(length(X)) -> MARK(X) 34.93/10.08 The remaining pairs can at least be oriented weakly. 34.93/10.08 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 34.93/10.08 34.93/10.08 POL( A__LENGTH_1(x_1) ) = x_1 34.93/10.08 POL( A__TAKE_2(x_1, x_2) ) = 2x_2 34.93/10.08 POL( A__U71_3(x_1, ..., x_3) ) = x_2 + x_3 34.93/10.08 POL( A__U72_2(x_1, x_2) ) = x_2 34.93/10.08 POL( A__U91_4(x_1, ..., x_4) ) = x_2 + 2x_4 34.93/10.08 POL( A__U92_4(x_1, ..., x_4) ) = x_4 34.93/10.08 POL( A__U93_4(x_1, ..., x_4) ) = x_4 34.93/10.08 POL( mark_1(x_1) ) = x_1 34.93/10.08 POL( zeros ) = 0 34.93/10.08 POL( a__zeros ) = 0 34.93/10.08 POL( U11_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U11_1(x_1) ) = 2x_1 34.93/10.08 POL( U21_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U21_1(x_1) ) = 2x_1 34.93/10.08 POL( U31_1(x_1) ) = x_1 34.93/10.08 POL( a__U31_1(x_1) ) = x_1 34.93/10.08 POL( U41_2(x_1, x_2) ) = 2x_1 34.93/10.08 POL( a__U41_2(x_1, x_2) ) = 2x_1 34.93/10.08 POL( U42_1(x_1) ) = x_1 34.93/10.08 POL( a__U42_1(x_1) ) = x_1 34.93/10.08 POL( isNatIList_1(x_1) ) = 0 34.93/10.08 POL( a__isNatIList_1(x_1) ) = 0 34.93/10.08 POL( U51_2(x_1, x_2) ) = x_1 34.93/10.08 POL( a__U51_2(x_1, x_2) ) = x_1 34.93/10.08 POL( U52_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U52_1(x_1) ) = 2x_1 34.93/10.08 POL( isNatList_1(x_1) ) = 0 34.93/10.08 POL( a__isNatList_1(x_1) ) = 0 34.93/10.08 POL( U61_2(x_1, x_2) ) = x_1 34.93/10.08 POL( a__U61_2(x_1, x_2) ) = x_1 34.93/10.08 POL( U62_1(x_1) ) = x_1 34.93/10.08 POL( a__U62_1(x_1) ) = x_1 34.93/10.08 POL( U71_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + x_3 + 2 34.93/10.08 POL( a__U71_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + x_3 + 2 34.93/10.08 POL( U72_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 34.93/10.08 POL( a__U72_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 34.93/10.08 POL( isNat_1(x_1) ) = 0 34.93/10.08 POL( a__isNat_1(x_1) ) = 0 34.93/10.08 POL( length_1(x_1) ) = 2x_1 + 2 34.93/10.08 POL( a__length_1(x_1) ) = 2x_1 + 2 34.93/10.08 POL( U81_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U81_1(x_1) ) = 2x_1 34.93/10.08 POL( U91_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( a__U91_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( U92_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( a__U92_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( U93_4(x_1, ..., x_4) ) = x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( a__U93_4(x_1, ..., x_4) ) = x_1 + 2x_2 + 2x_3 + 2x_4 34.93/10.08 POL( take_2(x_1, x_2) ) = 2x_1 + 2x_2 34.93/10.08 POL( a__take_2(x_1, x_2) ) = 2x_1 + 2x_2 34.93/10.08 POL( cons_2(x_1, x_2) ) = 2x_1 + x_2 34.93/10.08 POL( 0 ) = 0 34.93/10.08 POL( tt ) = 0 34.93/10.08 POL( s_1(x_1) ) = x_1 34.93/10.08 POL( nil ) = 0 34.93/10.08 POL( MARK_1(x_1) ) = x_1 34.93/10.08 34.93/10.08 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 34.93/10.08 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(tt) -> nil 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.08 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.08 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.08 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__zeros -> zeros 34.93/10.08 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (14) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 MARK(U11(X)) -> MARK(X) 34.93/10.08 MARK(U21(X)) -> MARK(X) 34.93/10.08 MARK(U31(X)) -> MARK(X) 34.93/10.08 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U42(X)) -> MARK(X) 34.93/10.08 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U52(X)) -> MARK(X) 34.93/10.08 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U62(X)) -> MARK(X) 34.93/10.08 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 34.93/10.08 A__U72(tt, L) -> A__LENGTH(mark(L)) 34.93/10.08 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 34.93/10.08 A__U72(tt, L) -> MARK(L) 34.93/10.08 MARK(U81(X)) -> MARK(X) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> A__U91(mark(X1), X2, X3, X4) 34.93/10.08 A__U91(tt, IL, M, N) -> A__U92(a__isNat(M), IL, M, N) 34.93/10.08 A__U92(tt, IL, M, N) -> A__U93(a__isNat(N), IL, M, N) 34.93/10.08 A__U93(tt, IL, M, N) -> MARK(N) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> A__U92(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> A__U93(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 34.93/10.08 A__TAKE(s(M), cons(N, IL)) -> A__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X2) 34.93/10.08 MARK(cons(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(s(X)) -> MARK(X) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.08 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.08 a__U81(tt) -> nil 34.93/10.08 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.08 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.08 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__zeros -> zeros 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 a__isNatIList(x0) 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__isNat(x0) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (15) DependencyGraphProof (EQUIVALENT) 34.93/10.08 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (16) 34.93/10.08 Complex Obligation (AND) 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (17) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 MARK(U21(X)) -> MARK(X) 34.93/10.08 MARK(U11(X)) -> MARK(X) 34.93/10.08 MARK(U31(X)) -> MARK(X) 34.93/10.08 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U42(X)) -> MARK(X) 34.93/10.08 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U52(X)) -> MARK(X) 34.93/10.08 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U62(X)) -> MARK(X) 34.93/10.08 MARK(U81(X)) -> MARK(X) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> A__U91(mark(X1), X2, X3, X4) 34.93/10.08 A__U91(tt, IL, M, N) -> A__U92(a__isNat(M), IL, M, N) 34.93/10.08 A__U92(tt, IL, M, N) -> A__U93(a__isNat(N), IL, M, N) 34.93/10.08 A__U93(tt, IL, M, N) -> MARK(N) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> A__U92(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> A__U93(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 34.93/10.08 A__TAKE(s(M), cons(N, IL)) -> A__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X2) 34.93/10.08 MARK(cons(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(s(X)) -> MARK(X) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.08 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.08 a__U81(tt) -> nil 34.93/10.08 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.08 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.08 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__zeros -> zeros 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 34.93/10.08 The set Q consists of the following terms: 34.93/10.08 34.93/10.08 a__zeros 34.93/10.08 a__isNatIList(x0) 34.93/10.08 mark(zeros) 34.93/10.08 mark(U11(x0)) 34.93/10.08 mark(U21(x0)) 34.93/10.08 mark(U31(x0)) 34.93/10.08 mark(U41(x0, x1)) 34.93/10.08 mark(U42(x0)) 34.93/10.08 mark(isNatIList(x0)) 34.93/10.08 mark(U51(x0, x1)) 34.93/10.08 mark(U52(x0)) 34.93/10.08 mark(isNatList(x0)) 34.93/10.08 mark(U61(x0, x1)) 34.93/10.08 mark(U62(x0)) 34.93/10.08 mark(U71(x0, x1, x2)) 34.93/10.08 mark(U72(x0, x1)) 34.93/10.08 mark(isNat(x0)) 34.93/10.08 mark(length(x0)) 34.93/10.08 mark(U81(x0)) 34.93/10.08 mark(U91(x0, x1, x2, x3)) 34.93/10.08 mark(U92(x0, x1, x2, x3)) 34.93/10.08 mark(U93(x0, x1, x2, x3)) 34.93/10.08 mark(take(x0, x1)) 34.93/10.08 mark(cons(x0, x1)) 34.93/10.08 mark(0) 34.93/10.08 mark(tt) 34.93/10.08 mark(s(x0)) 34.93/10.08 mark(nil) 34.93/10.08 a__U11(x0) 34.93/10.08 a__U21(x0) 34.93/10.08 a__U31(x0) 34.93/10.08 a__U41(x0, x1) 34.93/10.08 a__U42(x0) 34.93/10.08 a__U51(x0, x1) 34.93/10.08 a__U52(x0) 34.93/10.08 a__isNatList(x0) 34.93/10.08 a__U61(x0, x1) 34.93/10.08 a__U62(x0) 34.93/10.08 a__U71(x0, x1, x2) 34.93/10.08 a__U72(x0, x1) 34.93/10.08 a__isNat(x0) 34.93/10.08 a__length(x0) 34.93/10.08 a__U81(x0) 34.93/10.08 a__U91(x0, x1, x2, x3) 34.93/10.08 a__U92(x0, x1, x2, x3) 34.93/10.08 a__U93(x0, x1, x2, x3) 34.93/10.08 a__take(x0, x1) 34.93/10.08 34.93/10.08 We have to consider all minimal (P,Q,R)-chains. 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (18) QDPOrderProof (EQUIVALENT) 34.93/10.08 We use the reduction pair processor [LPAR04,JAR06]. 34.93/10.08 34.93/10.08 34.93/10.08 The following pairs can be oriented strictly and are deleted. 34.93/10.08 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> A__U91(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U91(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> A__U92(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U92(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> A__U93(mark(X1), X2, X3, X4) 34.93/10.08 MARK(U93(X1, X2, X3, X4)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(take(X1, X2)) -> MARK(X2) 34.93/10.08 MARK(cons(X1, X2)) -> MARK(X1) 34.93/10.08 The remaining pairs can at least be oriented weakly. 34.93/10.08 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 34.93/10.08 34.93/10.08 POL( A__TAKE_2(x_1, x_2) ) = max{0, 2x_2 - 2} 34.93/10.08 POL( A__U91_4(x_1, ..., x_4) ) = 2x_4 + 2 34.93/10.08 POL( A__U92_4(x_1, ..., x_4) ) = 2x_4 + 2 34.93/10.08 POL( A__U93_4(x_1, ..., x_4) ) = 2x_4 + 2 34.93/10.08 POL( mark_1(x_1) ) = 2x_1 34.93/10.08 POL( zeros ) = 2 34.93/10.08 POL( a__zeros ) = 2 34.93/10.08 POL( U11_1(x_1) ) = x_1 34.93/10.08 POL( a__U11_1(x_1) ) = x_1 34.93/10.08 POL( U21_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U21_1(x_1) ) = 2x_1 34.93/10.08 POL( U31_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U31_1(x_1) ) = 2x_1 34.93/10.08 POL( U41_2(x_1, x_2) ) = 2x_1 34.93/10.08 POL( a__U41_2(x_1, x_2) ) = 2x_1 34.93/10.08 POL( U42_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U42_1(x_1) ) = 2x_1 34.93/10.08 POL( isNatIList_1(x_1) ) = 0 34.93/10.08 POL( a__isNatIList_1(x_1) ) = 0 34.93/10.08 POL( U51_2(x_1, x_2) ) = x_1 34.93/10.08 POL( a__U51_2(x_1, x_2) ) = x_1 34.93/10.08 POL( U52_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U52_1(x_1) ) = 2x_1 34.93/10.08 POL( isNatList_1(x_1) ) = 0 34.93/10.08 POL( a__isNatList_1(x_1) ) = 0 34.93/10.08 POL( U61_2(x_1, x_2) ) = x_1 34.93/10.08 POL( a__U61_2(x_1, x_2) ) = x_1 34.93/10.08 POL( U62_1(x_1) ) = x_1 34.93/10.08 POL( a__U62_1(x_1) ) = x_1 34.93/10.08 POL( U71_3(x_1, ..., x_3) ) = 0 34.93/10.08 POL( a__U71_3(x_1, ..., x_3) ) = max{0, -2} 34.93/10.08 POL( U72_2(x_1, x_2) ) = 0 34.93/10.08 POL( a__U72_2(x_1, x_2) ) = max{0, -2} 34.93/10.08 POL( isNat_1(x_1) ) = 0 34.93/10.08 POL( a__isNat_1(x_1) ) = 0 34.93/10.08 POL( length_1(x_1) ) = 0 34.93/10.08 POL( a__length_1(x_1) ) = max{0, -2} 34.93/10.08 POL( U81_1(x_1) ) = 2x_1 34.93/10.08 POL( a__U81_1(x_1) ) = 2x_1 34.93/10.08 POL( U91_4(x_1, ..., x_4) ) = x_1 + x_3 + 2x_4 + 2 34.93/10.08 POL( a__U91_4(x_1, ..., x_4) ) = x_1 + x_3 + 2x_4 + 2 34.93/10.08 POL( U92_4(x_1, ..., x_4) ) = x_1 + x_3 + x_4 + 1 34.93/10.08 POL( a__U92_4(x_1, ..., x_4) ) = x_1 + x_3 + 2x_4 + 2 34.93/10.08 POL( U93_4(x_1, ..., x_4) ) = x_1 + x_3 + 2x_4 + 1 34.93/10.08 POL( a__U93_4(x_1, ..., x_4) ) = x_1 + x_3 + 2x_4 + 2 34.93/10.08 POL( take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 34.93/10.08 POL( a__take_2(x_1, x_2) ) = x_1 + 2x_2 + 2 34.93/10.08 POL( cons_2(x_1, x_2) ) = x_1 + 2 34.93/10.08 POL( 0 ) = 0 34.93/10.08 POL( tt ) = 0 34.93/10.08 POL( s_1(x_1) ) = x_1 34.93/10.08 POL( nil ) = 0 34.93/10.08 POL( MARK_1(x_1) ) = 2x_1 + 2 34.93/10.08 34.93/10.08 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 34.93/10.08 34.93/10.08 mark(zeros) -> a__zeros 34.93/10.08 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.08 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.08 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.08 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.08 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.08 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.08 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.08 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.08 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.08 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.08 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.08 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.08 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.08 mark(isNat(X)) -> a__isNat(X) 34.93/10.08 mark(length(X)) -> a__length(mark(X)) 34.93/10.08 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.08 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.08 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.08 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.08 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.08 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.08 mark(0) -> 0 34.93/10.08 mark(tt) -> tt 34.93/10.08 mark(s(X)) -> s(mark(X)) 34.93/10.08 mark(nil) -> nil 34.93/10.08 a__isNat(0) -> tt 34.93/10.08 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.08 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.08 a__isNat(X) -> isNat(X) 34.93/10.08 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.08 a__isNatIList(zeros) -> tt 34.93/10.08 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.08 a__isNatIList(X) -> isNatIList(X) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U11(X) -> U11(X) 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U21(X) -> U21(X) 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U31(X) -> U31(X) 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U42(X) -> U42(X) 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U52(X) -> U52(X) 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.08 a__U62(tt) -> tt 34.93/10.08 a__U62(X) -> U62(X) 34.93/10.08 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.08 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.08 a__length(nil) -> 0 34.93/10.08 a__length(X) -> length(X) 34.93/10.08 a__U81(tt) -> nil 34.93/10.08 a__U81(X) -> U81(X) 34.93/10.08 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.08 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.08 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.08 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.08 a__take(X1, X2) -> take(X1, X2) 34.93/10.08 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.08 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.08 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.08 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.08 a__isNatList(nil) -> tt 34.93/10.08 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.08 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.08 a__isNatList(X) -> isNatList(X) 34.93/10.08 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.08 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__zeros -> zeros 34.93/10.08 34.93/10.08 34.93/10.08 ---------------------------------------- 34.93/10.08 34.93/10.08 (19) 34.93/10.08 Obligation: 34.93/10.08 Q DP problem: 34.93/10.08 The TRS P consists of the following rules: 34.93/10.08 34.93/10.08 MARK(U21(X)) -> MARK(X) 34.93/10.08 MARK(U11(X)) -> MARK(X) 34.93/10.08 MARK(U31(X)) -> MARK(X) 34.93/10.08 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U42(X)) -> MARK(X) 34.93/10.08 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U52(X)) -> MARK(X) 34.93/10.08 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.08 MARK(U62(X)) -> MARK(X) 34.93/10.08 MARK(U81(X)) -> MARK(X) 34.93/10.08 A__U91(tt, IL, M, N) -> A__U92(a__isNat(M), IL, M, N) 34.93/10.08 A__U92(tt, IL, M, N) -> A__U93(a__isNat(N), IL, M, N) 34.93/10.08 A__U93(tt, IL, M, N) -> MARK(N) 34.93/10.08 A__TAKE(s(M), cons(N, IL)) -> A__U91(a__isNatIList(IL), IL, M, N) 34.93/10.08 MARK(s(X)) -> MARK(X) 34.93/10.08 34.93/10.08 The TRS R consists of the following rules: 34.93/10.08 34.93/10.08 a__zeros -> cons(0, zeros) 34.93/10.08 a__U11(tt) -> tt 34.93/10.08 a__U21(tt) -> tt 34.93/10.08 a__U31(tt) -> tt 34.93/10.08 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.08 a__U42(tt) -> tt 34.93/10.08 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.08 a__U52(tt) -> tt 34.93/10.08 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.08 a__U62(tt) -> tt 34.93/10.09 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.09 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.09 a__U81(tt) -> nil 34.93/10.09 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.09 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.09 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.09 a__isNat(0) -> tt 34.93/10.09 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.09 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.09 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.09 a__isNatIList(zeros) -> tt 34.93/10.09 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.09 a__isNatList(nil) -> tt 34.93/10.09 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.09 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 34.93/10.09 a__length(nil) -> 0 34.93/10.09 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 34.93/10.09 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 34.93/10.09 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 34.93/10.09 mark(zeros) -> a__zeros 34.93/10.09 mark(U11(X)) -> a__U11(mark(X)) 34.93/10.09 mark(U21(X)) -> a__U21(mark(X)) 34.93/10.09 mark(U31(X)) -> a__U31(mark(X)) 34.93/10.09 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 34.93/10.09 mark(U42(X)) -> a__U42(mark(X)) 34.93/10.09 mark(isNatIList(X)) -> a__isNatIList(X) 34.93/10.09 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 34.93/10.09 mark(U52(X)) -> a__U52(mark(X)) 34.93/10.09 mark(isNatList(X)) -> a__isNatList(X) 34.93/10.09 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 34.93/10.09 mark(U62(X)) -> a__U62(mark(X)) 34.93/10.09 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 34.93/10.09 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 34.93/10.09 mark(isNat(X)) -> a__isNat(X) 34.93/10.09 mark(length(X)) -> a__length(mark(X)) 34.93/10.09 mark(U81(X)) -> a__U81(mark(X)) 34.93/10.09 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 34.93/10.09 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 34.93/10.09 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 34.93/10.09 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 34.93/10.09 mark(cons(X1, X2)) -> cons(mark(X1), X2) 34.93/10.09 mark(0) -> 0 34.93/10.09 mark(tt) -> tt 34.93/10.09 mark(s(X)) -> s(mark(X)) 34.93/10.09 mark(nil) -> nil 34.93/10.09 a__zeros -> zeros 34.93/10.09 a__U11(X) -> U11(X) 34.93/10.09 a__U21(X) -> U21(X) 34.93/10.09 a__U31(X) -> U31(X) 34.93/10.09 a__U41(X1, X2) -> U41(X1, X2) 34.93/10.09 a__U42(X) -> U42(X) 34.93/10.09 a__isNatIList(X) -> isNatIList(X) 34.93/10.09 a__U51(X1, X2) -> U51(X1, X2) 34.93/10.09 a__U52(X) -> U52(X) 34.93/10.09 a__isNatList(X) -> isNatList(X) 34.93/10.09 a__U61(X1, X2) -> U61(X1, X2) 34.93/10.09 a__U62(X) -> U62(X) 34.93/10.09 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 34.93/10.09 a__U72(X1, X2) -> U72(X1, X2) 34.93/10.09 a__isNat(X) -> isNat(X) 34.93/10.09 a__length(X) -> length(X) 34.93/10.09 a__U81(X) -> U81(X) 34.93/10.09 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 34.93/10.09 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 34.93/10.09 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 34.93/10.09 a__take(X1, X2) -> take(X1, X2) 34.93/10.09 34.93/10.09 The set Q consists of the following terms: 34.93/10.09 34.93/10.09 a__zeros 34.93/10.09 a__isNatIList(x0) 34.93/10.09 mark(zeros) 34.93/10.09 mark(U11(x0)) 34.93/10.09 mark(U21(x0)) 34.93/10.09 mark(U31(x0)) 34.93/10.09 mark(U41(x0, x1)) 34.93/10.09 mark(U42(x0)) 34.93/10.09 mark(isNatIList(x0)) 34.93/10.09 mark(U51(x0, x1)) 34.93/10.09 mark(U52(x0)) 34.93/10.09 mark(isNatList(x0)) 34.93/10.09 mark(U61(x0, x1)) 34.93/10.09 mark(U62(x0)) 34.93/10.09 mark(U71(x0, x1, x2)) 34.93/10.09 mark(U72(x0, x1)) 34.93/10.09 mark(isNat(x0)) 34.93/10.09 mark(length(x0)) 34.93/10.09 mark(U81(x0)) 34.93/10.09 mark(U91(x0, x1, x2, x3)) 34.93/10.09 mark(U92(x0, x1, x2, x3)) 34.93/10.09 mark(U93(x0, x1, x2, x3)) 34.93/10.09 mark(take(x0, x1)) 34.93/10.09 mark(cons(x0, x1)) 34.93/10.09 mark(0) 34.93/10.09 mark(tt) 34.93/10.09 mark(s(x0)) 34.93/10.09 mark(nil) 34.93/10.09 a__U11(x0) 34.93/10.09 a__U21(x0) 34.93/10.09 a__U31(x0) 34.93/10.09 a__U41(x0, x1) 34.93/10.09 a__U42(x0) 34.93/10.09 a__U51(x0, x1) 34.93/10.09 a__U52(x0) 34.93/10.09 a__isNatList(x0) 34.93/10.09 a__U61(x0, x1) 34.93/10.09 a__U62(x0) 34.93/10.09 a__U71(x0, x1, x2) 34.93/10.09 a__U72(x0, x1) 34.93/10.09 a__isNat(x0) 34.93/10.09 a__length(x0) 34.93/10.09 a__U81(x0) 34.93/10.09 a__U91(x0, x1, x2, x3) 34.93/10.09 a__U92(x0, x1, x2, x3) 34.93/10.09 a__U93(x0, x1, x2, x3) 34.93/10.09 a__take(x0, x1) 34.93/10.09 34.93/10.09 We have to consider all minimal (P,Q,R)-chains. 34.93/10.09 ---------------------------------------- 34.93/10.09 34.93/10.09 (20) DependencyGraphProof (EQUIVALENT) 34.93/10.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 34.93/10.09 ---------------------------------------- 34.93/10.09 34.93/10.09 (21) 34.93/10.09 Obligation: 34.93/10.09 Q DP problem: 34.93/10.09 The TRS P consists of the following rules: 34.93/10.09 34.93/10.09 MARK(U11(X)) -> MARK(X) 34.93/10.09 MARK(U21(X)) -> MARK(X) 34.93/10.09 MARK(U31(X)) -> MARK(X) 34.93/10.09 MARK(U41(X1, X2)) -> MARK(X1) 34.93/10.09 MARK(U42(X)) -> MARK(X) 34.93/10.09 MARK(U51(X1, X2)) -> MARK(X1) 34.93/10.09 MARK(U52(X)) -> MARK(X) 34.93/10.09 MARK(U61(X1, X2)) -> MARK(X1) 34.93/10.09 MARK(U62(X)) -> MARK(X) 34.93/10.09 MARK(U81(X)) -> MARK(X) 34.93/10.09 MARK(s(X)) -> MARK(X) 34.93/10.09 34.93/10.09 The TRS R consists of the following rules: 34.93/10.09 34.93/10.09 a__zeros -> cons(0, zeros) 34.93/10.09 a__U11(tt) -> tt 34.93/10.09 a__U21(tt) -> tt 34.93/10.09 a__U31(tt) -> tt 34.93/10.09 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 34.93/10.09 a__U42(tt) -> tt 34.93/10.09 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 34.93/10.09 a__U52(tt) -> tt 34.93/10.09 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 34.93/10.09 a__U62(tt) -> tt 34.93/10.09 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 34.93/10.09 a__U72(tt, L) -> s(a__length(mark(L))) 34.93/10.09 a__U81(tt) -> nil 34.93/10.09 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 34.93/10.09 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 34.93/10.09 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 34.93/10.09 a__isNat(0) -> tt 34.93/10.09 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 34.93/10.09 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 34.93/10.09 a__isNatIList(V) -> a__U31(a__isNatList(V)) 34.93/10.09 a__isNatIList(zeros) -> tt 34.93/10.09 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 34.93/10.09 a__isNatList(nil) -> tt 34.93/10.09 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 34.93/10.09 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__length(nil) -> 0 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__zeros -> zeros 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (22) UsableRulesProof (EQUIVALENT) 35.18/10.14 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. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (23) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 MARK(U11(X)) -> MARK(X) 35.18/10.14 MARK(U21(X)) -> MARK(X) 35.18/10.14 MARK(U31(X)) -> MARK(X) 35.18/10.14 MARK(U41(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U42(X)) -> MARK(X) 35.18/10.14 MARK(U51(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U52(X)) -> MARK(X) 35.18/10.14 MARK(U61(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U62(X)) -> MARK(X) 35.18/10.14 MARK(U81(X)) -> MARK(X) 35.18/10.14 MARK(s(X)) -> MARK(X) 35.18/10.14 35.18/10.14 R is empty. 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (24) QReductionProof (EQUIVALENT) 35.18/10.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (25) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 MARK(U11(X)) -> MARK(X) 35.18/10.14 MARK(U21(X)) -> MARK(X) 35.18/10.14 MARK(U31(X)) -> MARK(X) 35.18/10.14 MARK(U41(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U42(X)) -> MARK(X) 35.18/10.14 MARK(U51(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U52(X)) -> MARK(X) 35.18/10.14 MARK(U61(X1, X2)) -> MARK(X1) 35.18/10.14 MARK(U62(X)) -> MARK(X) 35.18/10.14 MARK(U81(X)) -> MARK(X) 35.18/10.14 MARK(s(X)) -> MARK(X) 35.18/10.14 35.18/10.14 R is empty. 35.18/10.14 Q is empty. 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (26) QDPSizeChangeProof (EQUIVALENT) 35.18/10.14 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. 35.18/10.14 35.18/10.14 From the DPs we obtained the following set of size-change graphs: 35.18/10.14 *MARK(U11(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U21(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U31(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U41(X1, X2)) -> MARK(X1) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U42(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U51(X1, X2)) -> MARK(X1) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U52(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U61(X1, X2)) -> MARK(X1) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U62(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(U81(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 *MARK(s(X)) -> MARK(X) 35.18/10.14 The graph contains the following edges 1 > 1 35.18/10.14 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (27) 35.18/10.14 YES 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (28) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 A__U72(tt, L) -> A__LENGTH(mark(L)) 35.18/10.14 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 35.18/10.14 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 35.18/10.14 35.18/10.14 The TRS R consists of the following rules: 35.18/10.14 35.18/10.14 a__zeros -> cons(0, zeros) 35.18/10.14 a__U11(tt) -> tt 35.18/10.14 a__U21(tt) -> tt 35.18/10.14 a__U31(tt) -> tt 35.18/10.14 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 35.18/10.14 a__U42(tt) -> tt 35.18/10.14 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 35.18/10.14 a__U52(tt) -> tt 35.18/10.14 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 35.18/10.14 a__U62(tt) -> tt 35.18/10.14 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 35.18/10.14 a__U72(tt, L) -> s(a__length(mark(L))) 35.18/10.14 a__U81(tt) -> nil 35.18/10.14 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 35.18/10.14 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 35.18/10.14 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 35.18/10.14 a__isNat(0) -> tt 35.18/10.14 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 35.18/10.14 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 35.18/10.14 a__isNatIList(V) -> a__U31(a__isNatList(V)) 35.18/10.14 a__isNatIList(zeros) -> tt 35.18/10.14 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 35.18/10.14 a__isNatList(nil) -> tt 35.18/10.14 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 35.18/10.14 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__length(nil) -> 0 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__zeros -> zeros 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (29) QDPQMonotonicMRRProof (EQUIVALENT) 35.18/10.14 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. 35.18/10.14 35.18/10.14 35.18/10.14 Strictly oriented rules of the TRS R: 35.18/10.14 35.18/10.14 a__length(nil) -> 0 35.18/10.14 35.18/10.14 Used ordering: Polynomial interpretation [POLO]: 35.18/10.14 35.18/10.14 POL(0) = 0 35.18/10.14 POL(A__LENGTH(x_1)) = 2*x_1 35.18/10.14 POL(A__U71(x_1, x_2, x_3)) = 2*x_2 + 2*x_3 35.18/10.14 POL(A__U72(x_1, x_2)) = 2*x_2 35.18/10.14 POL(U11(x_1)) = 2*x_1 35.18/10.14 POL(U21(x_1)) = 2*x_1 35.18/10.14 POL(U31(x_1)) = x_1 35.18/10.14 POL(U41(x_1, x_2)) = 2*x_1 35.18/10.14 POL(U42(x_1)) = 2*x_1 35.18/10.14 POL(U51(x_1, x_2)) = x_1 35.18/10.14 POL(U52(x_1)) = 2*x_1 35.18/10.14 POL(U61(x_1, x_2)) = 2*x_1 35.18/10.14 POL(U62(x_1)) = x_1 35.18/10.14 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 35.18/10.14 POL(U72(x_1, x_2)) = 1 + x_1 + x_2 35.18/10.14 POL(U81(x_1)) = 2*x_1 35.18/10.14 POL(U91(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(U92(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(U93(x_1, x_2, x_3, x_4)) = 2*x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(a__U11(x_1)) = 2*x_1 35.18/10.14 POL(a__U21(x_1)) = 2*x_1 35.18/10.14 POL(a__U31(x_1)) = x_1 35.18/10.14 POL(a__U41(x_1, x_2)) = 2*x_1 35.18/10.14 POL(a__U42(x_1)) = 2*x_1 35.18/10.14 POL(a__U51(x_1, x_2)) = x_1 35.18/10.14 POL(a__U52(x_1)) = 2*x_1 35.18/10.14 POL(a__U61(x_1, x_2)) = 2*x_1 35.18/10.14 POL(a__U62(x_1)) = x_1 35.18/10.14 POL(a__U71(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 35.18/10.14 POL(a__U72(x_1, x_2)) = 1 + x_1 + x_2 35.18/10.14 POL(a__U81(x_1)) = 2*x_1 35.18/10.14 POL(a__U91(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(a__U92(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(a__U93(x_1, x_2, x_3, x_4)) = 2*x_1 + x_2 + 2*x_3 + x_4 35.18/10.14 POL(a__isNat(x_1)) = 0 35.18/10.14 POL(a__isNatIList(x_1)) = 0 35.18/10.14 POL(a__isNatList(x_1)) = 0 35.18/10.14 POL(a__length(x_1)) = 1 + x_1 35.18/10.14 POL(a__take(x_1, x_2)) = 2*x_1 + x_2 35.18/10.14 POL(a__zeros) = 0 35.18/10.14 POL(cons(x_1, x_2)) = x_1 + x_2 35.18/10.14 POL(isNat(x_1)) = 0 35.18/10.14 POL(isNatIList(x_1)) = 0 35.18/10.14 POL(isNatList(x_1)) = 0 35.18/10.14 POL(length(x_1)) = 1 + x_1 35.18/10.14 POL(mark(x_1)) = x_1 35.18/10.14 POL(nil) = 0 35.18/10.14 POL(s(x_1)) = x_1 35.18/10.14 POL(take(x_1, x_2)) = 2*x_1 + x_2 35.18/10.14 POL(tt) = 0 35.18/10.14 POL(zeros) = 0 35.18/10.14 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (30) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 A__U72(tt, L) -> A__LENGTH(mark(L)) 35.18/10.14 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 35.18/10.14 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 35.18/10.14 35.18/10.14 The TRS R consists of the following rules: 35.18/10.14 35.18/10.14 a__zeros -> cons(0, zeros) 35.18/10.14 a__U11(tt) -> tt 35.18/10.14 a__U21(tt) -> tt 35.18/10.14 a__U31(tt) -> tt 35.18/10.14 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 35.18/10.14 a__U42(tt) -> tt 35.18/10.14 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 35.18/10.14 a__U52(tt) -> tt 35.18/10.14 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 35.18/10.14 a__U62(tt) -> tt 35.18/10.14 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 35.18/10.14 a__U72(tt, L) -> s(a__length(mark(L))) 35.18/10.14 a__U81(tt) -> nil 35.18/10.14 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 35.18/10.14 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 35.18/10.14 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 35.18/10.14 a__isNat(0) -> tt 35.18/10.14 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 35.18/10.14 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 35.18/10.14 a__isNatIList(V) -> a__U31(a__isNatList(V)) 35.18/10.14 a__isNatIList(zeros) -> tt 35.18/10.14 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 35.18/10.14 a__isNatList(nil) -> tt 35.18/10.14 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 35.18/10.14 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__zeros -> zeros 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (31) QDPQMonotonicMRRProof (EQUIVALENT) 35.18/10.14 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. 35.18/10.14 35.18/10.14 35.18/10.14 Strictly oriented rules of the TRS R: 35.18/10.14 35.18/10.14 a__take(0, IL) -> a__U81(a__isNatIList(IL)) 35.18/10.14 35.18/10.14 Used ordering: Polynomial interpretation [POLO]: 35.18/10.14 35.18/10.14 POL(0) = 0 35.18/10.14 POL(A__LENGTH(x_1)) = 2*x_1 35.18/10.14 POL(A__U71(x_1, x_2, x_3)) = 2*x_2 + 2*x_3 35.18/10.14 POL(A__U72(x_1, x_2)) = 2*x_2 35.18/10.14 POL(U11(x_1)) = 2*x_1 35.18/10.14 POL(U21(x_1)) = x_1 35.18/10.14 POL(U31(x_1)) = 2*x_1 35.18/10.14 POL(U41(x_1, x_2)) = x_1 35.18/10.14 POL(U42(x_1)) = 2*x_1 35.18/10.14 POL(U51(x_1, x_2)) = 2*x_1 35.18/10.14 POL(U52(x_1)) = x_1 35.18/10.14 POL(U61(x_1, x_2)) = x_1 35.18/10.14 POL(U62(x_1)) = 2*x_1 35.18/10.14 POL(U71(x_1, x_2, x_3)) = x_1 + x_2 + x_3 35.18/10.14 POL(U72(x_1, x_2)) = x_1 + x_2 35.18/10.14 POL(U81(x_1)) = 2*x_1 35.18/10.14 POL(U91(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(U92(x_1, x_2, x_3, x_4)) = 1 + x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(U93(x_1, x_2, x_3, x_4)) = 1 + x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(a__U11(x_1)) = 2*x_1 35.18/10.14 POL(a__U21(x_1)) = x_1 35.18/10.14 POL(a__U31(x_1)) = 2*x_1 35.18/10.14 POL(a__U41(x_1, x_2)) = x_1 35.18/10.14 POL(a__U42(x_1)) = 2*x_1 35.18/10.14 POL(a__U51(x_1, x_2)) = 2*x_1 35.18/10.14 POL(a__U52(x_1)) = x_1 35.18/10.14 POL(a__U61(x_1, x_2)) = x_1 35.18/10.14 POL(a__U62(x_1)) = 2*x_1 35.18/10.14 POL(a__U71(x_1, x_2, x_3)) = x_1 + x_2 + x_3 35.18/10.14 POL(a__U72(x_1, x_2)) = x_1 + x_2 35.18/10.14 POL(a__U81(x_1)) = 2*x_1 35.18/10.14 POL(a__U91(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(a__U92(x_1, x_2, x_3, x_4)) = 1 + x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(a__U93(x_1, x_2, x_3, x_4)) = 1 + x_1 + 2*x_2 + x_3 + 2*x_4 35.18/10.14 POL(a__isNat(x_1)) = 0 35.18/10.14 POL(a__isNatIList(x_1)) = 0 35.18/10.14 POL(a__isNatList(x_1)) = 0 35.18/10.14 POL(a__length(x_1)) = x_1 35.18/10.14 POL(a__take(x_1, x_2)) = 1 + x_1 + 2*x_2 35.18/10.14 POL(a__zeros) = 0 35.18/10.14 POL(cons(x_1, x_2)) = 2*x_1 + x_2 35.18/10.14 POL(isNat(x_1)) = 0 35.18/10.14 POL(isNatIList(x_1)) = 0 35.18/10.14 POL(isNatList(x_1)) = 0 35.18/10.14 POL(length(x_1)) = x_1 35.18/10.14 POL(mark(x_1)) = x_1 35.18/10.14 POL(nil) = 0 35.18/10.14 POL(s(x_1)) = x_1 35.18/10.14 POL(take(x_1, x_2)) = 1 + x_1 + 2*x_2 35.18/10.14 POL(tt) = 0 35.18/10.14 POL(zeros) = 0 35.18/10.14 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (32) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 A__U72(tt, L) -> A__LENGTH(mark(L)) 35.18/10.14 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 35.18/10.14 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 35.18/10.14 35.18/10.14 The TRS R consists of the following rules: 35.18/10.14 35.18/10.14 a__zeros -> cons(0, zeros) 35.18/10.14 a__U11(tt) -> tt 35.18/10.14 a__U21(tt) -> tt 35.18/10.14 a__U31(tt) -> tt 35.18/10.14 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 35.18/10.14 a__U42(tt) -> tt 35.18/10.14 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 35.18/10.14 a__U52(tt) -> tt 35.18/10.14 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 35.18/10.14 a__U62(tt) -> tt 35.18/10.14 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 35.18/10.14 a__U72(tt, L) -> s(a__length(mark(L))) 35.18/10.14 a__U81(tt) -> nil 35.18/10.14 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 35.18/10.14 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 35.18/10.14 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 35.18/10.14 a__isNat(0) -> tt 35.18/10.14 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 35.18/10.14 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 35.18/10.14 a__isNatIList(V) -> a__U31(a__isNatList(V)) 35.18/10.14 a__isNatIList(zeros) -> tt 35.18/10.14 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 35.18/10.14 a__isNatList(nil) -> tt 35.18/10.14 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 35.18/10.14 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__zeros -> zeros 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (33) QDPOrderProof (EQUIVALENT) 35.18/10.14 We use the reduction pair processor [LPAR04,JAR06]. 35.18/10.14 35.18/10.14 35.18/10.14 The following pairs can be oriented strictly and are deleted. 35.18/10.14 35.18/10.14 A__U72(tt, L) -> A__LENGTH(mark(L)) 35.18/10.14 A__LENGTH(cons(N, L)) -> A__U71(a__isNatList(L), L, N) 35.18/10.14 The remaining pairs can at least be oriented weakly. 35.18/10.14 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 35.18/10.14 35.18/10.14 POL( A__LENGTH_1(x_1) ) = 2x_1 + 1 35.18/10.14 POL( mark_1(x_1) ) = x_1 35.18/10.14 POL( zeros ) = 0 35.18/10.14 POL( a__zeros ) = 0 35.18/10.14 POL( U11_1(x_1) ) = x_1 35.18/10.14 POL( a__U11_1(x_1) ) = x_1 35.18/10.14 POL( U21_1(x_1) ) = x_1 35.18/10.14 POL( a__U21_1(x_1) ) = x_1 35.18/10.14 POL( U31_1(x_1) ) = 2 35.18/10.14 POL( a__U31_1(x_1) ) = 2 35.18/10.14 POL( U41_2(x_1, x_2) ) = 2 35.18/10.14 POL( a__U41_2(x_1, x_2) ) = 2 35.18/10.14 POL( U42_1(x_1) ) = x_1 35.18/10.14 POL( a__U42_1(x_1) ) = x_1 35.18/10.14 POL( isNatIList_1(x_1) ) = 2 35.18/10.14 POL( a__isNatIList_1(x_1) ) = 2 35.18/10.14 POL( U51_2(x_1, x_2) ) = 2x_2 35.18/10.14 POL( a__U51_2(x_1, x_2) ) = 2x_2 35.18/10.14 POL( U52_1(x_1) ) = 2x_1 35.18/10.14 POL( a__U52_1(x_1) ) = 2x_1 35.18/10.14 POL( isNatList_1(x_1) ) = x_1 35.18/10.14 POL( a__isNatList_1(x_1) ) = x_1 35.18/10.14 POL( U61_2(x_1, x_2) ) = x_1 35.18/10.14 POL( a__U61_2(x_1, x_2) ) = x_1 35.18/10.14 POL( U62_1(x_1) ) = 2 35.18/10.14 POL( a__U62_1(x_1) ) = 2 35.18/10.14 POL( U71_3(x_1, ..., x_3) ) = 2x_2 35.18/10.14 POL( a__U71_3(x_1, ..., x_3) ) = 2x_2 35.18/10.14 POL( U72_2(x_1, x_2) ) = 2x_2 35.18/10.14 POL( a__U72_2(x_1, x_2) ) = 2x_2 35.18/10.14 POL( isNat_1(x_1) ) = x_1 35.18/10.14 POL( a__isNat_1(x_1) ) = x_1 35.18/10.14 POL( length_1(x_1) ) = x_1 35.18/10.14 POL( a__length_1(x_1) ) = x_1 35.18/10.14 POL( U81_1(x_1) ) = x_1 + 1 35.18/10.14 POL( a__U81_1(x_1) ) = x_1 + 1 35.18/10.14 POL( U91_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( a__U91_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( U92_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( a__U92_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( U93_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( a__U93_4(x_1, ..., x_4) ) = 2x_3 35.18/10.14 POL( take_2(x_1, x_2) ) = x_1 35.18/10.14 POL( a__take_2(x_1, x_2) ) = x_1 35.18/10.14 POL( cons_2(x_1, x_2) ) = 2x_2 35.18/10.14 POL( 0 ) = 2 35.18/10.14 POL( tt ) = 2 35.18/10.14 POL( s_1(x_1) ) = 2x_1 35.18/10.14 POL( nil ) = 2 35.18/10.14 POL( A__U71_3(x_1, ..., x_3) ) = max{0, 2x_1 + 2x_2 - 2} 35.18/10.14 POL( A__U72_2(x_1, x_2) ) = 2x_2 + 2 35.18/10.14 35.18/10.14 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 35.18/10.14 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__isNatList(nil) -> tt 35.18/10.14 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 35.18/10.14 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__isNat(0) -> tt 35.18/10.14 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 35.18/10.14 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__U11(tt) -> tt 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(tt) -> tt 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(tt) -> tt 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(tt) -> tt 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(tt) -> tt 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(tt) -> tt 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(tt) -> nil 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 a__isNatIList(V) -> a__U31(a__isNatList(V)) 35.18/10.14 a__isNatIList(zeros) -> tt 35.18/10.14 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 35.18/10.14 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 35.18/10.14 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 35.18/10.14 a__U72(tt, L) -> s(a__length(mark(L))) 35.18/10.14 a__zeros -> cons(0, zeros) 35.18/10.14 a__zeros -> zeros 35.18/10.14 35.18/10.14 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (34) 35.18/10.14 Obligation: 35.18/10.14 Q DP problem: 35.18/10.14 The TRS P consists of the following rules: 35.18/10.14 35.18/10.14 A__U71(tt, L, N) -> A__U72(a__isNat(N), L) 35.18/10.14 35.18/10.14 The TRS R consists of the following rules: 35.18/10.14 35.18/10.14 a__zeros -> cons(0, zeros) 35.18/10.14 a__U11(tt) -> tt 35.18/10.14 a__U21(tt) -> tt 35.18/10.14 a__U31(tt) -> tt 35.18/10.14 a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) 35.18/10.14 a__U42(tt) -> tt 35.18/10.14 a__U51(tt, V2) -> a__U52(a__isNatList(V2)) 35.18/10.14 a__U52(tt) -> tt 35.18/10.14 a__U61(tt, V2) -> a__U62(a__isNatIList(V2)) 35.18/10.14 a__U62(tt) -> tt 35.18/10.14 a__U71(tt, L, N) -> a__U72(a__isNat(N), L) 35.18/10.14 a__U72(tt, L) -> s(a__length(mark(L))) 35.18/10.14 a__U81(tt) -> nil 35.18/10.14 a__U91(tt, IL, M, N) -> a__U92(a__isNat(M), IL, M, N) 35.18/10.14 a__U92(tt, IL, M, N) -> a__U93(a__isNat(N), IL, M, N) 35.18/10.14 a__U93(tt, IL, M, N) -> cons(mark(N), take(M, IL)) 35.18/10.14 a__isNat(0) -> tt 35.18/10.14 a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) 35.18/10.14 a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 35.18/10.14 a__isNatIList(V) -> a__U31(a__isNatList(V)) 35.18/10.14 a__isNatIList(zeros) -> tt 35.18/10.14 a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) 35.18/10.14 a__isNatList(nil) -> tt 35.18/10.14 a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) 35.18/10.14 a__isNatList(take(V1, V2)) -> a__U61(a__isNat(V1), V2) 35.18/10.14 a__length(cons(N, L)) -> a__U71(a__isNatList(L), L, N) 35.18/10.14 a__take(s(M), cons(N, IL)) -> a__U91(a__isNatIList(IL), IL, M, N) 35.18/10.14 mark(zeros) -> a__zeros 35.18/10.14 mark(U11(X)) -> a__U11(mark(X)) 35.18/10.14 mark(U21(X)) -> a__U21(mark(X)) 35.18/10.14 mark(U31(X)) -> a__U31(mark(X)) 35.18/10.14 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 35.18/10.14 mark(U42(X)) -> a__U42(mark(X)) 35.18/10.14 mark(isNatIList(X)) -> a__isNatIList(X) 35.18/10.14 mark(U51(X1, X2)) -> a__U51(mark(X1), X2) 35.18/10.14 mark(U52(X)) -> a__U52(mark(X)) 35.18/10.14 mark(isNatList(X)) -> a__isNatList(X) 35.18/10.14 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 35.18/10.14 mark(U62(X)) -> a__U62(mark(X)) 35.18/10.14 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 35.18/10.14 mark(U72(X1, X2)) -> a__U72(mark(X1), X2) 35.18/10.14 mark(isNat(X)) -> a__isNat(X) 35.18/10.14 mark(length(X)) -> a__length(mark(X)) 35.18/10.14 mark(U81(X)) -> a__U81(mark(X)) 35.18/10.14 mark(U91(X1, X2, X3, X4)) -> a__U91(mark(X1), X2, X3, X4) 35.18/10.14 mark(U92(X1, X2, X3, X4)) -> a__U92(mark(X1), X2, X3, X4) 35.18/10.14 mark(U93(X1, X2, X3, X4)) -> a__U93(mark(X1), X2, X3, X4) 35.18/10.14 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 35.18/10.14 mark(cons(X1, X2)) -> cons(mark(X1), X2) 35.18/10.14 mark(0) -> 0 35.18/10.14 mark(tt) -> tt 35.18/10.14 mark(s(X)) -> s(mark(X)) 35.18/10.14 mark(nil) -> nil 35.18/10.14 a__zeros -> zeros 35.18/10.14 a__U11(X) -> U11(X) 35.18/10.14 a__U21(X) -> U21(X) 35.18/10.14 a__U31(X) -> U31(X) 35.18/10.14 a__U41(X1, X2) -> U41(X1, X2) 35.18/10.14 a__U42(X) -> U42(X) 35.18/10.14 a__isNatIList(X) -> isNatIList(X) 35.18/10.14 a__U51(X1, X2) -> U51(X1, X2) 35.18/10.14 a__U52(X) -> U52(X) 35.18/10.14 a__isNatList(X) -> isNatList(X) 35.18/10.14 a__U61(X1, X2) -> U61(X1, X2) 35.18/10.14 a__U62(X) -> U62(X) 35.18/10.14 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 35.18/10.14 a__U72(X1, X2) -> U72(X1, X2) 35.18/10.14 a__isNat(X) -> isNat(X) 35.18/10.14 a__length(X) -> length(X) 35.18/10.14 a__U81(X) -> U81(X) 35.18/10.14 a__U91(X1, X2, X3, X4) -> U91(X1, X2, X3, X4) 35.18/10.14 a__U92(X1, X2, X3, X4) -> U92(X1, X2, X3, X4) 35.18/10.14 a__U93(X1, X2, X3, X4) -> U93(X1, X2, X3, X4) 35.18/10.14 a__take(X1, X2) -> take(X1, X2) 35.18/10.14 35.18/10.14 The set Q consists of the following terms: 35.18/10.14 35.18/10.14 a__zeros 35.18/10.14 a__isNatIList(x0) 35.18/10.14 mark(zeros) 35.18/10.14 mark(U11(x0)) 35.18/10.14 mark(U21(x0)) 35.18/10.14 mark(U31(x0)) 35.18/10.14 mark(U41(x0, x1)) 35.18/10.14 mark(U42(x0)) 35.18/10.14 mark(isNatIList(x0)) 35.18/10.14 mark(U51(x0, x1)) 35.18/10.14 mark(U52(x0)) 35.18/10.14 mark(isNatList(x0)) 35.18/10.14 mark(U61(x0, x1)) 35.18/10.14 mark(U62(x0)) 35.18/10.14 mark(U71(x0, x1, x2)) 35.18/10.14 mark(U72(x0, x1)) 35.18/10.14 mark(isNat(x0)) 35.18/10.14 mark(length(x0)) 35.18/10.14 mark(U81(x0)) 35.18/10.14 mark(U91(x0, x1, x2, x3)) 35.18/10.14 mark(U92(x0, x1, x2, x3)) 35.18/10.14 mark(U93(x0, x1, x2, x3)) 35.18/10.14 mark(take(x0, x1)) 35.18/10.14 mark(cons(x0, x1)) 35.18/10.14 mark(0) 35.18/10.14 mark(tt) 35.18/10.14 mark(s(x0)) 35.18/10.14 mark(nil) 35.18/10.14 a__U11(x0) 35.18/10.14 a__U21(x0) 35.18/10.14 a__U31(x0) 35.18/10.14 a__U41(x0, x1) 35.18/10.14 a__U42(x0) 35.18/10.14 a__U51(x0, x1) 35.18/10.14 a__U52(x0) 35.18/10.14 a__isNatList(x0) 35.18/10.14 a__U61(x0, x1) 35.18/10.14 a__U62(x0) 35.18/10.14 a__U71(x0, x1, x2) 35.18/10.14 a__U72(x0, x1) 35.18/10.14 a__isNat(x0) 35.18/10.14 a__length(x0) 35.18/10.14 a__U81(x0) 35.18/10.14 a__U91(x0, x1, x2, x3) 35.18/10.14 a__U92(x0, x1, x2, x3) 35.18/10.14 a__U93(x0, x1, x2, x3) 35.18/10.14 a__take(x0, x1) 35.18/10.14 35.18/10.14 We have to consider all minimal (P,Q,R)-chains. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (35) DependencyGraphProof (EQUIVALENT) 35.18/10.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 35.18/10.14 ---------------------------------------- 35.18/10.14 35.18/10.14 (36) 35.18/10.14 TRUE 35.36/10.21 EOF