TIMEOUT

The TRS could not be proven terminating. The proof attempt took 60027 ms.

The following DP Processors were used


Problem 1 remains open; application of the following processors failed [DependencyGraph (timeout)].

The following open problems remain:



Open Dependency Pair Problem 1

Dependency Pairs

active#(take(s(M), cons(N, IL))) → U91#(isNatIList(IL), IL, M, N)active#(U72(tt, L)) → length#(L)
mark#(U51(X1, X2)) → U51#(mark(X1), X2)active#(U72(tt, L)) → s#(length(L))
mark#(take(X1, X2)) → active#(take(mark(X1), mark(X2)))active#(U51(tt, V2)) → U52#(isNatList(V2))
active#(U51(tt, V2)) → isNatList#(V2)U91#(active(X1), X2, X3, X4) → U91#(X1, X2, X3, X4)
U51#(mark(X1), X2) → U51#(X1, X2)U72#(mark(X1), X2) → U72#(X1, X2)
isNat#(active(X)) → isNat#(X)mark#(s(X)) → mark#(X)
U71#(X1, mark(X2), X3) → U71#(X1, X2, X3)length#(mark(X)) → length#(X)
mark#(U81(X)) → active#(U81(mark(X)))U81#(mark(X)) → U81#(X)
mark#(U52(X)) → mark#(X)active#(U31(tt)) → mark#(tt)
mark#(U42(X)) → active#(U42(mark(X)))U92#(X1, mark(X2), X3, X4) → U92#(X1, X2, X3, X4)
mark#(U92(X1, X2, X3, X4)) → mark#(X1)U93#(X1, X2, X3, active(X4)) → U93#(X1, X2, X3, X4)
active#(U42(tt)) → mark#(tt)active#(U91(tt, IL, M, N)) → U92#(isNat(M), IL, M, N)
mark#(U62(X)) → active#(U62(mark(X)))mark#(U11(X)) → mark#(X)
mark#(U21(X)) → mark#(X)active#(isNat(length(V1))) → U11#(isNatList(V1))
active#(U93(tt, IL, M, N)) → take#(M, IL)active#(U93(tt, IL, M, N)) → mark#(cons(N, take(M, IL)))
U71#(active(X1), X2, X3) → U71#(X1, X2, X3)active#(isNatList(cons(V1, V2))) → mark#(U51(isNat(V1), V2))
mark#(U41(X1, X2)) → mark#(X1)mark#(U11(X)) → active#(U11(mark(X)))
cons#(X1, mark(X2)) → cons#(X1, X2)U41#(X1, active(X2)) → U41#(X1, X2)
active#(isNat(s(V1))) → isNat#(V1)active#(isNatIList(cons(V1, V2))) → mark#(U41(isNat(V1), V2))
U62#(active(X)) → U62#(X)active#(U61(tt, V2)) → isNatIList#(V2)
cons#(active(X1), X2) → cons#(X1, X2)active#(isNatList(cons(V1, V2))) → U51#(isNat(V1), V2)
U91#(mark(X1), X2, X3, X4) → U91#(X1, X2, X3, X4)mark#(U71(X1, X2, X3)) → U71#(mark(X1), X2, X3)
U93#(X1, X2, X3, mark(X4)) → U93#(X1, X2, X3, X4)U51#(X1, mark(X2)) → U51#(X1, X2)
mark#(isNatList(X)) → isNatList#(X)isNatList#(mark(X)) → isNatList#(X)
active#(isNatIList(V)) → U31#(isNatList(V))mark#(U72(X1, X2)) → active#(U72(mark(X1), X2))
mark#(take(X1, X2)) → mark#(X1)mark#(U21(X)) → active#(U21(mark(X)))
active#(U21(tt)) → mark#(tt)active#(length(cons(N, L))) → mark#(U71(isNatList(L), L, N))
active#(U41(tt, V2)) → mark#(U42(isNatIList(V2)))active#(take(s(M), cons(N, IL))) → isNatIList#(IL)
active#(isNatIList(cons(V1, V2))) → U41#(isNat(V1), V2)active#(U91(tt, IL, M, N)) → mark#(U92(isNat(M), IL, M, N))
active#(U81(tt)) → mark#(nil)U61#(active(X1), X2) → U61#(X1, X2)
mark#(s(X)) → s#(mark(X))U52#(active(X)) → U52#(X)
U61#(mark(X1), X2) → U61#(X1, X2)active#(isNatIList(V)) → mark#(U31(isNatList(V)))
isNatList#(active(X)) → isNatList#(X)active#(U62(tt)) → mark#(tt)
U41#(X1, mark(X2)) → U41#(X1, X2)active#(isNat(0)) → mark#(tt)
active#(take(0, IL)) → mark#(U81(isNatIList(IL)))take#(X1, mark(X2)) → take#(X1, X2)
mark#(U61(X1, X2)) → active#(U61(mark(X1), X2))mark#(isNatIList(X)) → isNatIList#(X)
isNatIList#(mark(X)) → isNatIList#(X)mark#(U92(X1, X2, X3, X4)) → U92#(mark(X1), X2, X3, X4)
mark#(U93(X1, X2, X3, X4)) → mark#(X1)cons#(X1, active(X2)) → cons#(X1, X2)
U92#(X1, X2, mark(X3), X4) → U92#(X1, X2, X3, X4)U93#(X1, X2, active(X3), X4) → U93#(X1, X2, X3, X4)
active#(U52(tt)) → mark#(tt)mark#(U61(X1, X2)) → mark#(X1)
take#(mark(X1), X2) → take#(X1, X2)mark#(U11(X)) → U11#(mark(X))
U71#(X1, X2, active(X3)) → U71#(X1, X2, X3)mark#(U42(X)) → mark#(X)
mark#(isNat(X)) → isNat#(X)U61#(X1, mark(X2)) → U61#(X1, X2)
isNat#(mark(X)) → isNat#(X)active#(U11(tt)) → mark#(tt)
active#(length(cons(N, L))) → isNatList#(L)active#(isNatList(nil)) → mark#(tt)
mark#(nil) → active#(nil)take#(X1, active(X2)) → take#(X1, X2)
active#(isNatIList(zeros)) → mark#(tt)U41#(mark(X1), X2) → U41#(X1, X2)
mark#(cons(X1, X2)) → cons#(mark(X1), X2)mark#(U91(X1, X2, X3, X4)) → active#(U91(mark(X1), X2, X3, X4))
mark#(length(X)) → length#(mark(X))U31#(active(X)) → U31#(X)
U93#(X1, X2, mark(X3), X4) → U93#(X1, X2, X3, X4)U72#(active(X1), X2) → U72#(X1, X2)
active#(isNatIList(V)) → isNatList#(V)mark#(take(X1, X2)) → take#(mark(X1), mark(X2))
s#(mark(X)) → s#(X)U52#(mark(X)) → U52#(X)
active#(U51(tt, V2)) → mark#(U52(isNatList(V2)))U93#(X1, active(X2), X3, X4) → U93#(X1, X2, X3, X4)
mark#(length(X)) → active#(length(mark(X)))U91#(X1, X2, X3, active(X4)) → U91#(X1, X2, X3, X4)
active#(take(0, IL)) → isNatIList#(IL)U92#(X1, X2, X3, mark(X4)) → U92#(X1, X2, X3, X4)
active#(U92(tt, IL, M, N)) → U93#(isNat(N), IL, M, N)active#(U92(tt, IL, M, N)) → mark#(U93(isNat(N), IL, M, N))
active#(U41(tt, V2)) → isNatIList#(V2)active#(length(nil)) → mark#(0)
U81#(active(X)) → U81#(X)U93#(X1, mark(X2), X3, X4) → U93#(X1, X2, X3, X4)
active#(isNat(length(V1))) → isNatList#(V1)active#(take(s(M), cons(N, IL))) → mark#(U91(isNatIList(IL), IL, M, N))
U72#(X1, active(X2)) → U72#(X1, X2)mark#(U42(X)) → U42#(mark(X))
mark#(U72(X1, X2)) → mark#(X1)active#(U71(tt, L, N)) → mark#(U72(isNat(N), L))
mark#(cons(X1, X2)) → mark#(X1)U71#(mark(X1), X2, X3) → U71#(X1, X2, X3)
mark#(U51(X1, X2)) → active#(U51(mark(X1), X2))active#(isNatList(take(V1, V2))) → mark#(U61(isNat(V1), V2))
U41#(active(X1), X2) → U41#(X1, X2)active#(isNatIList(cons(V1, V2))) → isNat#(V1)
mark#(U62(X)) → mark#(X)mark#(U31(X)) → mark#(X)
U92#(active(X1), X2, X3, X4) → U92#(X1, X2, X3, X4)U51#(X1, active(X2)) → U51#(X1, X2)
mark#(tt) → active#(tt)cons#(mark(X1), X2) → cons#(X1, X2)
active#(U61(tt, V2)) → mark#(U62(isNatIList(V2)))mark#(U61(X1, X2)) → U61#(mark(X1), X2)
mark#(U93(X1, X2, X3, X4)) → active#(U93(mark(X1), X2, X3, X4))mark#(U52(X)) → active#(U52(mark(X)))
active#(U41(tt, V2)) → U42#(isNatIList(V2))U62#(mark(X)) → U62#(X)
U61#(X1, active(X2)) → U61#(X1, X2)active#(U61(tt, V2)) → U62#(isNatIList(V2))
mark#(length(X)) → mark#(X)mark#(zeros) → active#(zeros)
U11#(mark(X)) → U11#(X)U92#(X1, X2, active(X3), X4) → U92#(X1, X2, X3, X4)
mark#(0) → active#(0)mark#(s(X)) → active#(s(mark(X)))
active#(isNat(s(V1))) → U21#(isNat(V1))U91#(X1, mark(X2), X3, X4) → U91#(X1, X2, X3, X4)
U71#(X1, X2, mark(X3)) → U71#(X1, X2, X3)active#(U91(tt, IL, M, N)) → isNat#(M)
mark#(U62(X)) → U62#(mark(X))mark#(U31(X)) → U31#(mark(X))
active#(zeros) → cons#(0, zeros)mark#(U72(X1, X2)) → U72#(mark(X1), X2)
U72#(X1, mark(X2)) → U72#(X1, X2)U92#(mark(X1), X2, X3, X4) → U92#(X1, X2, X3, X4)
mark#(U21(X)) → U21#(mark(X))mark#(cons(X1, X2)) → active#(cons(mark(X1), X2))
mark#(U71(X1, X2, X3)) → active#(U71(mark(X1), X2, X3))U11#(active(X)) → U11#(X)
active#(isNat(length(V1))) → mark#(U11(isNatList(V1)))U93#(active(X1), X2, X3, X4) → U93#(X1, X2, X3, X4)
U42#(active(X)) → U42#(X)mark#(U41(X1, X2)) → active#(U41(mark(X1), X2))
mark#(U52(X)) → U52#(mark(X))U42#(mark(X)) → U42#(X)
U91#(X1, X2, active(X3), X4) → U91#(X1, X2, X3, X4)mark#(U81(X)) → mark#(X)
length#(active(X)) → length#(X)U71#(X1, active(X2), X3) → U71#(X1, X2, X3)
active#(length(cons(N, L))) → U71#(isNatList(L), L, N)mark#(isNatIList(X)) → active#(isNatIList(X))
mark#(U71(X1, X2, X3)) → mark#(X1)isNatIList#(active(X)) → isNatIList#(X)
mark#(U92(X1, X2, X3, X4)) → active#(U92(mark(X1), X2, X3, X4))U92#(X1, X2, X3, active(X4)) → U92#(X1, X2, X3, X4)
active#(isNatList(take(V1, V2))) → U61#(isNat(V1), V2)mark#(U41(X1, X2)) → U41#(mark(X1), X2)
active#(isNatList(cons(V1, V2))) → isNat#(V1)mark#(U93(X1, X2, X3, X4)) → U93#(mark(X1), X2, X3, X4)
U31#(mark(X)) → U31#(X)mark#(isNat(X)) → active#(isNat(X))
U93#(mark(X1), X2, X3, X4) → U93#(X1, X2, X3, X4)U51#(active(X1), X2) → U51#(X1, X2)
mark#(U81(X)) → U81#(mark(X))mark#(U51(X1, X2)) → mark#(X1)
active#(U72(tt, L)) → mark#(s(length(L)))active#(U92(tt, IL, M, N)) → isNat#(N)
active#(isNatList(take(V1, V2))) → isNat#(V1)active#(U71(tt, L, N)) → isNat#(N)
mark#(U91(X1, X2, X3, X4)) → U91#(mark(X1), X2, X3, X4)U92#(X1, active(X2), X3, X4) → U92#(X1, X2, X3, X4)
U21#(mark(X)) → U21#(X)U21#(active(X)) → U21#(X)
mark#(U31(X)) → active#(U31(mark(X)))active#(isNat(s(V1))) → mark#(U21(isNat(V1)))
active#(take(0, IL)) → U81#(isNatIList(IL))mark#(U91(X1, X2, X3, X4)) → mark#(X1)
active#(U93(tt, IL, M, N)) → cons#(N, take(M, IL))mark#(take(X1, X2)) → mark#(X2)
active#(zeros) → mark#(cons(0, zeros))s#(active(X)) → s#(X)
U91#(X1, X2, mark(X3), X4) → U91#(X1, X2, X3, X4)U91#(X1, active(X2), X3, X4) → U91#(X1, X2, X3, X4)
mark#(isNatList(X)) → active#(isNatList(X))active#(U71(tt, L, N)) → U72#(isNat(N), L)
take#(active(X1), X2) → take#(X1, X2)U91#(X1, X2, X3, mark(X4)) → U91#(X1, X2, X3, X4)

Rewrite Rules

active(zeros) → mark(cons(0, zeros))active(U11(tt)) → mark(tt)
active(U21(tt)) → mark(tt)active(U31(tt)) → mark(tt)
active(U41(tt, V2)) → mark(U42(isNatIList(V2)))active(U42(tt)) → mark(tt)
active(U51(tt, V2)) → mark(U52(isNatList(V2)))active(U52(tt)) → mark(tt)
active(U61(tt, V2)) → mark(U62(isNatIList(V2)))active(U62(tt)) → mark(tt)
active(U71(tt, L, N)) → mark(U72(isNat(N), L))active(U72(tt, L)) → mark(s(length(L)))
active(U81(tt)) → mark(nil)active(U91(tt, IL, M, N)) → mark(U92(isNat(M), IL, M, N))
active(U92(tt, IL, M, N)) → mark(U93(isNat(N), IL, M, N))active(U93(tt, IL, M, N)) → mark(cons(N, take(M, IL)))
active(isNat(0)) → mark(tt)active(isNat(length(V1))) → mark(U11(isNatList(V1)))
active(isNat(s(V1))) → mark(U21(isNat(V1)))active(isNatIList(V)) → mark(U31(isNatList(V)))
active(isNatIList(zeros)) → mark(tt)active(isNatIList(cons(V1, V2))) → mark(U41(isNat(V1), V2))
active(isNatList(nil)) → mark(tt)active(isNatList(cons(V1, V2))) → mark(U51(isNat(V1), V2))
active(isNatList(take(V1, V2))) → mark(U61(isNat(V1), V2))active(length(nil)) → mark(0)
active(length(cons(N, L))) → mark(U71(isNatList(L), L, N))active(take(0, IL)) → mark(U81(isNatIList(IL)))
active(take(s(M), cons(N, IL))) → mark(U91(isNatIList(IL), IL, M, N))mark(zeros) → active(zeros)
mark(cons(X1, X2)) → active(cons(mark(X1), X2))mark(0) → active(0)
mark(U11(X)) → active(U11(mark(X)))mark(tt) → active(tt)
mark(U21(X)) → active(U21(mark(X)))mark(U31(X)) → active(U31(mark(X)))
mark(U41(X1, X2)) → active(U41(mark(X1), X2))mark(U42(X)) → active(U42(mark(X)))
mark(isNatIList(X)) → active(isNatIList(X))mark(U51(X1, X2)) → active(U51(mark(X1), X2))
mark(U52(X)) → active(U52(mark(X)))mark(isNatList(X)) → active(isNatList(X))
mark(U61(X1, X2)) → active(U61(mark(X1), X2))mark(U62(X)) → active(U62(mark(X)))
mark(U71(X1, X2, X3)) → active(U71(mark(X1), X2, X3))mark(U72(X1, X2)) → active(U72(mark(X1), X2))
mark(isNat(X)) → active(isNat(X))mark(s(X)) → active(s(mark(X)))
mark(length(X)) → active(length(mark(X)))mark(U81(X)) → active(U81(mark(X)))
mark(nil) → active(nil)mark(U91(X1, X2, X3, X4)) → active(U91(mark(X1), X2, X3, X4))
mark(U92(X1, X2, X3, X4)) → active(U92(mark(X1), X2, X3, X4))mark(U93(X1, X2, X3, X4)) → active(U93(mark(X1), X2, X3, X4))
mark(take(X1, X2)) → active(take(mark(X1), mark(X2)))cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)U11(mark(X)) → U11(X)
U11(active(X)) → U11(X)U21(mark(X)) → U21(X)
U21(active(X)) → U21(X)U31(mark(X)) → U31(X)
U31(active(X)) → U31(X)U41(mark(X1), X2) → U41(X1, X2)
U41(X1, mark(X2)) → U41(X1, X2)U41(active(X1), X2) → U41(X1, X2)
U41(X1, active(X2)) → U41(X1, X2)U42(mark(X)) → U42(X)
U42(active(X)) → U42(X)isNatIList(mark(X)) → isNatIList(X)
isNatIList(active(X)) → isNatIList(X)U51(mark(X1), X2) → U51(X1, X2)
U51(X1, mark(X2)) → U51(X1, X2)U51(active(X1), X2) → U51(X1, X2)
U51(X1, active(X2)) → U51(X1, X2)U52(mark(X)) → U52(X)
U52(active(X)) → U52(X)isNatList(mark(X)) → isNatList(X)
isNatList(active(X)) → isNatList(X)U61(mark(X1), X2) → U61(X1, X2)
U61(X1, mark(X2)) → U61(X1, X2)U61(active(X1), X2) → U61(X1, X2)
U61(X1, active(X2)) → U61(X1, X2)U62(mark(X)) → U62(X)
U62(active(X)) → U62(X)U71(mark(X1), X2, X3) → U71(X1, X2, X3)
U71(X1, mark(X2), X3) → U71(X1, X2, X3)U71(X1, X2, mark(X3)) → U71(X1, X2, X3)
U71(active(X1), X2, X3) → U71(X1, X2, X3)U71(X1, active(X2), X3) → U71(X1, X2, X3)
U71(X1, X2, active(X3)) → U71(X1, X2, X3)U72(mark(X1), X2) → U72(X1, X2)
U72(X1, mark(X2)) → U72(X1, X2)U72(active(X1), X2) → U72(X1, X2)
U72(X1, active(X2)) → U72(X1, X2)isNat(mark(X)) → isNat(X)
isNat(active(X)) → isNat(X)s(mark(X)) → s(X)
s(active(X)) → s(X)length(mark(X)) → length(X)
length(active(X)) → length(X)U81(mark(X)) → U81(X)
U81(active(X)) → U81(X)U91(mark(X1), X2, X3, X4) → U91(X1, X2, X3, X4)
U91(X1, mark(X2), X3, X4) → U91(X1, X2, X3, X4)U91(X1, X2, mark(X3), X4) → U91(X1, X2, X3, X4)
U91(X1, X2, X3, mark(X4)) → U91(X1, X2, X3, X4)U91(active(X1), X2, X3, X4) → U91(X1, X2, X3, X4)
U91(X1, active(X2), X3, X4) → U91(X1, X2, X3, X4)U91(X1, X2, active(X3), X4) → U91(X1, X2, X3, X4)
U91(X1, X2, X3, active(X4)) → U91(X1, X2, X3, X4)U92(mark(X1), X2, X3, X4) → U92(X1, X2, X3, X4)
U92(X1, mark(X2), X3, X4) → U92(X1, X2, X3, X4)U92(X1, X2, mark(X3), X4) → U92(X1, X2, X3, X4)
U92(X1, X2, X3, mark(X4)) → U92(X1, X2, X3, X4)U92(active(X1), X2, X3, X4) → U92(X1, X2, X3, X4)
U92(X1, active(X2), X3, X4) → U92(X1, X2, X3, X4)U92(X1, X2, active(X3), X4) → U92(X1, X2, X3, X4)
U92(X1, X2, X3, active(X4)) → U92(X1, X2, X3, X4)U93(mark(X1), X2, X3, X4) → U93(X1, X2, X3, X4)
U93(X1, mark(X2), X3, X4) → U93(X1, X2, X3, X4)U93(X1, X2, mark(X3), X4) → U93(X1, X2, X3, X4)
U93(X1, X2, X3, mark(X4)) → U93(X1, X2, X3, X4)U93(active(X1), X2, X3, X4) → U93(X1, X2, X3, X4)
U93(X1, active(X2), X3, X4) → U93(X1, X2, X3, X4)U93(X1, X2, active(X3), X4) → U93(X1, X2, X3, X4)
U93(X1, X2, X3, active(X4)) → U93(X1, X2, X3, X4)take(mark(X1), X2) → take(X1, X2)
take(X1, mark(X2)) → take(X1, X2)take(active(X1), X2) → take(X1, X2)
take(X1, active(X2)) → take(X1, X2)

Original Signature

Termination of terms over the following signature is verified: isNat, U62, U61, U93, U42, U41, U92, U91, length, U21, cons, isNatIList, mark, U71, U72, 0, isNatList, U51, s, tt, zeros, take, U52, U81, U11, active, U31, nil