*** 1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X,nil()) -> X
__(X1,X2) -> n____(X1,X2)
__(__(X,Y),Z) -> __(X,__(Y,Z))
__(nil(),X) -> X
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Weak DP Rules:
Weak TRS Rules:
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
InnermostRuleRemoval
Proof:
Arguments of following rules are not normal-forms.
__(X,nil()) -> X
__(__(X,Y),Z) -> __(X,__(Y,Z))
__(nil(),X) -> X
All above mentioned rules can be savely removed.
*** 1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Weak DP Rules:
Weak TRS Rules:
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [5]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [0]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [0]
p(U72) = [1] x1 + [0]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [0]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [0]
p(isList) = [1] x1 + [0]
p(isNeList) = [1] x1 + [0]
p(isNePal) = [1] x1 + [0]
p(isPal) = [1] x1 + [0]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [0]
p(n__a) = [0]
p(n__e) = [0]
p(n__i) = [3]
p(n__nil) = [0]
p(n__o) = [0]
p(n__u) = [0]
p(nil) = [0]
p(o) = [0]
p(tt) = [0]
p(u) = [1]
Following rules are strictly oriented:
U11(tt()) = [5]
> [0]
= tt()
activate(n__i()) = [3]
> [0]
= i()
isQid(n__i()) = [3]
> [0]
= tt()
u() = [1]
> [0]
= n__u()
Following rules are (at-least) weakly oriented:
U21(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U22(isList(activate(V2)))
U22(tt()) = [0]
>= [0]
= tt()
U31(tt()) = [0]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U52(isList(activate(V2)))
U52(tt()) = [0]
>= [0]
= tt()
U61(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [0]
>= [1] P + [0]
= U72(isPal(activate(P)))
U72(tt()) = [0]
>= [0]
= tt()
U81(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= n____(X1,X2)
a() = [0]
>= [0]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= __(activate(X1),activate(X2))
activate(n__a()) = [0]
>= [0]
= a()
activate(n__e()) = [0]
>= [0]
= e()
activate(n__nil()) = [0]
>= [0]
= nil()
activate(n__o()) = [0]
>= [0]
= o()
activate(n__u()) = [0]
>= [1]
= u()
e() = [0]
>= [0]
= n__e()
i() = [0]
>= [3]
= n__i()
isList(V) = [1] V + [0]
>= [1] V + [5]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [0]
>= [0]
= tt()
isNeList(V) = [1] V + [0]
>= [1] V + [0]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [0]
>= [1] V + [0]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [0]
>= [1] I + [1] P + [0]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [0]
>= [1] V + [0]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [0]
>= [0]
= tt()
isQid(n__a()) = [0]
>= [0]
= tt()
isQid(n__e()) = [0]
>= [0]
= tt()
isQid(n__o()) = [0]
>= [0]
= tt()
isQid(n__u()) = [0]
>= [0]
= tt()
nil() = [0]
>= [0]
= n__nil()
o() = [0]
>= [0]
= n__o()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
activate(n__i()) -> i()
isQid(n__i()) -> tt()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [0]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [0]
p(U72) = [1] x1 + [0]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [0]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [0]
p(isList) = [1] x1 + [0]
p(isNeList) = [1] x1 + [0]
p(isNePal) = [1] x1 + [0]
p(isPal) = [1] x1 + [0]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [0]
p(n__a) = [0]
p(n__e) = [0]
p(n__i) = [0]
p(n__nil) = [0]
p(n__o) = [1]
p(n__u) = [0]
p(nil) = [0]
p(o) = [3]
p(tt) = [0]
p(u) = [0]
Following rules are strictly oriented:
isQid(n__o()) = [1]
> [0]
= tt()
o() = [3]
> [1]
= n__o()
Following rules are (at-least) weakly oriented:
U11(tt()) = [0]
>= [0]
= tt()
U21(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U22(isList(activate(V2)))
U22(tt()) = [0]
>= [0]
= tt()
U31(tt()) = [0]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U52(isList(activate(V2)))
U52(tt()) = [0]
>= [0]
= tt()
U61(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [0]
>= [1] P + [0]
= U72(isPal(activate(P)))
U72(tt()) = [0]
>= [0]
= tt()
U81(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= n____(X1,X2)
a() = [0]
>= [0]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= __(activate(X1),activate(X2))
activate(n__a()) = [0]
>= [0]
= a()
activate(n__e()) = [0]
>= [0]
= e()
activate(n__i()) = [0]
>= [0]
= i()
activate(n__nil()) = [0]
>= [0]
= nil()
activate(n__o()) = [1]
>= [3]
= o()
activate(n__u()) = [0]
>= [0]
= u()
e() = [0]
>= [0]
= n__e()
i() = [0]
>= [0]
= n__i()
isList(V) = [1] V + [0]
>= [1] V + [0]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [0]
>= [0]
= tt()
isNeList(V) = [1] V + [0]
>= [1] V + [0]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [0]
>= [1] V + [0]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [0]
>= [1] I + [1] P + [0]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [0]
>= [1] V + [0]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [0]
>= [0]
= tt()
isQid(n__a()) = [0]
>= [0]
= tt()
isQid(n__e()) = [0]
>= [0]
= tt()
isQid(n__i()) = [0]
>= [0]
= tt()
isQid(n__u()) = [0]
>= [0]
= tt()
nil() = [0]
>= [0]
= n__nil()
u() = [0]
>= [0]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
activate(n__i()) -> i()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [0]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [3]
p(U72) = [1] x1 + [0]
p(U81) = [1] x1 + [3]
p(__) = [1] x1 + [1] x2 + [0]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [0]
p(isList) = [1] x1 + [0]
p(isNeList) = [1] x1 + [0]
p(isNePal) = [1] x1 + [0]
p(isPal) = [1] x1 + [3]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [0]
p(n__a) = [0]
p(n__e) = [0]
p(n__i) = [0]
p(n__nil) = [0]
p(n__o) = [0]
p(n__u) = [0]
p(nil) = [1]
p(o) = [0]
p(tt) = [0]
p(u) = [0]
Following rules are strictly oriented:
U81(tt()) = [3]
> [0]
= tt()
isPal(n__nil()) = [3]
> [0]
= tt()
nil() = [1]
> [0]
= n__nil()
Following rules are (at-least) weakly oriented:
U11(tt()) = [0]
>= [0]
= tt()
U21(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U22(isList(activate(V2)))
U22(tt()) = [0]
>= [0]
= tt()
U31(tt()) = [0]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [0]
>= [1] V2 + [0]
= U52(isList(activate(V2)))
U52(tt()) = [0]
>= [0]
= tt()
U61(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [3]
>= [1] P + [3]
= U72(isPal(activate(P)))
U72(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= n____(X1,X2)
a() = [0]
>= [0]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [0]
= __(activate(X1),activate(X2))
activate(n__a()) = [0]
>= [0]
= a()
activate(n__e()) = [0]
>= [0]
= e()
activate(n__i()) = [0]
>= [0]
= i()
activate(n__nil()) = [0]
>= [1]
= nil()
activate(n__o()) = [0]
>= [0]
= o()
activate(n__u()) = [0]
>= [0]
= u()
e() = [0]
>= [0]
= n__e()
i() = [0]
>= [0]
= n__i()
isList(V) = [1] V + [0]
>= [1] V + [0]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [0]
>= [0]
= tt()
isNeList(V) = [1] V + [0]
>= [1] V + [0]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [0]
>= [1] V + [0]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [0]
>= [1] I + [1] P + [3]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [3]
>= [1] V + [3]
= U81(isNePal(activate(V)))
isQid(n__a()) = [0]
>= [0]
= tt()
isQid(n__e()) = [0]
>= [0]
= tt()
isQid(n__i()) = [0]
>= [0]
= tt()
isQid(n__o()) = [0]
>= [0]
= tt()
isQid(n__u()) = [0]
>= [0]
= tt()
o() = [0]
>= [0]
= n__o()
u() = [0]
>= [0]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__u()) -> tt()
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U81(tt()) -> tt()
activate(n__i()) -> i()
isPal(n__nil()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [0]
p(U42) = [1] x1 + [5]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [0]
p(U72) = [1] x1 + [0]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [1]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [4]
p(isList) = [1] x1 + [0]
p(isNeList) = [1] x1 + [3]
p(isNePal) = [1] x1 + [0]
p(isPal) = [1] x1 + [1]
p(isQid) = [1] x1 + [4]
p(n____) = [1] x1 + [1] x2 + [1]
p(n__a) = [6]
p(n__e) = [0]
p(n__i) = [4]
p(n__nil) = [1]
p(n__o) = [4]
p(n__u) = [0]
p(nil) = [1]
p(o) = [4]
p(tt) = [2]
p(u) = [4]
Following rules are strictly oriented:
U21(tt(),V2) = [1] V2 + [2]
> [1] V2 + [0]
= U22(isList(activate(V2)))
U42(tt()) = [7]
> [2]
= tt()
U51(tt(),V2) = [1] V2 + [2]
> [1] V2 + [0]
= U52(isList(activate(V2)))
U71(tt(),P) = [1] P + [2]
> [1] P + [1]
= U72(isPal(activate(P)))
activate(n__a()) = [6]
> [0]
= a()
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [1]
> [1] V1 + [1] V2 + [0]
= U21(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [4]
> [1] V1 + [1] V2 + [0]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [4]
> [1] V1 + [1] V2 + [3]
= U51(isNeList(activate(V1))
,activate(V2))
isPal(V) = [1] V + [1]
> [1] V + [0]
= U81(isNePal(activate(V)))
isQid(n__a()) = [10]
> [2]
= tt()
isQid(n__e()) = [4]
> [2]
= tt()
isQid(n__u()) = [4]
> [2]
= tt()
Following rules are (at-least) weakly oriented:
U11(tt()) = [2]
>= [2]
= tt()
U22(tt()) = [2]
>= [2]
= tt()
U31(tt()) = [2]
>= [2]
= tt()
U41(tt(),V2) = [1] V2 + [2]
>= [1] V2 + [8]
= U42(isNeList(activate(V2)))
U52(tt()) = [2]
>= [2]
= tt()
U61(tt()) = [2]
>= [2]
= tt()
U72(tt()) = [2]
>= [2]
= tt()
U81(tt()) = [2]
>= [2]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [1]
>= [1] X1 + [1] X2 + [1]
= n____(X1,X2)
a() = [0]
>= [6]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [1]
>= [1] X1 + [1] X2 + [1]
= __(activate(X1),activate(X2))
activate(n__e()) = [0]
>= [0]
= e()
activate(n__i()) = [4]
>= [4]
= i()
activate(n__nil()) = [1]
>= [1]
= nil()
activate(n__o()) = [4]
>= [4]
= o()
activate(n__u()) = [0]
>= [4]
= u()
e() = [0]
>= [0]
= n__e()
i() = [4]
>= [4]
= n__i()
isList(V) = [1] V + [0]
>= [1] V + [3]
= U11(isNeList(activate(V)))
isList(n__nil()) = [1]
>= [2]
= tt()
isNeList(V) = [1] V + [3]
>= [1] V + [4]
= U31(isQid(activate(V)))
isNePal(V) = [1] V + [0]
>= [1] V + [4]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [2]
>= [1] I + [1] P + [4]
= U71(isQid(activate(I))
,activate(P))
isPal(n__nil()) = [2]
>= [2]
= tt()
isQid(n__i()) = [8]
>= [2]
= tt()
isQid(n__o()) = [8]
>= [2]
= tt()
nil() = [1]
>= [1]
= n__nil()
o() = [4]
>= [4]
= n__o()
u() = [4]
>= [0]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U72(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__e()) -> e()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U71(tt(),P) -> U72(isPal(activate(P)))
U81(tt()) -> tt()
activate(n__a()) -> a()
activate(n__i()) -> i()
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [2]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [0]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [2]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [1]
p(U72) = [1] x1 + [1]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [4]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [1]
p(isList) = [1] x1 + [0]
p(isNeList) = [1] x1 + [0]
p(isNePal) = [1] x1 + [2]
p(isPal) = [1] x1 + [2]
p(isQid) = [1] x1 + [2]
p(n____) = [1] x1 + [1] x2 + [0]
p(n__a) = [0]
p(n__e) = [0]
p(n__i) = [1]
p(n__nil) = [0]
p(n__o) = [0]
p(n__u) = [0]
p(nil) = [0]
p(o) = [0]
p(tt) = [2]
p(u) = [0]
Following rules are strictly oriented:
U22(tt()) = [4]
> [2]
= tt()
U41(tt(),V2) = [1] V2 + [2]
> [1] V2 + [0]
= U42(isNeList(activate(V2)))
U52(tt()) = [4]
> [2]
= tt()
U72(tt()) = [3]
> [2]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [4]
> [1] X1 + [1] X2 + [0]
= n____(X1,X2)
Following rules are (at-least) weakly oriented:
U11(tt()) = [2]
>= [2]
= tt()
U21(tt(),V2) = [1] V2 + [2]
>= [1] V2 + [2]
= U22(isList(activate(V2)))
U31(tt()) = [2]
>= [2]
= tt()
U42(tt()) = [2]
>= [2]
= tt()
U51(tt(),V2) = [1] V2 + [2]
>= [1] V2 + [2]
= U52(isList(activate(V2)))
U61(tt()) = [2]
>= [2]
= tt()
U71(tt(),P) = [1] P + [3]
>= [1] P + [3]
= U72(isPal(activate(P)))
U81(tt()) = [2]
>= [2]
= tt()
a() = [0]
>= [0]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [0]
>= [1] X1 + [1] X2 + [4]
= __(activate(X1),activate(X2))
activate(n__a()) = [0]
>= [0]
= a()
activate(n__e()) = [0]
>= [0]
= e()
activate(n__i()) = [1]
>= [1]
= i()
activate(n__nil()) = [0]
>= [0]
= nil()
activate(n__o()) = [0]
>= [0]
= o()
activate(n__u()) = [0]
>= [0]
= u()
e() = [0]
>= [0]
= n__e()
i() = [1]
>= [1]
= n__i()
isList(V) = [1] V + [0]
>= [1] V + [0]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [0]
>= [2]
= tt()
isNeList(V) = [1] V + [0]
>= [1] V + [2]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [0]
>= [1] V1 + [1] V2 + [0]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [2]
>= [1] V + [2]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [2]
>= [1] I + [1] P + [3]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [2]
>= [1] V + [2]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [2]
>= [2]
= tt()
isQid(n__a()) = [2]
>= [2]
= tt()
isQid(n__e()) = [2]
>= [2]
= tt()
isQid(n__i()) = [3]
>= [2]
= tt()
isQid(n__o()) = [2]
>= [2]
= tt()
isQid(n__u()) = [2]
>= [2]
= tt()
nil() = [0]
>= [0]
= n__nil()
o() = [0]
>= [0]
= n__o()
u() = [0]
>= [0]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U31(tt()) -> tt()
U61(tt()) -> tt()
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__e()) -> e()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
activate(n__a()) -> a()
activate(n__i()) -> i()
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [4]
p(U21) = [1] x1 + [1] x2 + [3]
p(U22) = [1] x1 + [1]
p(U31) = [1] x1 + [3]
p(U41) = [1] x1 + [1] x2 + [7]
p(U42) = [1] x1 + [1]
p(U51) = [1] x1 + [1] x2 + [5]
p(U52) = [1] x1 + [2]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [3]
p(U72) = [1] x1 + [1]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [7]
p(a) = [0]
p(activate) = [1] x1 + [0]
p(e) = [0]
p(i) = [0]
p(isList) = [1] x1 + [1]
p(isNeList) = [1] x1 + [6]
p(isNePal) = [1] x1 + [0]
p(isPal) = [1] x1 + [0]
p(isQid) = [1] x1 + [2]
p(n____) = [1] x1 + [1] x2 + [5]
p(n__a) = [3]
p(n__e) = [1]
p(n__i) = [1]
p(n__nil) = [4]
p(n__o) = [2]
p(n__u) = [0]
p(nil) = [5]
p(o) = [2]
p(tt) = [0]
p(u) = [0]
Following rules are strictly oriented:
U31(tt()) = [3]
> [0]
= tt()
activate(n__e()) = [1]
> [0]
= e()
isList(n__nil()) = [5]
> [0]
= tt()
isNeList(V) = [1] V + [6]
> [1] V + [5]
= U31(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [10]
> [1] I + [1] P + [5]
= U71(isQid(activate(I))
,activate(P))
Following rules are (at-least) weakly oriented:
U11(tt()) = [4]
>= [0]
= tt()
U21(tt(),V2) = [1] V2 + [3]
>= [1] V2 + [2]
= U22(isList(activate(V2)))
U22(tt()) = [1]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [7]
>= [1] V2 + [7]
= U42(isNeList(activate(V2)))
U42(tt()) = [1]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [5]
>= [1] V2 + [3]
= U52(isList(activate(V2)))
U52(tt()) = [2]
>= [0]
= tt()
U61(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [3]
>= [1] P + [1]
= U72(isPal(activate(P)))
U72(tt()) = [1]
>= [0]
= tt()
U81(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [7]
>= [1] X1 + [1] X2 + [5]
= n____(X1,X2)
a() = [0]
>= [3]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [5]
>= [1] X1 + [1] X2 + [7]
= __(activate(X1),activate(X2))
activate(n__a()) = [3]
>= [0]
= a()
activate(n__i()) = [1]
>= [0]
= i()
activate(n__nil()) = [4]
>= [5]
= nil()
activate(n__o()) = [2]
>= [2]
= o()
activate(n__u()) = [0]
>= [0]
= u()
e() = [0]
>= [1]
= n__e()
i() = [0]
>= [1]
= n__i()
isList(V) = [1] V + [1]
>= [1] V + [10]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [6]
>= [1] V1 + [1] V2 + [4]
= U21(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [11]
>= [1] V1 + [1] V2 + [8]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [11]
>= [1] V1 + [1] V2 + [11]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [0]
>= [1] V + [2]
= U61(isQid(activate(V)))
isPal(V) = [1] V + [0]
>= [1] V + [0]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [4]
>= [0]
= tt()
isQid(n__a()) = [5]
>= [0]
= tt()
isQid(n__e()) = [3]
>= [0]
= tt()
isQid(n__i()) = [3]
>= [0]
= tt()
isQid(n__o()) = [4]
>= [0]
= tt()
isQid(n__u()) = [2]
>= [0]
= tt()
nil() = [5]
>= [4]
= n__nil()
o() = [2]
>= [2]
= n__o()
u() = [0]
>= [0]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
U61(tt()) -> tt()
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isNePal(V) -> U61(isQid(activate(V)))
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [4]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [1]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [4]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [2]
p(U71) = [1] x1 + [1] x2 + [4]
p(U72) = [1] x1 + [0]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [4]
p(a) = [5]
p(activate) = [1] x1 + [0]
p(e) = [4]
p(i) = [2]
p(isList) = [1] x1 + [4]
p(isNeList) = [1] x1 + [1]
p(isNePal) = [1] x1 + [3]
p(isPal) = [1] x1 + [4]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [4]
p(n__a) = [5]
p(n__e) = [4]
p(n__i) = [2]
p(n__nil) = [5]
p(n__o) = [2]
p(n__u) = [2]
p(nil) = [6]
p(o) = [5]
p(tt) = [0]
p(u) = [5]
Following rules are strictly oriented:
U61(tt()) = [2]
> [0]
= tt()
isList(V) = [1] V + [4]
> [1] V + [1]
= U11(isNeList(activate(V)))
isNePal(V) = [1] V + [3]
> [1] V + [2]
= U61(isQid(activate(V)))
Following rules are (at-least) weakly oriented:
U11(tt()) = [0]
>= [0]
= tt()
U21(tt(),V2) = [1] V2 + [4]
>= [1] V2 + [4]
= U22(isList(activate(V2)))
U22(tt()) = [0]
>= [0]
= tt()
U31(tt()) = [0]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [1]
>= [1] V2 + [1]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [4]
>= [1] V2 + [4]
= U52(isList(activate(V2)))
U52(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [4]
>= [1] P + [4]
= U72(isPal(activate(P)))
U72(tt()) = [0]
>= [0]
= tt()
U81(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [4]
>= [1] X1 + [1] X2 + [4]
= n____(X1,X2)
a() = [5]
>= [5]
= n__a()
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [4]
>= [1] X1 + [1] X2 + [4]
= __(activate(X1),activate(X2))
activate(n__a()) = [5]
>= [5]
= a()
activate(n__e()) = [4]
>= [4]
= e()
activate(n__i()) = [2]
>= [2]
= i()
activate(n__nil()) = [5]
>= [6]
= nil()
activate(n__o()) = [2]
>= [5]
= o()
activate(n__u()) = [2]
>= [5]
= u()
e() = [4]
>= [4]
= n__e()
i() = [2]
>= [2]
= n__i()
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [8]
>= [1] V1 + [1] V2 + [8]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [9]
>= [0]
= tt()
isNeList(V) = [1] V + [1]
>= [1] V + [0]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [5]
>= [1] V1 + [1] V2 + [5]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [5]
>= [1] V1 + [1] V2 + [5]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [11]
>= [1] I + [1] P + [4]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [4]
>= [1] V + [3]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [9]
>= [0]
= tt()
isQid(n__a()) = [5]
>= [0]
= tt()
isQid(n__e()) = [4]
>= [0]
= tt()
isQid(n__i()) = [2]
>= [0]
= tt()
isQid(n__o()) = [2]
>= [0]
= tt()
isQid(n__u()) = [2]
>= [0]
= tt()
nil() = [6]
>= [5]
= n__nil()
o() = [5]
>= [2]
= n__o()
u() = [5]
>= [2]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [0]
p(U21) = [1] x1 + [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [3]
p(U42) = [1] x1 + [1]
p(U51) = [1] x1 + [1] x2 + [0]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [4]
p(U72) = [1] x1 + [2]
p(U81) = [1] x1 + [1]
p(__) = [1] x1 + [1] x2 + [6]
p(a) = [4]
p(activate) = [1] x1 + [1]
p(e) = [0]
p(i) = [0]
p(isList) = [1] x1 + [2]
p(isNeList) = [1] x1 + [1]
p(isNePal) = [1] x1 + [2]
p(isPal) = [1] x1 + [4]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [6]
p(n__a) = [3]
p(n__e) = [6]
p(n__i) = [3]
p(n__nil) = [1]
p(n__o) = [3]
p(n__u) = [3]
p(nil) = [1]
p(o) = [3]
p(tt) = [3]
p(u) = [3]
Following rules are strictly oriented:
a() = [4]
> [3]
= n__a()
activate(X) = [1] X + [1]
> [1] X + [0]
= X
activate(n__nil()) = [2]
> [1]
= nil()
activate(n__o()) = [4]
> [3]
= o()
activate(n__u()) = [4]
> [3]
= u()
Following rules are (at-least) weakly oriented:
U11(tt()) = [3]
>= [3]
= tt()
U21(tt(),V2) = [1] V2 + [3]
>= [1] V2 + [3]
= U22(isList(activate(V2)))
U22(tt()) = [3]
>= [3]
= tt()
U31(tt()) = [3]
>= [3]
= tt()
U41(tt(),V2) = [1] V2 + [6]
>= [1] V2 + [3]
= U42(isNeList(activate(V2)))
U42(tt()) = [4]
>= [3]
= tt()
U51(tt(),V2) = [1] V2 + [3]
>= [1] V2 + [3]
= U52(isList(activate(V2)))
U52(tt()) = [3]
>= [3]
= tt()
U61(tt()) = [3]
>= [3]
= tt()
U71(tt(),P) = [1] P + [7]
>= [1] P + [7]
= U72(isPal(activate(P)))
U72(tt()) = [5]
>= [3]
= tt()
U81(tt()) = [4]
>= [3]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [6]
>= [1] X1 + [1] X2 + [6]
= n____(X1,X2)
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [7]
>= [1] X1 + [1] X2 + [8]
= __(activate(X1),activate(X2))
activate(n__a()) = [4]
>= [4]
= a()
activate(n__e()) = [7]
>= [0]
= e()
activate(n__i()) = [4]
>= [0]
= i()
e() = [0]
>= [6]
= n__e()
i() = [0]
>= [3]
= n__i()
isList(V) = [1] V + [2]
>= [1] V + [2]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [8]
>= [1] V1 + [1] V2 + [4]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [3]
>= [3]
= tt()
isNeList(V) = [1] V + [1]
>= [1] V + [1]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [7]
>= [1] V1 + [1] V2 + [7]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [7]
>= [1] V1 + [1] V2 + [3]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [2]
>= [1] V + [1]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [14]
>= [1] I + [1] P + [6]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [4]
>= [1] V + [4]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [5]
>= [3]
= tt()
isQid(n__a()) = [3]
>= [3]
= tt()
isQid(n__e()) = [6]
>= [3]
= tt()
isQid(n__i()) = [3]
>= [3]
= tt()
isQid(n__o()) = [3]
>= [3]
= tt()
isQid(n__u()) = [3]
>= [3]
= tt()
nil() = [1]
>= [1]
= n__nil()
o() = [3]
>= [3]
= n__o()
u() = [3]
>= [3]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
e() -> n__e()
i() -> n__i()
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
Proof:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{}
TcT has computed the following interpretation:
p(U11) = [1] x1 + [2]
p(U21) = [1] x1 + [1] x2 + [5]
p(U22) = [1] x1 + [0]
p(U31) = [1] x1 + [0]
p(U41) = [1] x1 + [1] x2 + [2]
p(U42) = [1] x1 + [0]
p(U51) = [1] x1 + [1] x2 + [5]
p(U52) = [1] x1 + [0]
p(U61) = [1] x1 + [0]
p(U71) = [1] x1 + [1] x2 + [5]
p(U72) = [1] x1 + [1]
p(U81) = [1] x1 + [0]
p(__) = [1] x1 + [1] x2 + [7]
p(a) = [0]
p(activate) = [1] x1 + [1]
p(e) = [1]
p(i) = [1]
p(isList) = [1] x1 + [4]
p(isNeList) = [1] x1 + [1]
p(isNePal) = [1] x1 + [1]
p(isPal) = [1] x1 + [2]
p(isQid) = [1] x1 + [0]
p(n____) = [1] x1 + [1] x2 + [7]
p(n__a) = [0]
p(n__e) = [0]
p(n__i) = [0]
p(n__nil) = [5]
p(n__o) = [2]
p(n__u) = [3]
p(nil) = [5]
p(o) = [2]
p(tt) = [0]
p(u) = [4]
Following rules are strictly oriented:
e() = [1]
> [0]
= n__e()
i() = [1]
> [0]
= n__i()
Following rules are (at-least) weakly oriented:
U11(tt()) = [2]
>= [0]
= tt()
U21(tt(),V2) = [1] V2 + [5]
>= [1] V2 + [5]
= U22(isList(activate(V2)))
U22(tt()) = [0]
>= [0]
= tt()
U31(tt()) = [0]
>= [0]
= tt()
U41(tt(),V2) = [1] V2 + [2]
>= [1] V2 + [2]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
>= [0]
= tt()
U51(tt(),V2) = [1] V2 + [5]
>= [1] V2 + [5]
= U52(isList(activate(V2)))
U52(tt()) = [0]
>= [0]
= tt()
U61(tt()) = [0]
>= [0]
= tt()
U71(tt(),P) = [1] P + [5]
>= [1] P + [4]
= U72(isPal(activate(P)))
U72(tt()) = [1]
>= [0]
= tt()
U81(tt()) = [0]
>= [0]
= tt()
__(X1,X2) = [1] X1 + [1] X2 + [7]
>= [1] X1 + [1] X2 + [7]
= n____(X1,X2)
a() = [0]
>= [0]
= n__a()
activate(X) = [1] X + [1]
>= [1] X + [0]
= X
activate(n____(X1,X2)) = [1] X1 + [1] X2 + [8]
>= [1] X1 + [1] X2 + [9]
= __(activate(X1),activate(X2))
activate(n__a()) = [1]
>= [0]
= a()
activate(n__e()) = [1]
>= [1]
= e()
activate(n__i()) = [1]
>= [1]
= i()
activate(n__nil()) = [6]
>= [5]
= nil()
activate(n__o()) = [3]
>= [2]
= o()
activate(n__u()) = [4]
>= [4]
= u()
isList(V) = [1] V + [4]
>= [1] V + [4]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [1] V1 + [1] V2 + [11]
>= [1] V1 + [1] V2 + [11]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [9]
>= [0]
= tt()
isNeList(V) = [1] V + [1]
>= [1] V + [1]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [8]
>= [1] V1 + [1] V2 + [8]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [1] V1 + [1] V2 + [8]
>= [1] V1 + [1] V2 + [8]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1] V + [1]
>= [1] V + [1]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2] I + [1] P + [15]
>= [1] I + [1] P + [7]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1] V + [2]
>= [1] V + [2]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [7]
>= [0]
= tt()
isQid(n__a()) = [0]
>= [0]
= tt()
isQid(n__e()) = [0]
>= [0]
= tt()
isQid(n__i()) = [0]
>= [0]
= tt()
isQid(n__o()) = [2]
>= [0]
= tt()
isQid(n__u()) = [3]
>= [0]
= tt()
nil() = [5]
>= [5]
= n__nil()
o() = [2]
>= [2]
= n__o()
u() = [4]
>= [3]
= n__u()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** 1.1.1.1.1.1.1.1.1.1.1 Progress [(O(1),O(n^2))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules, greedy = NoGreedy}
Proof:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(U11) = {1},
uargs(U21) = {1,2},
uargs(U22) = {1},
uargs(U31) = {1},
uargs(U41) = {1,2},
uargs(U42) = {1},
uargs(U51) = {1,2},
uargs(U52) = {1},
uargs(U61) = {1},
uargs(U71) = {1,2},
uargs(U72) = {1},
uargs(U81) = {1},
uargs(__) = {1,2},
uargs(isList) = {1},
uargs(isNeList) = {1},
uargs(isNePal) = {1},
uargs(isPal) = {1},
uargs(isQid) = {1}
Following symbols are considered usable:
{U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}
TcT has computed the following interpretation:
p(U11) = [1 0] x1 + [0]
[0 0] [4]
p(U21) = [1 1] x1 + [2 7] x2 + [5]
[0 0] [0 0] [1]
p(U22) = [1 0] x1 + [2]
[0 0] [1]
p(U31) = [2 0] x1 + [0]
[0 0] [0]
p(U41) = [1 2] x1 + [2 5] x2 + [0]
[0 1] [0 0] [0]
p(U42) = [1 0] x1 + [0]
[0 0] [0]
p(U51) = [1 2] x1 + [2 7] x2 + [0]
[0 0] [0 0] [4]
p(U52) = [1 0] x1 + [0]
[0 0] [0]
p(U61) = [1 0] x1 + [0]
[0 0] [1]
p(U71) = [2 0] x1 + [1 7] x2 + [3]
[0 0] [1 4] [7]
p(U72) = [1 1] x1 + [0]
[0 2] [4]
p(U81) = [1 0] x1 + [0]
[0 0] [0]
p(__) = [1 2] x1 + [1 3] x2 + [3]
[0 1] [0 1] [1]
p(a) = [0]
[0]
p(activate) = [1 1] x1 + [0]
[0 1] [0]
p(e) = [0]
[0]
p(i) = [0]
[0]
p(isList) = [2 5] x1 + [0]
[0 0] [4]
p(isNeList) = [2 3] x1 + [0]
[0 0] [4]
p(isNePal) = [1 3] x1 + [0]
[1 0] [1]
p(isPal) = [1 4] x1 + [1]
[0 2] [0]
p(isQid) = [1 0] x1 + [0]
[4 4] [0]
p(n____) = [1 2] x1 + [1 3] x2 + [3]
[0 1] [0 1] [1]
p(n__a) = [0]
[0]
p(n__e) = [0]
[0]
p(n__i) = [0]
[0]
p(n__nil) = [3]
[0]
p(n__o) = [2]
[0]
p(n__u) = [0]
[0]
p(nil) = [3]
[0]
p(o) = [2]
[0]
p(tt) = [0]
[0]
p(u) = [0]
[0]
Following rules are strictly oriented:
activate(n____(X1,X2)) = [1 3] X1 + [1 4] X2 + [4]
[0 1] [0 1] [1]
> [1 3] X1 + [1 4] X2 + [3]
[0 1] [0 1] [1]
= __(activate(X1),activate(X2))
Following rules are (at-least) weakly oriented:
U11(tt()) = [0]
[4]
>= [0]
[0]
= tt()
U21(tt(),V2) = [2 7] V2 + [5]
[0 0] [1]
>= [2 7] V2 + [2]
[0 0] [1]
= U22(isList(activate(V2)))
U22(tt()) = [2]
[1]
>= [0]
[0]
= tt()
U31(tt()) = [0]
[0]
>= [0]
[0]
= tt()
U41(tt(),V2) = [2 5] V2 + [0]
[0 0] [0]
>= [2 5] V2 + [0]
[0 0] [0]
= U42(isNeList(activate(V2)))
U42(tt()) = [0]
[0]
>= [0]
[0]
= tt()
U51(tt(),V2) = [2 7] V2 + [0]
[0 0] [4]
>= [2 7] V2 + [0]
[0 0] [0]
= U52(isList(activate(V2)))
U52(tt()) = [0]
[0]
>= [0]
[0]
= tt()
U61(tt()) = [0]
[1]
>= [0]
[0]
= tt()
U71(tt(),P) = [1 7] P + [3]
[1 4] [7]
>= [1 7] P + [1]
[0 4] [4]
= U72(isPal(activate(P)))
U72(tt()) = [0]
[4]
>= [0]
[0]
= tt()
U81(tt()) = [0]
[0]
>= [0]
[0]
= tt()
__(X1,X2) = [1 2] X1 + [1 3] X2 + [3]
[0 1] [0 1] [1]
>= [1 2] X1 + [1 3] X2 + [3]
[0 1] [0 1] [1]
= n____(X1,X2)
a() = [0]
[0]
>= [0]
[0]
= n__a()
activate(X) = [1 1] X + [0]
[0 1] [0]
>= [1 0] X + [0]
[0 1] [0]
= X
activate(n__a()) = [0]
[0]
>= [0]
[0]
= a()
activate(n__e()) = [0]
[0]
>= [0]
[0]
= e()
activate(n__i()) = [0]
[0]
>= [0]
[0]
= i()
activate(n__nil()) = [3]
[0]
>= [3]
[0]
= nil()
activate(n__o()) = [2]
[0]
>= [2]
[0]
= o()
activate(n__u()) = [0]
[0]
>= [0]
[0]
= u()
e() = [0]
[0]
>= [0]
[0]
= n__e()
i() = [0]
[0]
>= [0]
[0]
= n__i()
isList(V) = [2 5] V + [0]
[0 0] [4]
>= [2 5] V + [0]
[0 0] [4]
= U11(isNeList(activate(V)))
isList(n____(V1,V2)) = [2 9] V1 + [2 11] V2 + [11]
[0 0] [0 0] [4]
>= [2 7] V1 + [2 9] V2 + [9]
[0 0] [0 0] [1]
= U21(isList(activate(V1))
,activate(V2))
isList(n__nil()) = [6]
[4]
>= [0]
[0]
= tt()
isNeList(V) = [2 3] V + [0]
[0 0] [4]
>= [2 2] V + [0]
[0 0] [0]
= U31(isQid(activate(V)))
isNeList(n____(V1,V2)) = [2 7] V1 + [2 9] V2 + [9]
[0 0] [0 0] [4]
>= [2 7] V1 + [2 7] V2 + [8]
[0 0] [0 0] [4]
= U41(isList(activate(V1))
,activate(V2))
isNeList(n____(V1,V2)) = [2 7] V1 + [2 9] V2 + [9]
[0 0] [0 0] [4]
>= [2 5] V1 + [2 9] V2 + [8]
[0 0] [0 0] [4]
= U51(isNeList(activate(V1))
,activate(V2))
isNePal(V) = [1 3] V + [0]
[1 0] [1]
>= [1 1] V + [0]
[0 0] [1]
= U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) = [2 14] I + [1 8] P + [15]
[2 8] [1 5] [10]
>= [2 2] I + [1 8] P + [3]
[0 0] [1 5] [7]
= U71(isQid(activate(I))
,activate(P))
isPal(V) = [1 4] V + [1]
[0 2] [0]
>= [1 4] V + [0]
[0 0] [0]
= U81(isNePal(activate(V)))
isPal(n__nil()) = [4]
[0]
>= [0]
[0]
= tt()
isQid(n__a()) = [0]
[0]
>= [0]
[0]
= tt()
isQid(n__e()) = [0]
[0]
>= [0]
[0]
= tt()
isQid(n__i()) = [0]
[0]
>= [0]
[0]
= tt()
isQid(n__o()) = [2]
[8]
>= [0]
[0]
= tt()
isQid(n__u()) = [0]
[0]
>= [0]
[0]
= tt()
nil() = [3]
[0]
>= [3]
[0]
= n__nil()
o() = [2]
[0]
>= [2]
[0]
= n__o()
u() = [0]
[0]
>= [0]
[0]
= n__u()
*** 1.1.1.1.1.1.1.1.1.1.1.1 Progress [(O(1),O(1))] ***
Considered Problem:
Strict DP Rules:
Strict TRS Rules:
Weak DP Rules:
Weak TRS Rules:
U11(tt()) -> tt()
U21(tt(),V2) -> U22(isList(activate(V2)))
U22(tt()) -> tt()
U31(tt()) -> tt()
U41(tt(),V2) -> U42(isNeList(activate(V2)))
U42(tt()) -> tt()
U51(tt(),V2) -> U52(isList(activate(V2)))
U52(tt()) -> tt()
U61(tt()) -> tt()
U71(tt(),P) -> U72(isPal(activate(P)))
U72(tt()) -> tt()
U81(tt()) -> tt()
__(X1,X2) -> n____(X1,X2)
a() -> n__a()
activate(X) -> X
activate(n____(X1,X2)) -> __(activate(X1),activate(X2))
activate(n__a()) -> a()
activate(n__e()) -> e()
activate(n__i()) -> i()
activate(n__nil()) -> nil()
activate(n__o()) -> o()
activate(n__u()) -> u()
e() -> n__e()
i() -> n__i()
isList(V) -> U11(isNeList(activate(V)))
isList(n____(V1,V2)) -> U21(isList(activate(V1)),activate(V2))
isList(n__nil()) -> tt()
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1,V2)) -> U41(isList(activate(V1)),activate(V2))
isNeList(n____(V1,V2)) -> U51(isNeList(activate(V1)),activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I,n____(P,I))) -> U71(isQid(activate(I)),activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil()) -> tt()
isQid(n__a()) -> tt()
isQid(n__e()) -> tt()
isQid(n__i()) -> tt()
isQid(n__o()) -> tt()
isQid(n__u()) -> tt()
nil() -> n__nil()
o() -> n__o()
u() -> n__u()
Signature:
{U11/1,U21/2,U22/1,U31/1,U41/2,U42/1,U51/2,U52/1,U61/1,U71/2,U72/1,U81/1,__/2,a/0,activate/1,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1,isQid/1,nil/0,o/0,u/0} / {n____/2,n__a/0,n__e/0,n__i/0,n__nil/0,n__o/0,n__u/0,tt/0}
Obligation:
Innermost
basic terms: {U11,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,activate,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,u}/{n____,n__a,n__e,n__i,n__nil,n__o,n__u,tt}
Applied Processor:
EmptyProcessor
Proof:
The problem is already closed. The intended complexity is O(1).