0 QTRS
↳1 QTRSRRRProof (⇔, 82 ms)
↳2 QTRS
↳3 QTRSRRRProof (⇔, 35 ms)
↳4 QTRS
↳5 QTRSRRRProof (⇔, 0 ms)
↳6 QTRS
↳7 DependencyPairsProof (⇔, 0 ms)
↳8 QDP
↳9 DependencyGraphProof (⇔, 0 ms)
↳10 AND
↳11 QDP
↳12 UsableRulesProof (⇔, 0 ms)
↳13 QDP
↳14 UsableRulesReductionPairsProof (⇔, 0 ms)
↳15 QDP
↳16 DependencyGraphProof (⇔, 0 ms)
↳17 QDP
↳18 UsableRulesProof (⇔, 0 ms)
↳19 QDP
↳20 QDPSizeChangeProof (⇔, 0 ms)
↳21 YES
↳22 QDP
↳23 NonLoopProof (⇔, 317 ms)
↳24 NO
zeros → cons(0, n__zeros)
and(tt, X) → activate(X)
length(nil) → 0
length(cons(N, L)) → s(length(activate(L)))
take(0, IL) → nil
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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(activate(x1)) = x1
POL(and(x1, x2)) = 2 + 2·x1 + x2
POL(cons(x1, x2)) = 2·x1 + x2
POL(length(x1)) = 2·x1
POL(n__take(x1, x2)) = x1 + 2·x2
POL(n__zeros) = 0
POL(nil) = 0
POL(s(x1)) = x1
POL(take(x1, x2)) = x1 + 2·x2
POL(tt) = 2
POL(zeros) = 0
and(tt, X) → activate(X)
zeros → cons(0, n__zeros)
length(nil) → 0
length(cons(N, L)) → s(length(activate(L)))
take(0, IL) → nil
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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(activate(x1)) = x1
POL(cons(x1, x2)) = 2·x1 + x2
POL(length(x1)) = 2 + 2·x1
POL(n__take(x1, x2)) = x1 + 2·x2
POL(n__zeros) = 0
POL(nil) = 0
POL(s(x1)) = x1
POL(take(x1, x2)) = x1 + 2·x2
POL(zeros) = 0
length(nil) → 0
zeros → cons(0, n__zeros)
length(cons(N, L)) → s(length(activate(L)))
take(0, IL) → nil
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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(activate(x1)) = x1
POL(cons(x1, x2)) = x1 + x2
POL(length(x1)) = 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(zeros) = 0
take(0, IL) → nil
zeros → cons(0, n__zeros)
length(cons(N, L)) → s(length(activate(L)))
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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
LENGTH(cons(N, L)) → LENGTH(activate(L))
LENGTH(cons(N, L)) → ACTIVATE(L)
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)
length(cons(N, L)) → s(length(activate(L)))
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
zeros → cons(0, n__zeros)
length(cons(N, L)) → s(length(activate(L)))
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(X) → X
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
take(X1, X2) → n__take(X1, X2)
zeros → cons(0, n__zeros)
zeros → n__zeros
The following rules are removed from R:
TAKE(s(M), cons(N, IL)) → ACTIVATE(IL)
Used ordering: POLO with Polynomial interpretation [POLO]:
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
POL(0) = 0
POL(ACTIVATE(x1)) = 2·x1
POL(TAKE(x1, x2)) = x1 + 2·x2
POL(activate(x1)) = x1
POL(cons(x1, x2)) = x1 + x2
POL(n__take(x1, x2)) = 2·x1 + 2·x2
POL(n__zeros) = 0
POL(s(x1)) = 2 + 2·x1
POL(take(x1, x2)) = 2·x1 + 2·x2
POL(zeros) = 0
ACTIVATE(n__take(X1, X2)) → TAKE(activate(X1), activate(X2))
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__take(X1, X2)) → ACTIVATE(X2)
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
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)
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:
LENGTH(cons(N, L)) → LENGTH(activate(L))
zeros → cons(0, n__zeros)
length(cons(N, L)) → s(length(activate(L)))
take(s(M), cons(N, IL)) → cons(N, n__take(M, activate(IL)))
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