/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__fcons(X,Z) -> cons(mark(X),Z) a__fcons(X1,X2) -> fcons(X1,X2) a__first(X1,X2) -> first(X1,X2) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first1(X1,X2) -> first1(X1,X2) a__first1(0(),Z) -> nil1() a__first1(s(X),cons(Y,Z)) -> cons1(a__quote(Y),a__first1(mark(X),mark(Z))) a__from(X) -> cons(mark(X),from(s(X))) a__from(X) -> from(X) a__quote(X) -> quote(X) a__quote(0()) -> 01() a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X,Z)) -> a__sel1(mark(X),mark(Z)) a__quote1(X) -> quote1(X) a__quote1(cons(X,Z)) -> cons1(a__quote(X),a__quote1(Z)) a__quote1(first(X,Z)) -> a__first1(mark(X),mark(Z)) a__quote1(nil()) -> nil1() a__sel(X1,X2) -> sel(X1,X2) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) a__sel1(X1,X2) -> sel1(X1,X2) a__sel1(0(),cons(X,Z)) -> a__quote(X) a__sel1(s(X),cons(Y,Z)) -> a__sel1(mark(X),mark(Z)) a__unquote(X) -> unquote(X) a__unquote(01()) -> 0() a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(X) -> unquote1(X) a__unquote1(cons1(X,Z)) -> a__fcons(a__unquote(mark(X)),a__unquote1(mark(Z))) a__unquote1(nil1()) -> nil() mark(0()) -> 0() mark(01()) -> 01() mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(cons1(X1,X2)) -> cons1(mark(X1),mark(X2)) mark(fcons(X1,X2)) -> a__fcons(mark(X1),mark(X2)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(first1(X1,X2)) -> a__first1(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(nil()) -> nil() mark(nil1()) -> nil1() mark(quote(X)) -> a__quote(X) mark(quote1(X)) -> a__quote1(X) mark(s(X)) -> s(mark(X)) mark(s1(X)) -> s1(mark(X)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(sel1(X1,X2)) -> a__sel1(mark(X1),mark(X2)) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) - Signature: {a__fcons/2,a__first/2,a__first1/2,a__from/1,a__quote/1,a__quote1/1,a__sel/2,a__sel1/2,a__unquote/1 ,a__unquote1/1,mark/1} / {0/0,01/0,cons/2,cons1/2,fcons/2,first/2,first1/2,from/1,nil/0,nil1/0,quote/1 ,quote1/1,s/1,s1/1,sel/2,sel1/2,unquote/1,unquote1/1} - Obligation: runtime complexity wrt. defined symbols {a__fcons,a__first,a__first1,a__from,a__quote,a__quote1,a__sel ,a__sel1,a__unquote,a__unquote1,mark} and constructors {0,01,cons,cons1,fcons,first,first1,from,nil,nil1 ,quote,quote1,s,s1,sel,sel1,unquote,unquote1} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: a__fcons(X,Z) -> cons(mark(X),Z) a__fcons(X1,X2) -> fcons(X1,X2) a__first(X1,X2) -> first(X1,X2) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first1(X1,X2) -> first1(X1,X2) a__first1(0(),Z) -> nil1() a__first1(s(X),cons(Y,Z)) -> cons1(a__quote(Y),a__first1(mark(X),mark(Z))) a__from(X) -> cons(mark(X),from(s(X))) a__from(X) -> from(X) a__quote(X) -> quote(X) a__quote(0()) -> 01() a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X,Z)) -> a__sel1(mark(X),mark(Z)) a__quote1(X) -> quote1(X) a__quote1(cons(X,Z)) -> cons1(a__quote(X),a__quote1(Z)) a__quote1(first(X,Z)) -> a__first1(mark(X),mark(Z)) a__quote1(nil()) -> nil1() a__sel(X1,X2) -> sel(X1,X2) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) a__sel1(X1,X2) -> sel1(X1,X2) a__sel1(0(),cons(X,Z)) -> a__quote(X) a__sel1(s(X),cons(Y,Z)) -> a__sel1(mark(X),mark(Z)) a__unquote(X) -> unquote(X) a__unquote(01()) -> 0() a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(X) -> unquote1(X) a__unquote1(cons1(X,Z)) -> a__fcons(a__unquote(mark(X)),a__unquote1(mark(Z))) a__unquote1(nil1()) -> nil() mark(0()) -> 0() mark(01()) -> 01() mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(cons1(X1,X2)) -> cons1(mark(X1),mark(X2)) mark(fcons(X1,X2)) -> a__fcons(mark(X1),mark(X2)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(first1(X1,X2)) -> a__first1(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(nil()) -> nil() mark(nil1()) -> nil1() mark(quote(X)) -> a__quote(X) mark(quote1(X)) -> a__quote1(X) mark(s(X)) -> s(mark(X)) mark(s1(X)) -> s1(mark(X)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(sel1(X1,X2)) -> a__sel1(mark(X1),mark(X2)) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) - Signature: {a__fcons/2,a__first/2,a__first1/2,a__from/1,a__quote/1,a__quote1/1,a__sel/2,a__sel1/2,a__unquote/1 ,a__unquote1/1,mark/1} / {0/0,01/0,cons/2,cons1/2,fcons/2,first/2,first1/2,from/1,nil/0,nil1/0,quote/1 ,quote1/1,s/1,s1/1,sel/2,sel1/2,unquote/1,unquote1/1} - Obligation: runtime complexity wrt. defined symbols {a__fcons,a__first,a__first1,a__from,a__quote,a__quote1,a__sel ,a__sel1,a__unquote,a__unquote1,mark} and constructors {0,01,cons,cons1,fcons,first,first1,from,nil,nil1 ,quote,quote1,s,s1,sel,sel1,unquote,unquote1} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 3: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: a__fcons(X,Z) -> cons(mark(X),Z) a__fcons(X1,X2) -> fcons(X1,X2) a__first(X1,X2) -> first(X1,X2) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__first1(X1,X2) -> first1(X1,X2) a__first1(0(),Z) -> nil1() a__first1(s(X),cons(Y,Z)) -> cons1(a__quote(Y),a__first1(mark(X),mark(Z))) a__from(X) -> cons(mark(X),from(s(X))) a__from(X) -> from(X) a__quote(X) -> quote(X) a__quote(0()) -> 01() a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X,Z)) -> a__sel1(mark(X),mark(Z)) a__quote1(X) -> quote1(X) a__quote1(cons(X,Z)) -> cons1(a__quote(X),a__quote1(Z)) a__quote1(first(X,Z)) -> a__first1(mark(X),mark(Z)) a__quote1(nil()) -> nil1() a__sel(X1,X2) -> sel(X1,X2) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) a__sel1(X1,X2) -> sel1(X1,X2) a__sel1(0(),cons(X,Z)) -> a__quote(X) a__sel1(s(X),cons(Y,Z)) -> a__sel1(mark(X),mark(Z)) a__unquote(X) -> unquote(X) a__unquote(01()) -> 0() a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(X) -> unquote1(X) a__unquote1(cons1(X,Z)) -> a__fcons(a__unquote(mark(X)),a__unquote1(mark(Z))) a__unquote1(nil1()) -> nil() mark(0()) -> 0() mark(01()) -> 01() mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(cons1(X1,X2)) -> cons1(mark(X1),mark(X2)) mark(fcons(X1,X2)) -> a__fcons(mark(X1),mark(X2)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(first1(X1,X2)) -> a__first1(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(nil()) -> nil() mark(nil1()) -> nil1() mark(quote(X)) -> a__quote(X) mark(quote1(X)) -> a__quote1(X) mark(s(X)) -> s(mark(X)) mark(s1(X)) -> s1(mark(X)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(sel1(X1,X2)) -> a__sel1(mark(X1),mark(X2)) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) - Signature: {a__fcons/2,a__first/2,a__first1/2,a__from/1,a__quote/1,a__quote1/1,a__sel/2,a__sel1/2,a__unquote/1 ,a__unquote1/1,mark/1} / {0/0,01/0,cons/2,cons1/2,fcons/2,first/2,first1/2,from/1,nil/0,nil1/0,quote/1 ,quote1/1,s/1,s1/1,sel/2,sel1/2,unquote/1,unquote1/1} - Obligation: runtime complexity wrt. defined symbols {a__fcons,a__first,a__first1,a__from,a__quote,a__quote1,a__sel ,a__sel1,a__unquote,a__unquote1,mark} and constructors {0,01,cons,cons1,fcons,first,first1,from,nil,nil1 ,quote,quote1,s,s1,sel,sel1,unquote,unquote1} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: a__quote(x){x -> s(x)} = a__quote(s(x)) ->^+ s1(a__quote(x)) = C[a__quote(x) = a__quote(x){}] WORST_CASE(Omega(n^1),?)