YES(O(1), O(n^1)) 5.85/1.97 YES(O(1), O(n^1)) 6.67/2.16 6.67/2.16 6.67/2.16 6.67/2.16 6.67/2.16 6.67/2.16 Runtime Complexity (innermost) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml.xml 6.67/2.16 6.67/2.16 6.67/2.16
6.67/2.16
6.67/2.16
6.67/2.16
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

0 CpxTRS
6.67/2.16 
↳1 CpxTrsToCdtProof (BOTH BOUNDS(ID, ID))
6.67/2.16 
↳2 CdtProblem
6.67/2.16 
↳3 CdtUnreachableProof (⇔)
6.67/2.16 
↳4 CdtProblem
6.67/2.16 
↳5 CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
6.67/2.16 
↳6 CdtProblem
6.67/2.16 
↳7 CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
6.67/2.16 
↳8 CdtProblem
6.67/2.16 
↳9 CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
6.67/2.16 
↳10 CdtProblem
6.67/2.16 
↳11 CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
6.67/2.16 
↳12 CdtProblem
6.67/2.16 
↳13 CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))))
6.67/2.16 
↳14 CdtProblem
6.67/2.16 
↳15 CdtKnowledgeProof (⇔)
6.67/2.16 
↳16 BOUNDS(O(1), O(1))
6.67/2.16
6.67/2.16 6.67/2.16
6.67/2.16
6.67/2.16

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

__(__(X, Y), Z) → __(X, __(Y, Z)) 6.67/2.16
__(X, nil) → X 6.67/2.16
__(nil, X) → X 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, V2) → U22(isList(activate(V2))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, V2) → U42(isNeList(activate(V2))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, V2) → U52(isList(activate(V2))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, P) → U72(isPal(activate(P))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(V) → U11(isNeList(activate(V))) 6.67/2.16
isList(n__nil) → tt 6.67/2.16
isList(n____(V1, V2)) → U21(isList(activate(V1)), activate(V2)) 6.67/2.16
isNeList(V) → U31(isQid(activate(V))) 6.67/2.16
isNeList(n____(V1, V2)) → U41(isList(activate(V1)), activate(V2)) 6.67/2.16
isNeList(n____(V1, V2)) → U51(isNeList(activate(V1)), activate(V2)) 6.67/2.16
isNePal(V) → U61(isQid(activate(V))) 6.67/2.16
isNePal(n____(I, __(P, I))) → U71(isQid(activate(I)), activate(P)) 6.67/2.16
isPal(V) → U81(isNePal(activate(V))) 6.67/2.16
isPal(n__nil) → tt 6.67/2.16
isQid(n__a) → tt 6.67/2.16
isQid(n__e) → tt 6.67/2.16
isQid(n__i) → tt 6.67/2.16
isQid(n__o) → tt 6.67/2.16
isQid(n__u) → tt 6.67/2.16
nil → n__nil 6.67/2.16
__(X1, X2) → n____(X1, X2) 6.67/2.16
a → n__a 6.67/2.16
e → n__e 6.67/2.16
i → n__i 6.67/2.16
o → n__o 6.67/2.16
u → n__u 6.67/2.16
activate(n__nil) → nil 6.67/2.16
activate(n____(X1, X2)) → __(X1, X2) 6.67/2.16
activate(n__a) → a 6.67/2.16
activate(n__e) → e 6.67/2.16
activate(n__i) → i 6.67/2.16
activate(n__o) → o 6.67/2.16
activate(n__u) → u 6.67/2.16
activate(X) → X

Rewrite Strategy: INNERMOST
6.67/2.16
6.67/2.16

(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

Converted CpxTRS to CDT
6.67/2.16
6.67/2.16

(2) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.16
__(z0, nil) → z0 6.67/2.16
__(nil, z0) → z0 6.67/2.16
__(z0, z1) → n____(z0, z1) 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.16
isList(n__nil) → tt 6.67/2.16
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.16
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.16
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.16
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.16
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.16
isPal(n__nil) → tt 6.67/2.16
isQid(n__a) → tt 6.67/2.16
isQid(n__e) → tt 6.67/2.16
isQid(n__i) → tt 6.67/2.16
isQid(n__o) → tt 6.67/2.16
isQid(n__u) → tt 6.67/2.16
nil → n__nil 6.67/2.16
a → n__a 6.67/2.16
e → n__e 6.67/2.16
i → n__i 6.67/2.16
o → n__o 6.67/2.16
u → n__u 6.67/2.16
activate(n__nil) → nil 6.67/2.16
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.16
activate(n__a) → a 6.67/2.16
activate(n__e) → e 6.67/2.16
activate(n__i) → i 6.67/2.16
activate(n__o) → o 6.67/2.16
activate(n__u) → u 6.67/2.16
activate(z0) → z0
Tuples:

__'(__(z0, z1), z2) → c(__'(z0, __(z1, z2)), __'(z1, z2)) 6.67/2.16
U21'(tt, z0) → c5(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(z0) → c19(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNEPAL(z0) → c22(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNEPAL(n____(z0, __(z1, z0))) → c23(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISPAL(z0) → c24(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37(NIL) 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38(__'(z0, z1)) 6.67/2.16
ACTIVATE(n__a) → c39(A) 6.67/2.16
ACTIVATE(n__e) → c40(E) 6.67/2.16
ACTIVATE(n__i) → c41(I) 6.67/2.16
ACTIVATE(n__o) → c42(O) 6.67/2.16
ACTIVATE(n__u) → c43(U)
S tuples:

__'(__(z0, z1), z2) → c(__'(z0, __(z1, z2)), __'(z1, z2)) 6.67/2.16
U21'(tt, z0) → c5(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(z0) → c19(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNEPAL(z0) → c22(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNEPAL(n____(z0, __(z1, z0))) → c23(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISPAL(z0) → c24(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37(NIL) 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38(__'(z0, z1)) 6.67/2.16
ACTIVATE(n__a) → c39(A) 6.67/2.16
ACTIVATE(n__e) → c40(E) 6.67/2.16
ACTIVATE(n__i) → c41(I) 6.67/2.16
ACTIVATE(n__o) → c42(O) 6.67/2.16
ACTIVATE(n__u) → c43(U)
K tuples:none
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

__', U21', U41', U51', U71', ISLIST, ISNELIST, ISNEPAL, ISPAL, ACTIVATE

Compound Symbols:

c, c5, c8, c10, c13, c16, c18, c19, c20, c21, c22, c23, c24, c37, c38, c39, c40, c41, c42, c43

6.67/2.16
6.67/2.16

(3) CdtUnreachableProof (EQUIVALENT transformation)

The following tuples could be removed as they are not reachable from basic start terms:

__'(__(z0, z1), z2) → c(__'(z0, __(z1, z2)), __'(z1, z2)) 6.67/2.16
ISNEPAL(n____(z0, __(z1, z0))) → c23(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
6.67/2.16
6.67/2.16

(4) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.16
__(z0, nil) → z0 6.67/2.16
__(nil, z0) → z0 6.67/2.16
__(z0, z1) → n____(z0, z1) 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.16
isList(n__nil) → tt 6.67/2.16
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.16
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.16
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.16
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.16
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.16
isPal(n__nil) → tt 6.67/2.16
isQid(n__a) → tt 6.67/2.16
isQid(n__e) → tt 6.67/2.16
isQid(n__i) → tt 6.67/2.16
isQid(n__o) → tt 6.67/2.16
isQid(n__u) → tt 6.67/2.16
nil → n__nil 6.67/2.16
a → n__a 6.67/2.16
e → n__e 6.67/2.16
i → n__i 6.67/2.16
o → n__o 6.67/2.16
u → n__u 6.67/2.16
activate(n__nil) → nil 6.67/2.16
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.16
activate(n__a) → a 6.67/2.16
activate(n__e) → e 6.67/2.16
activate(n__i) → i 6.67/2.16
activate(n__o) → o 6.67/2.16
activate(n__u) → u 6.67/2.16
activate(z0) → z0
Tuples:

U21'(tt, z0) → c5(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(z0) → c19(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNEPAL(z0) → c22(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c24(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37(NIL) 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38(__'(z0, z1)) 6.67/2.16
ACTIVATE(n__a) → c39(A) 6.67/2.16
ACTIVATE(n__e) → c40(E) 6.67/2.16
ACTIVATE(n__i) → c41(I) 6.67/2.16
ACTIVATE(n__o) → c42(O) 6.67/2.16
ACTIVATE(n__u) → c43(U)
S tuples:

U21'(tt, z0) → c5(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(z0) → c19(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNEPAL(z0) → c22(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c24(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37(NIL) 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38(__'(z0, z1)) 6.67/2.16
ACTIVATE(n__a) → c39(A) 6.67/2.16
ACTIVATE(n__e) → c40(E) 6.67/2.16
ACTIVATE(n__i) → c41(I) 6.67/2.16
ACTIVATE(n__o) → c42(O) 6.67/2.16
ACTIVATE(n__u) → c43(U)
K tuples:none
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

U21', U41', U51', U71', ISLIST, ISNELIST, ISNEPAL, ISPAL, ACTIVATE

Compound Symbols:

c5, c8, c10, c13, c16, c18, c19, c20, c21, c22, c24, c37, c38, c39, c40, c41, c42, c43

6.67/2.16
6.67/2.16

(5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID) transformation)

Removed 17 trailing tuple parts
6.67/2.16
6.67/2.16

(6) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.16
__(z0, nil) → z0 6.67/2.16
__(nil, z0) → z0 6.67/2.16
__(z0, z1) → n____(z0, z1) 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.16
isList(n__nil) → tt 6.67/2.16
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.16
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.16
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.16
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.16
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.16
isPal(n__nil) → tt 6.67/2.16
isQid(n__a) → tt 6.67/2.16
isQid(n__e) → tt 6.67/2.16
isQid(n__i) → tt 6.67/2.16
isQid(n__o) → tt 6.67/2.16
isQid(n__u) → tt 6.67/2.16
nil → n__nil 6.67/2.16
a → n__a 6.67/2.16
e → n__e 6.67/2.16
i → n__i 6.67/2.16
o → n__o 6.67/2.16
u → n__u 6.67/2.16
activate(n__nil) → nil 6.67/2.16
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.16
activate(n__a) → a 6.67/2.16
activate(n__e) → e 6.67/2.16
activate(n__i) → i 6.67/2.16
activate(n__o) → o 6.67/2.16
activate(n__u) → u 6.67/2.16
activate(z0) → z0
Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.16
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c24(ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38 6.67/2.16
ACTIVATE(n__a) → c39 6.67/2.16
ACTIVATE(n__e) → c40 6.67/2.16
ACTIVATE(n__i) → c41 6.67/2.16
ACTIVATE(n__o) → c42 6.67/2.16
ACTIVATE(n__u) → c43
S tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c13(ISPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.16
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c24(ISNEPAL(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38 6.67/2.16
ACTIVATE(n__a) → c39 6.67/2.16
ACTIVATE(n__e) → c40 6.67/2.16
ACTIVATE(n__i) → c41 6.67/2.16
ACTIVATE(n__o) → c42 6.67/2.16
ACTIVATE(n__u) → c43
K tuples:none
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

ISLIST, ISNELIST, U21', U41', U51', U71', ISNEPAL, ISPAL, ACTIVATE

Compound Symbols:

c18, c20, c21, c5, c8, c10, c13, c16, c19, c22, c24, c37, c38, c39, c40, c41, c42, c43

6.67/2.16
6.67/2.16

(7) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID) transformation)

Split RHS of tuples not part of any SCC
6.67/2.16
6.67/2.16

(8) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.16
__(z0, nil) → z0 6.67/2.16
__(nil, z0) → z0 6.67/2.16
__(z0, z1) → n____(z0, z1) 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.16
isList(n__nil) → tt 6.67/2.16
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.16
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.16
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.16
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.16
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.16
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.16
isPal(n__nil) → tt 6.67/2.16
isQid(n__a) → tt 6.67/2.16
isQid(n__e) → tt 6.67/2.16
isQid(n__i) → tt 6.67/2.16
isQid(n__o) → tt 6.67/2.16
isQid(n__u) → tt 6.67/2.16
nil → n__nil 6.67/2.16
a → n__a 6.67/2.16
e → n__e 6.67/2.16
i → n__i 6.67/2.16
o → n__o 6.67/2.16
u → n__u 6.67/2.16
activate(n__nil) → nil 6.67/2.16
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.16
activate(n__a) → a 6.67/2.16
activate(n__e) → e 6.67/2.16
activate(n__i) → i 6.67/2.16
activate(n__o) → o 6.67/2.16
activate(n__u) → u 6.67/2.16
activate(z0) → z0
Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.16
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38 6.67/2.16
ACTIVATE(n__a) → c39 6.67/2.16
ACTIVATE(n__e) → c40 6.67/2.16
ACTIVATE(n__i) → c41 6.67/2.16
ACTIVATE(n__o) → c42 6.67/2.16
ACTIVATE(n__u) → c43 6.67/2.16
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.16
U71'(tt, z0) → c(ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.16
ISPAL(z0) → c(ACTIVATE(z0))
S tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.16
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.16
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.16
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__nil) → c37 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38 6.67/2.16
ACTIVATE(n__a) → c39 6.67/2.16
ACTIVATE(n__e) → c40 6.67/2.16
ACTIVATE(n__i) → c41 6.67/2.16
ACTIVATE(n__o) → c42 6.67/2.16
ACTIVATE(n__u) → c43 6.67/2.16
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.16
U71'(tt, z0) → c(ACTIVATE(z0)) 6.67/2.16
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.16
ISPAL(z0) → c(ACTIVATE(z0))
K tuples:none
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

ISLIST, ISNELIST, U21', U41', U51', ISNEPAL, ACTIVATE, U71', ISPAL

Compound Symbols:

c18, c20, c21, c5, c8, c10, c16, c19, c22, c37, c38, c39, c40, c41, c42, c43, c

6.67/2.16
6.67/2.16

(9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

Removed 13 trailing nodes:

ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__u) → c43 6.67/2.16
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.16
ACTIVATE(n__e) → c40 6.67/2.16
ACTIVATE(n__a) → c39 6.67/2.16
ACTIVATE(n__o) → c42 6.67/2.16
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.16
U71'(tt, z0) → c(ACTIVATE(z0)) 6.67/2.16
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.16
ACTIVATE(n__nil) → c37 6.67/2.16
ACTIVATE(n__i) → c41 6.67/2.16
ACTIVATE(n____(z0, z1)) → c38 6.67/2.16
ISPAL(z0) → c(ACTIVATE(z0))
6.67/2.16
6.67/2.16

(10) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.16
__(z0, nil) → z0 6.67/2.16
__(nil, z0) → z0 6.67/2.16
__(z0, z1) → n____(z0, z1) 6.67/2.16
U11(tt) → tt 6.67/2.16
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.16
U22(tt) → tt 6.67/2.16
U31(tt) → tt 6.67/2.16
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.16
U42(tt) → tt 6.67/2.16
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.16
U52(tt) → tt 6.67/2.16
U61(tt) → tt 6.67/2.16
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.16
U72(tt) → tt 6.67/2.16
U81(tt) → tt 6.67/2.16
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.17
isList(n__nil) → tt 6.67/2.17
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.17
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.17
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.17
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.17
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.17
isPal(n__nil) → tt 6.67/2.17
isQid(n__a) → tt 6.67/2.17
isQid(n__e) → tt 6.67/2.17
isQid(n__i) → tt 6.67/2.17
isQid(n__o) → tt 6.67/2.17
isQid(n__u) → tt 6.67/2.17
nil → n__nil 6.67/2.17
a → n__a 6.67/2.17
e → n__e 6.67/2.17
i → n__i 6.67/2.17
o → n__o 6.67/2.17
u → n__u 6.67/2.17
activate(n__nil) → nil 6.67/2.17
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.17
activate(n__a) → a 6.67/2.17
activate(n__e) → e 6.67/2.17
activate(n__i) → i 6.67/2.17
activate(n__o) → o 6.67/2.17
activate(n__u) → u 6.67/2.17
activate(z0) → z0
Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0))
S tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0))
K tuples:none
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

ISLIST, ISNELIST, U21', U41', U51', ISNEPAL, ACTIVATE, U71', ISPAL

Compound Symbols:

c18, c20, c21, c5, c8, c10, c16, c19, c22, c37, c38, c39, c40, c41, c42, c43, c

6.67/2.17
6.67/2.17

(11) CdtKnowledgeProof (BOTH BOUNDS(ID, ID) transformation)

The following tuples could be moved from S to K by knowledge propagation:

U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0)) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0))
6.67/2.17
6.67/2.17

(12) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.17
__(z0, nil) → z0 6.67/2.17
__(nil, z0) → z0 6.67/2.17
__(z0, z1) → n____(z0, z1) 6.67/2.17
U11(tt) → tt 6.67/2.17
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.17
U22(tt) → tt 6.67/2.17
U31(tt) → tt 6.67/2.17
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.17
U42(tt) → tt 6.67/2.17
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.17
U52(tt) → tt 6.67/2.17
U61(tt) → tt 6.67/2.17
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.17
U72(tt) → tt 6.67/2.17
U81(tt) → tt 6.67/2.17
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.17
isList(n__nil) → tt 6.67/2.17
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.17
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.17
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.17
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.17
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.17
isPal(n__nil) → tt 6.67/2.17
isQid(n__a) → tt 6.67/2.17
isQid(n__e) → tt 6.67/2.17
isQid(n__i) → tt 6.67/2.17
isQid(n__o) → tt 6.67/2.17
isQid(n__u) → tt 6.67/2.17
nil → n__nil 6.67/2.17
a → n__a 6.67/2.17
e → n__e 6.67/2.17
i → n__i 6.67/2.17
o → n__o 6.67/2.17
u → n__u 6.67/2.17
activate(n__nil) → nil 6.67/2.17
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.17
activate(n__a) → a 6.67/2.17
activate(n__e) → e 6.67/2.17
activate(n__i) → i 6.67/2.17
activate(n__o) → o 6.67/2.17
activate(n__u) → u 6.67/2.17
activate(z0) → z0
Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0))
S tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43
K tuples:

U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0))
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

ISLIST, ISNELIST, U21', U41', U51', ISNEPAL, ACTIVATE, U71', ISPAL

Compound Symbols:

c18, c20, c21, c5, c8, c10, c16, c19, c22, c37, c38, c39, c40, c41, c42, c43, c

6.67/2.17
6.67/2.17

(13) CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
We considered the (Usable) Rules:

activate(n__nil) → nil 6.67/2.17
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.17
activate(n__a) → a 6.67/2.17
activate(n__e) → e 6.67/2.17
activate(n__i) → i 6.67/2.17
activate(n__o) → o 6.67/2.17
activate(n__u) → u 6.67/2.17
activate(z0) → z0 6.67/2.17
u → n__u 6.67/2.17
o → n__o 6.67/2.17
i → n__i 6.67/2.17
e → n__e 6.67/2.17
a → n__a 6.67/2.17
__(z0, z1) → n____(z0, z1) 6.67/2.17
nil → n__nil 6.67/2.17
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.17
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.17
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.17
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.17
isList(n__nil) → tt 6.67/2.17
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.17
U52(tt) → tt 6.67/2.17
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.17
U22(tt) → tt 6.67/2.17
U11(tt) → tt 6.67/2.17
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.17
U42(tt) → tt 6.67/2.17
isQid(n__a) → tt 6.67/2.17
isQid(n__e) → tt 6.67/2.17
isQid(n__i) → tt 6.67/2.17
isQid(n__o) → tt 6.67/2.17
isQid(n__u) → tt 6.67/2.17
U31(tt) → tt
And the Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0))
The order we found is given by the following interpretation:
Polynomial interpretation : 6.67/2.17

POL(ACTIVATE(x1)) = 0    6.67/2.17
POL(ISLIST(x1)) = x1    6.67/2.17
POL(ISNELIST(x1)) = x1    6.67/2.17
POL(ISNEPAL(x1)) = 0    6.67/2.17
POL(ISPAL(x1)) = [2] + [2]x1    6.67/2.17
POL(U11(x1)) = [3]    6.67/2.17
POL(U21(x1, x2)) = [3]    6.67/2.17
POL(U21'(x1, x2)) = x2    6.67/2.17
POL(U22(x1)) = [3] + [3]x1    6.67/2.17
POL(U31(x1)) = [3]    6.67/2.17
POL(U41(x1, x2)) = [3]    6.67/2.17
POL(U41'(x1, x2)) = x2    6.67/2.17
POL(U42(x1)) = [3] + [3]x1    6.67/2.17
POL(U51(x1, x2)) = [3] + [3]x1    6.67/2.17
POL(U51'(x1, x2)) = x2    6.67/2.17
POL(U52(x1)) = [3]    6.67/2.17
POL(U71'(x1, x2)) = [3] + x1 + [4]x2    6.67/2.17
POL(__(x1, x2)) = [1] + x1 + x2    6.67/2.17
POL(a) = 0    6.67/2.17
POL(activate(x1)) = x1    6.67/2.17
POL(c(x1)) = x1    6.67/2.17
POL(c10(x1, x2)) = x1 + x2    6.67/2.17
POL(c16(x1, x2)) = x1 + x2    6.67/2.17
POL(c18(x1, x2, x3, x4)) = x1 + x2 + x3 + x4    6.67/2.17
POL(c19(x1)) = x1    6.67/2.17
POL(c20(x1, x2, x3, x4)) = x1 + x2 + x3 + x4    6.67/2.17
POL(c21(x1, x2, x3, x4)) = x1 + x2 + x3 + x4    6.67/2.17
POL(c22(x1)) = x1    6.67/2.17
POL(c37) = 0    6.67/2.17
POL(c38) = 0    6.67/2.17
POL(c39) = 0    6.67/2.17
POL(c40) = 0    6.67/2.17
POL(c41) = 0    6.67/2.17
POL(c42) = 0    6.67/2.17
POL(c43) = 0    6.67/2.17
POL(c5(x1, x2)) = x1 + x2    6.67/2.17
POL(c8(x1, x2)) = x1 + x2    6.67/2.17
POL(e) = 0    6.67/2.17
POL(i) = 0    6.67/2.17
POL(isList(x1)) = 0    6.67/2.17
POL(isNeList(x1)) = 0    6.67/2.17
POL(isQid(x1)) = 0    6.67/2.17
POL(n____(x1, x2)) = [1] + x1 + x2    6.67/2.17
POL(n__a) = 0    6.67/2.17
POL(n__e) = 0    6.67/2.17
POL(n__i) = 0    6.67/2.17
POL(n__nil) = 0    6.67/2.17
POL(n__o) = 0    6.67/2.17
POL(n__u) = 0    6.67/2.17
POL(nil) = 0    6.67/2.17
POL(o) = 0    6.67/2.17
POL(tt) = 0    6.67/2.17
POL(u) = 0   
6.67/2.17
6.67/2.17

(14) Obligation:

Complexity Dependency Tuples Problem
Rules:

__(__(z0, z1), z2) → __(z0, __(z1, z2)) 6.67/2.17
__(z0, nil) → z0 6.67/2.17
__(nil, z0) → z0 6.67/2.17
__(z0, z1) → n____(z0, z1) 6.67/2.17
U11(tt) → tt 6.67/2.17
U21(tt, z0) → U22(isList(activate(z0))) 6.67/2.17
U22(tt) → tt 6.67/2.17
U31(tt) → tt 6.67/2.17
U41(tt, z0) → U42(isNeList(activate(z0))) 6.67/2.17
U42(tt) → tt 6.67/2.17
U51(tt, z0) → U52(isList(activate(z0))) 6.67/2.17
U52(tt) → tt 6.67/2.17
U61(tt) → tt 6.67/2.17
U71(tt, z0) → U72(isPal(activate(z0))) 6.67/2.17
U72(tt) → tt 6.67/2.17
U81(tt) → tt 6.67/2.17
isList(z0) → U11(isNeList(activate(z0))) 6.67/2.17
isList(n__nil) → tt 6.67/2.17
isList(n____(z0, z1)) → U21(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(z0) → U31(isQid(activate(z0))) 6.67/2.17
isNeList(n____(z0, z1)) → U41(isList(activate(z0)), activate(z1)) 6.67/2.17
isNeList(n____(z0, z1)) → U51(isNeList(activate(z0)), activate(z1)) 6.67/2.17
isNePal(z0) → U61(isQid(activate(z0))) 6.67/2.17
isNePal(n____(z0, __(z1, z0))) → U71(isQid(activate(z0)), activate(z1)) 6.67/2.17
isPal(z0) → U81(isNePal(activate(z0))) 6.67/2.17
isPal(n__nil) → tt 6.67/2.17
isQid(n__a) → tt 6.67/2.17
isQid(n__e) → tt 6.67/2.17
isQid(n__i) → tt 6.67/2.17
isQid(n__o) → tt 6.67/2.17
isQid(n__u) → tt 6.67/2.17
nil → n__nil 6.67/2.17
a → n__a 6.67/2.17
e → n__e 6.67/2.17
i → n__i 6.67/2.17
o → n__o 6.67/2.17
u → n__u 6.67/2.17
activate(n__nil) → nil 6.67/2.17
activate(n____(z0, z1)) → __(z0, z1) 6.67/2.17
activate(n__a) → a 6.67/2.17
activate(n__e) → e 6.67/2.17
activate(n__i) → i 6.67/2.17
activate(n__o) → o 6.67/2.17
activate(n__u) → u 6.67/2.17
activate(z0) → z0
Tuples:

ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0))
S tuples:

U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43
K tuples:

U71'(tt, z0) → c(ISPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ISNEPAL(activate(z0))) 6.67/2.17
ISPAL(z0) → c(ACTIVATE(z0)) 6.67/2.17
ISNEPAL(z0) → c22(ACTIVATE(z0)) 6.67/2.17
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
Defined Rule Symbols:

__, U11, U21, U22, U31, U41, U42, U51, U52, U61, U71, U72, U81, isList, isNeList, isNePal, isPal, isQid, nil, a, e, i, o, u, activate

Defined Pair Symbols:

ISLIST, ISNELIST, U21', U41', U51', ISNEPAL, ACTIVATE, U71', ISPAL

Compound Symbols:

c18, c20, c21, c5, c8, c10, c16, c19, c22, c37, c38, c39, c40, c41, c42, c43, c

6.67/2.17
6.67/2.17

(15) CdtKnowledgeProof (EQUIVALENT transformation)

The following tuples could be moved from S to K by knowledge propagation:

U21'(tt, z0) → c5(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U41'(tt, z0) → c8(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
U51'(tt, z0) → c10(ISLIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
ISLIST(n____(z0, z1)) → c18(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISLIST(z0) → c16(ISNELIST(activate(z0)), ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
ISNELIST(n____(z0, z1)) → c20(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(n____(z0, z1)) → c21(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 6.67/2.17
ISNELIST(z0) → c19(ACTIVATE(z0)) 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43 6.67/2.17
ACTIVATE(n__nil) → c37 6.67/2.17
ACTIVATE(n____(z0, z1)) → c38 6.67/2.17
ACTIVATE(n__a) → c39 6.67/2.17
ACTIVATE(n__e) → c40 6.67/2.17
ACTIVATE(n__i) → c41 6.67/2.17
ACTIVATE(n__o) → c42 6.67/2.17
ACTIVATE(n__u) → c43
Now S is empty
6.67/2.17
6.67/2.17

(16) BOUNDS(O(1), O(1))

6.67/2.17
6.67/2.17
7.03/2.23 EOF