0 QTRS
↳1 QTRSRRRProof (⇔)
↳2 QTRS
↳3 DependencyPairsProof (⇔)
↳4 QDP
↳5 DependencyGraphProof (⇔)
↳6 AND
↳7 QDP
↳8 UsableRulesProof (⇔)
↳9 QDP
↳10 UsableRulesReductionPairsProof (⇔)
↳11 QDP
↳12 DependencyGraphProof (⇔)
↳13 QDP
↳14 UsableRulesProof (⇔)
↳15 QDP
↳16 QDPSizeChangeProof (⇔)
↳17 TRUE
↳18 QDP
↳19 UsableRulesProof (⇔)
↳20 QDP
↳21 UsableRulesReductionPairsProof (⇔)
↳22 QDP
↳23 Narrowing (⇔)
↳24 QDP
↳25 Narrowing (⇔)
↳26 QDP
↳27 DependencyGraphProof (⇔)
↳28 QDP
↳29 MRRProof (⇔)
↳30 QDP
↳31 NonTerminationProof (⇔)
↳32 FALSE
zeros → cons(0, n__zeros)
U11(tt, L) → U12(tt, activate(L))
U12(tt, L) → s(length(activate(L)))
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
length(nil) → 0
length(cons(N, L)) → U11(tt, activate(L))
take(0, IL) → nil
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
POL(0) = 0
POL(U11(x1, x2)) = x1 + x2
POL(U12(x1, x2)) = x1 + x2
POL(U21(x1, x2, x3, x4)) = x1 + x2 + x3 + x4
POL(U22(x1, x2, x3, x4)) = x1 + x2 + x3 + x4
POL(U23(x1, x2, x3, x4)) = x1 + x2 + x3 + x4
POL(activate(x1)) = x1
POL(cons(x1, x2)) = x1 + x2
POL(length(x1)) = 1 + x1
POL(n__take(x1, x2)) = 1 + x1 + x2
POL(n__zeros) = 0
POL(nil) = 0
POL(s(x1)) = x1
POL(take(x1, x2)) = 1 + x1 + x2
POL(tt) = 1
POL(zeros) = 0
length(nil) → 0
take(0, IL) → nil
zeros → cons(0, n__zeros)
U11(tt, L) → U12(tt, activate(L))
U12(tt, L) → s(length(activate(L)))
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
length(cons(N, L)) → U11(tt, activate(L))
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
U111(tt, L) → U121(tt, activate(L))
U111(tt, L) → ACTIVATE(L)
U121(tt, L) → LENGTH(activate(L))
U121(tt, L) → ACTIVATE(L)
U211(tt, IL, M, N) → U221(tt, activate(IL), activate(M), activate(N))
U211(tt, IL, M, N) → ACTIVATE(IL)
U211(tt, IL, M, N) → ACTIVATE(M)
U211(tt, IL, M, N) → ACTIVATE(N)
U221(tt, IL, M, N) → U231(tt, activate(IL), activate(M), activate(N))
U221(tt, IL, M, N) → ACTIVATE(IL)
U221(tt, IL, M, N) → ACTIVATE(M)
U221(tt, IL, M, N) → ACTIVATE(N)
U231(tt, IL, M, N) → ACTIVATE(N)
U231(tt, IL, M, N) → ACTIVATE(M)
U231(tt, IL, M, N) → ACTIVATE(IL)
LENGTH(cons(N, L)) → U111(tt, activate(L))
LENGTH(cons(N, L)) → ACTIVATE(L)
TAKE(s(M), cons(N, IL)) → U211(tt, activate(IL), M, N)
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
ACTIVATE(n__zeros) → ZEROS
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
zeros → cons(0, n__zeros)
U11(tt, L) → U12(tt, activate(L))
U12(tt, L) → s(length(activate(L)))
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
length(cons(N, L)) → U11(tt, activate(L))
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
U221(tt, IL, M, N) → U231(tt, activate(IL), activate(M), activate(N))
U231(tt, IL, M, N) → ACTIVATE(N)
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
TAKE(s(M), cons(N, IL)) → U211(tt, activate(IL), M, N)
U211(tt, IL, M, N) → U221(tt, activate(IL), activate(M), activate(N))
U221(tt, IL, M, N) → ACTIVATE(IL)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
U221(tt, IL, M, N) → ACTIVATE(M)
U221(tt, IL, M, N) → ACTIVATE(N)
U211(tt, IL, M, N) → ACTIVATE(IL)
U211(tt, IL, M, N) → ACTIVATE(M)
U211(tt, IL, M, N) → ACTIVATE(N)
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
U231(tt, IL, M, N) → ACTIVATE(M)
U231(tt, IL, M, N) → ACTIVATE(IL)
zeros → cons(0, n__zeros)
U11(tt, L) → U12(tt, activate(L))
U12(tt, L) → s(length(activate(L)))
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
length(cons(N, L)) → U11(tt, activate(L))
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
U221(tt, IL, M, N) → U231(tt, activate(IL), activate(M), activate(N))
U231(tt, IL, M, N) → ACTIVATE(N)
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
TAKE(s(M), cons(N, IL)) → U211(tt, activate(IL), M, N)
U211(tt, IL, M, N) → U221(tt, activate(IL), activate(M), activate(N))
U221(tt, IL, M, N) → ACTIVATE(IL)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
U221(tt, IL, M, N) → ACTIVATE(M)
U221(tt, IL, M, N) → ACTIVATE(N)
U211(tt, IL, M, N) → ACTIVATE(IL)
U211(tt, IL, M, N) → ACTIVATE(M)
U211(tt, IL, M, N) → ACTIVATE(N)
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
U231(tt, IL, M, N) → ACTIVATE(M)
U231(tt, IL, M, N) → ACTIVATE(IL)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
take(X1, X2) → n__take(X1, X2)
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
zeros → cons(0, n__zeros)
zeros → n__zeros
The following rules are removed from R:
TAKE(s(M), cons(N, IL)) → U211(tt, activate(IL), M, N)
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
Used ordering: POLO with Polynomial interpretation [POLO]:
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
POL(0) = 0
POL(ACTIVATE(x1)) = x1
POL(TAKE(x1, x2)) = x1 + 2·x2
POL(U21(x1, x2, x3, x4)) = 2·x1 + 2·x2 + 2·x3 + 2·x4
POL(U211(x1, x2, x3, x4)) = 2·x1 + x2 + x3 + 2·x4
POL(U22(x1, x2, x3, x4)) = 2·x1 + 2·x2 + 2·x3 + 2·x4
POL(U221(x1, x2, x3, x4)) = 2·x1 + x2 + x3 + x4
POL(U23(x1, x2, x3, x4)) = 2·x1 + 2·x2 + 2·x3 + 2·x4
POL(U231(x1, x2, x3, x4)) = x1 + x2 + x3 + x4
POL(activate(x1)) = x1
POL(cons(x1, x2)) = x1 + x2
POL(n__take(x1, x2)) = x1 + 2·x2
POL(n__zeros) = 0
POL(s(x1)) = 2·x1
POL(take(x1, x2)) = x1 + 2·x2
POL(tt) = 0
POL(zeros) = 0
U221(tt, IL, M, N) → U231(tt, activate(IL), activate(M), activate(N))
U231(tt, IL, M, N) → ACTIVATE(N)
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
U211(tt, IL, M, N) → U221(tt, activate(IL), activate(M), activate(N))
U221(tt, IL, M, N) → ACTIVATE(IL)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
U221(tt, IL, M, N) → ACTIVATE(M)
U221(tt, IL, M, N) → ACTIVATE(N)
U211(tt, IL, M, N) → ACTIVATE(IL)
U211(tt, IL, M, N) → ACTIVATE(M)
U211(tt, IL, M, N) → ACTIVATE(N)
U231(tt, IL, M, N) → ACTIVATE(M)
U231(tt, IL, M, N) → ACTIVATE(IL)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
zeros → cons(0, n__zeros)
zeros → n__zeros
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
zeros → cons(0, n__zeros)
zeros → n__zeros
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
From the DPs we obtained the following set of size-change graphs:
U121(tt, L) → LENGTH(activate(L))
LENGTH(cons(N, L)) → U111(tt, activate(L))
U111(tt, L) → U121(tt, activate(L))
zeros → cons(0, n__zeros)
U11(tt, L) → U12(tt, activate(L))
U12(tt, L) → s(length(activate(L)))
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
length(cons(N, L)) → U11(tt, activate(L))
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
U121(tt, L) → LENGTH(activate(L))
LENGTH(cons(N, L)) → U111(tt, activate(L))
U111(tt, L) → U121(tt, activate(L))
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
take(X1, X2) → n__take(X1, X2)
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
zeros → cons(0, n__zeros)
zeros → n__zeros
Used ordering: POLO with Polynomial interpretation [POLO]:
take(s(M), cons(N, IL)) → U21(tt, activate(IL), M, N)
U21(tt, IL, M, N) → U22(tt, activate(IL), activate(M), activate(N))
U22(tt, IL, M, N) → U23(tt, activate(IL), activate(M), activate(N))
U23(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
POL(0) = 0
POL(LENGTH(x1)) = 1 + 2·x1
POL(U111(x1, x2)) = x1 + 2·x2
POL(U121(x1, x2)) = x1 + 2·x2
POL(U21(x1, x2, x3, x4)) = 2 + 2·x1 + x2 + 2·x3 + 2·x4
POL(U22(x1, x2, x3, x4)) = 2 + x1 + x2 + 2·x3 + 2·x4
POL(U23(x1, x2, x3, x4)) = 1 + x1 + x2 + 2·x3 + 2·x4
POL(activate(x1)) = x1
POL(cons(x1, x2)) = 2·x1 + x2
POL(n__take(x1, x2)) = 2·x1 + x2
POL(n__zeros) = 0
POL(s(x1)) = 2 + x1
POL(take(x1, x2)) = 2·x1 + x2
POL(tt) = 1
POL(zeros) = 0
U121(tt, L) → LENGTH(activate(L))
LENGTH(cons(N, L)) → U111(tt, activate(L))
U111(tt, L) → U121(tt, activate(L))
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros
U121(tt, n__zeros) → LENGTH(zeros)
U121(tt, n__take(x0, x1)) → LENGTH(take(activate(x0), activate(x1)))
U121(tt, x0) → LENGTH(x0)
LENGTH(cons(N, L)) → U111(tt, activate(L))
U111(tt, L) → U121(tt, activate(L))
U121(tt, n__zeros) → LENGTH(zeros)
U121(tt, n__take(x0, x1)) → LENGTH(take(activate(x0), activate(x1)))
U121(tt, x0) → LENGTH(x0)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros
U121(tt, n__zeros) → LENGTH(cons(0, n__zeros))
U121(tt, n__zeros) → LENGTH(n__zeros)
LENGTH(cons(N, L)) → U111(tt, activate(L))
U111(tt, L) → U121(tt, activate(L))
U121(tt, n__take(x0, x1)) → LENGTH(take(activate(x0), activate(x1)))
U121(tt, x0) → LENGTH(x0)
U121(tt, n__zeros) → LENGTH(cons(0, n__zeros))
U121(tt, n__zeros) → LENGTH(n__zeros)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros
U111(tt, L) → U121(tt, activate(L))
U121(tt, n__take(x0, x1)) → LENGTH(take(activate(x0), activate(x1)))
LENGTH(cons(N, L)) → U111(tt, activate(L))
U121(tt, x0) → LENGTH(x0)
U121(tt, n__zeros) → LENGTH(cons(0, n__zeros))
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros
U121(tt, n__take(x0, x1)) → LENGTH(take(activate(x0), activate(x1)))
POL(0) = 0
POL(LENGTH(x1)) = x1
POL(U111(x1, x2)) = 2·x1 + 2·x2
POL(U121(x1, x2)) = 2·x1 + 2·x2
POL(activate(x1)) = x1
POL(cons(x1, x2)) = 2·x1 + 2·x2
POL(n__take(x1, x2)) = 1 + 2·x1 + 2·x2
POL(n__zeros) = 0
POL(take(x1, x2)) = 1 + 2·x1 + 2·x2
POL(tt) = 0
POL(zeros) = 0
U111(tt, L) → U121(tt, activate(L))
LENGTH(cons(N, L)) → U111(tt, activate(L))
U121(tt, x0) → LENGTH(x0)
U121(tt, n__zeros) → LENGTH(cons(0, n__zeros))
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros