/export/starexec/sandbox/solver/bin/starexec_run_tct_rc /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: a__U11(X) -> U11(X) a__U11(tt()) -> tt() a__U21(X1,X2) -> U21(X1,X2) a__U21(tt(),V2) -> a__U22(a__isList(V2)) a__U22(X) -> U22(X) a__U22(tt()) -> tt() a__U31(X) -> U31(X) a__U31(tt()) -> tt() a__U41(X1,X2) -> U41(X1,X2) a__U41(tt(),V2) -> a__U42(a__isNeList(V2)) a__U42(X) -> U42(X) a__U42(tt()) -> tt() a__U51(X1,X2) -> U51(X1,X2) a__U51(tt(),V2) -> a__U52(a__isList(V2)) a__U52(X) -> U52(X) a__U52(tt()) -> tt() a__U61(X) -> U61(X) a__U61(tt()) -> tt() a__U71(X1,X2) -> U71(X1,X2) a__U71(tt(),P) -> a__U72(a__isPal(P)) a__U72(X) -> U72(X) a__U72(tt()) -> tt() a__U81(X) -> U81(X) a__U81(tt()) -> tt() a____(X,nil()) -> mark(X) a____(X1,X2) -> __(X1,X2) a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) a____(nil(),X) -> mark(X) a__isList(V) -> a__U11(a__isNeList(V)) a__isList(X) -> isList(X) a__isList(__(V1,V2)) -> a__U21(a__isList(V1),V2) a__isList(nil()) -> tt() a__isNeList(V) -> a__U31(a__isQid(V)) a__isNeList(X) -> isNeList(X) a__isNeList(__(V1,V2)) -> a__U41(a__isList(V1),V2) a__isNeList(__(V1,V2)) -> a__U51(a__isNeList(V1),V2) a__isNePal(V) -> a__U61(a__isQid(V)) a__isNePal(X) -> isNePal(X) a__isNePal(__(I,__(P,I))) -> a__U71(a__isQid(I),P) a__isPal(V) -> a__U81(a__isNePal(V)) a__isPal(X) -> isPal(X) a__isPal(nil()) -> tt() a__isQid(X) -> isQid(X) a__isQid(a()) -> tt() a__isQid(e()) -> tt() a__isQid(i()) -> tt() a__isQid(o()) -> tt() a__isQid(u()) -> tt() mark(U11(X)) -> a__U11(mark(X)) mark(U21(X1,X2)) -> a__U21(mark(X1),X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1,X2)) -> a__U41(mark(X1),X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1,X2)) -> a__U51(mark(X1),X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1,X2)) -> a__U71(mark(X1),X2) mark(U72(X)) -> a__U72(mark(X)) mark(U81(X)) -> a__U81(mark(X)) mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) mark(a()) -> a() mark(e()) -> e() mark(i()) -> i() mark(isList(X)) -> a__isList(X) mark(isNeList(X)) -> a__isNeList(X) mark(isNePal(X)) -> a__isNePal(X) mark(isPal(X)) -> a__isPal(X) mark(isQid(X)) -> a__isQid(X) mark(nil()) -> nil() mark(o()) -> o() mark(tt()) -> tt() mark(u()) -> u() - Signature: {a__U11/1,a__U21/2,a__U22/1,a__U31/1,a__U41/2,a__U42/1,a__U51/2,a__U52/1,a__U61/1,a__U71/2,a__U72/1,a__U81/1 ,a____/2,a__isList/1,a__isNeList/1,a__isNePal/1,a__isPal/1,a__isQid/1,mark/1} / {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,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1 ,isQid/1,nil/0,o/0,tt/0,u/0} - Obligation: runtime complexity wrt. defined symbols {a__U11,a__U21,a__U22,a__U31,a__U41,a__U42,a__U51,a__U52,a__U61 ,a__U71,a__U72,a__U81,a____,a__isList,a__isNeList,a__isNePal,a__isPal,a__isQid,mark} and constructors {U11 ,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,tt,u} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: a__U11(X) -> U11(X) a__U11(tt()) -> tt() a__U21(X1,X2) -> U21(X1,X2) a__U21(tt(),V2) -> a__U22(a__isList(V2)) a__U22(X) -> U22(X) a__U22(tt()) -> tt() a__U31(X) -> U31(X) a__U31(tt()) -> tt() a__U41(X1,X2) -> U41(X1,X2) a__U41(tt(),V2) -> a__U42(a__isNeList(V2)) a__U42(X) -> U42(X) a__U42(tt()) -> tt() a__U51(X1,X2) -> U51(X1,X2) a__U51(tt(),V2) -> a__U52(a__isList(V2)) a__U52(X) -> U52(X) a__U52(tt()) -> tt() a__U61(X) -> U61(X) a__U61(tt()) -> tt() a__U71(X1,X2) -> U71(X1,X2) a__U71(tt(),P) -> a__U72(a__isPal(P)) a__U72(X) -> U72(X) a__U72(tt()) -> tt() a__U81(X) -> U81(X) a__U81(tt()) -> tt() a____(X,nil()) -> mark(X) a____(X1,X2) -> __(X1,X2) a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) a____(nil(),X) -> mark(X) a__isList(V) -> a__U11(a__isNeList(V)) a__isList(X) -> isList(X) a__isList(__(V1,V2)) -> a__U21(a__isList(V1),V2) a__isList(nil()) -> tt() a__isNeList(V) -> a__U31(a__isQid(V)) a__isNeList(X) -> isNeList(X) a__isNeList(__(V1,V2)) -> a__U41(a__isList(V1),V2) a__isNeList(__(V1,V2)) -> a__U51(a__isNeList(V1),V2) a__isNePal(V) -> a__U61(a__isQid(V)) a__isNePal(X) -> isNePal(X) a__isNePal(__(I,__(P,I))) -> a__U71(a__isQid(I),P) a__isPal(V) -> a__U81(a__isNePal(V)) a__isPal(X) -> isPal(X) a__isPal(nil()) -> tt() a__isQid(X) -> isQid(X) a__isQid(a()) -> tt() a__isQid(e()) -> tt() a__isQid(i()) -> tt() a__isQid(o()) -> tt() a__isQid(u()) -> tt() mark(U11(X)) -> a__U11(mark(X)) mark(U21(X1,X2)) -> a__U21(mark(X1),X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1,X2)) -> a__U41(mark(X1),X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1,X2)) -> a__U51(mark(X1),X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1,X2)) -> a__U71(mark(X1),X2) mark(U72(X)) -> a__U72(mark(X)) mark(U81(X)) -> a__U81(mark(X)) mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) mark(a()) -> a() mark(e()) -> e() mark(i()) -> i() mark(isList(X)) -> a__isList(X) mark(isNeList(X)) -> a__isNeList(X) mark(isNePal(X)) -> a__isNePal(X) mark(isPal(X)) -> a__isPal(X) mark(isQid(X)) -> a__isQid(X) mark(nil()) -> nil() mark(o()) -> o() mark(tt()) -> tt() mark(u()) -> u() - Signature: {a__U11/1,a__U21/2,a__U22/1,a__U31/1,a__U41/2,a__U42/1,a__U51/2,a__U52/1,a__U61/1,a__U71/2,a__U72/1,a__U81/1 ,a____/2,a__isList/1,a__isNeList/1,a__isNePal/1,a__isPal/1,a__isQid/1,mark/1} / {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,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1 ,isQid/1,nil/0,o/0,tt/0,u/0} - Obligation: runtime complexity wrt. defined symbols {a__U11,a__U21,a__U22,a__U31,a__U41,a__U42,a__U51,a__U52,a__U61 ,a__U71,a__U72,a__U81,a____,a__isList,a__isNeList,a__isNePal,a__isPal,a__isQid,mark} and constructors {U11 ,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,tt,u} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: a__U11(X) -> U11(X) a__U11(tt()) -> tt() a__U21(X1,X2) -> U21(X1,X2) a__U21(tt(),V2) -> a__U22(a__isList(V2)) a__U22(X) -> U22(X) a__U22(tt()) -> tt() a__U31(X) -> U31(X) a__U31(tt()) -> tt() a__U41(X1,X2) -> U41(X1,X2) a__U41(tt(),V2) -> a__U42(a__isNeList(V2)) a__U42(X) -> U42(X) a__U42(tt()) -> tt() a__U51(X1,X2) -> U51(X1,X2) a__U51(tt(),V2) -> a__U52(a__isList(V2)) a__U52(X) -> U52(X) a__U52(tt()) -> tt() a__U61(X) -> U61(X) a__U61(tt()) -> tt() a__U71(X1,X2) -> U71(X1,X2) a__U71(tt(),P) -> a__U72(a__isPal(P)) a__U72(X) -> U72(X) a__U72(tt()) -> tt() a__U81(X) -> U81(X) a__U81(tt()) -> tt() a____(X,nil()) -> mark(X) a____(X1,X2) -> __(X1,X2) a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) a____(nil(),X) -> mark(X) a__isList(V) -> a__U11(a__isNeList(V)) a__isList(X) -> isList(X) a__isList(__(V1,V2)) -> a__U21(a__isList(V1),V2) a__isList(nil()) -> tt() a__isNeList(V) -> a__U31(a__isQid(V)) a__isNeList(X) -> isNeList(X) a__isNeList(__(V1,V2)) -> a__U41(a__isList(V1),V2) a__isNeList(__(V1,V2)) -> a__U51(a__isNeList(V1),V2) a__isNePal(V) -> a__U61(a__isQid(V)) a__isNePal(X) -> isNePal(X) a__isNePal(__(I,__(P,I))) -> a__U71(a__isQid(I),P) a__isPal(V) -> a__U81(a__isNePal(V)) a__isPal(X) -> isPal(X) a__isPal(nil()) -> tt() a__isQid(X) -> isQid(X) a__isQid(a()) -> tt() a__isQid(e()) -> tt() a__isQid(i()) -> tt() a__isQid(o()) -> tt() a__isQid(u()) -> tt() mark(U11(X)) -> a__U11(mark(X)) mark(U21(X1,X2)) -> a__U21(mark(X1),X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1,X2)) -> a__U41(mark(X1),X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1,X2)) -> a__U51(mark(X1),X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1,X2)) -> a__U71(mark(X1),X2) mark(U72(X)) -> a__U72(mark(X)) mark(U81(X)) -> a__U81(mark(X)) mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) mark(a()) -> a() mark(e()) -> e() mark(i()) -> i() mark(isList(X)) -> a__isList(X) mark(isNeList(X)) -> a__isNeList(X) mark(isNePal(X)) -> a__isNePal(X) mark(isPal(X)) -> a__isPal(X) mark(isQid(X)) -> a__isQid(X) mark(nil()) -> nil() mark(o()) -> o() mark(tt()) -> tt() mark(u()) -> u() - Signature: {a__U11/1,a__U21/2,a__U22/1,a__U31/1,a__U41/2,a__U42/1,a__U51/2,a__U52/1,a__U61/1,a__U71/2,a__U72/1,a__U81/1 ,a____/2,a__isList/1,a__isNeList/1,a__isNePal/1,a__isPal/1,a__isQid/1,mark/1} / {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,e/0,i/0,isList/1,isNeList/1,isNePal/1,isPal/1 ,isQid/1,nil/0,o/0,tt/0,u/0} - Obligation: runtime complexity wrt. defined symbols {a__U11,a__U21,a__U22,a__U31,a__U41,a__U42,a__U51,a__U52,a__U61 ,a__U71,a__U72,a__U81,a____,a__isList,a__isNeList,a__isNePal,a__isPal,a__isQid,mark} and constructors {U11 ,U21,U22,U31,U41,U42,U51,U52,U61,U71,U72,U81,__,a,e,i,isList,isNeList,isNePal,isPal,isQid,nil,o,tt,u} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: a__isList(x){x -> __(x,y)} = a__isList(__(x,y)) ->^+ a__U21(a__isList(x),y) = C[a__isList(x) = a__isList(x){}] WORST_CASE(Omega(n^1),?)