/export/starexec/sandbox2/solver/bin/starexec_run_tct_rc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: __(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__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__nil()) -> nil() activate(n__o()) -> o() activate(n__u()) -> u() and(tt(),X) -> activate(X) e() -> n__e() i() -> n__i() isList(V) -> isNeList(activate(V)) isList(X) -> n__isList(X) isList(n____(V1,V2)) -> and(isList(activate(V1)),n__isList(activate(V2))) isList(n__nil()) -> tt() isNeList(V) -> isQid(activate(V)) isNeList(X) -> n__isNeList(X) isNeList(n____(V1,V2)) -> and(isList(activate(V1)),n__isNeList(activate(V2))) isNeList(n____(V1,V2)) -> and(isNeList(activate(V1)),n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I,n____(P,I))) -> and(isQid(activate(I)),n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(X) -> n__isPal(X) 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: {__/2,a/0,activate/1,and/2,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__isList/1,n__isNeList/1,n__isPal/1,n__nil/0,n__o/0,n__u/0,tt/0} - Obligation: runtime complexity wrt. defined symbols {__,a,activate,and,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o ,u} and constructors {n____,n__a,n__e,n__i,n__isList,n__isNeList,n__isPal,n__nil,n__o,n__u,tt} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: __(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__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__nil()) -> nil() activate(n__o()) -> o() activate(n__u()) -> u() and(tt(),X) -> activate(X) e() -> n__e() i() -> n__i() isList(V) -> isNeList(activate(V)) isList(X) -> n__isList(X) isList(n____(V1,V2)) -> and(isList(activate(V1)),n__isList(activate(V2))) isList(n__nil()) -> tt() isNeList(V) -> isQid(activate(V)) isNeList(X) -> n__isNeList(X) isNeList(n____(V1,V2)) -> and(isList(activate(V1)),n__isNeList(activate(V2))) isNeList(n____(V1,V2)) -> and(isNeList(activate(V1)),n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I,n____(P,I))) -> and(isQid(activate(I)),n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(X) -> n__isPal(X) 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: {__/2,a/0,activate/1,and/2,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__isList/1,n__isNeList/1,n__isPal/1,n__nil/0,n__o/0,n__u/0,tt/0} - Obligation: runtime complexity wrt. defined symbols {__,a,activate,and,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o ,u} and constructors {n____,n__a,n__e,n__i,n__isList,n__isNeList,n__isPal,n__nil,n__o,n__u,tt} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: __(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__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__nil()) -> nil() activate(n__o()) -> o() activate(n__u()) -> u() and(tt(),X) -> activate(X) e() -> n__e() i() -> n__i() isList(V) -> isNeList(activate(V)) isList(X) -> n__isList(X) isList(n____(V1,V2)) -> and(isList(activate(V1)),n__isList(activate(V2))) isList(n__nil()) -> tt() isNeList(V) -> isQid(activate(V)) isNeList(X) -> n__isNeList(X) isNeList(n____(V1,V2)) -> and(isList(activate(V1)),n__isNeList(activate(V2))) isNeList(n____(V1,V2)) -> and(isNeList(activate(V1)),n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I,n____(P,I))) -> and(isQid(activate(I)),n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(X) -> n__isPal(X) 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: {__/2,a/0,activate/1,and/2,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__isList/1,n__isNeList/1,n__isPal/1,n__nil/0,n__o/0,n__u/0,tt/0} - Obligation: runtime complexity wrt. defined symbols {__,a,activate,and,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o ,u} and constructors {n____,n__a,n__e,n__i,n__isList,n__isNeList,n__isPal,n__nil,n__o,n__u,tt} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: activate(x){x -> n____(x,y)} = activate(n____(x,y)) ->^+ __(activate(x),activate(y)) = C[activate(x) = activate(x){}] WORST_CASE(Omega(n^1),?)