WORST_CASE(?,O(n^1)) * Step 1: InnermostRuleRemoval WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: copy(0(),y,z) -> f(z) copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) f(cons(f(cons(nil(),y)),z)) -> copy(n(),y,z) f(cons(nil(),y)) -> y - Signature: {copy/3,f/1} / {0/0,cons/2,n/0,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {copy,f} and constructors {0,cons,n,nil,s} + Applied Processor: InnermostRuleRemoval + Details: Arguments of following rules are not normal-forms. f(cons(f(cons(nil(),y)),z)) -> copy(n(),y,z) All above mentioned rules can be savely removed. * Step 2: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: copy(0(),y,z) -> f(z) copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) f(cons(nil(),y)) -> y - Signature: {copy/3,f/1} / {0/0,cons/2,n/0,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {copy,f} and constructors {0,cons,n,nil,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(15) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(3)] -(3)-> A(3) copy :: [A(15) x A(3) x A(3)] -(14)-> A(0) f :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(0) s :: [A(15)] -(15)-> A(15) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) copy :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) f :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(1)-> A(1) nil_A :: [] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: copy(0(),y,z) -> f(z) 2. Weak: copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) f(cons(nil(),y)) -> y * Step 3: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) f(cons(nil(),y)) -> y - Weak TRS: copy(0(),y,z) -> f(z) - Signature: {copy/3,f/1} / {0/0,cons/2,n/0,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {copy,f} and constructors {0,cons,n,nil,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(12) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(10) copy :: [A(12) x A(1) x A(2)] -(7)-> A(0) f :: [A(0)] -(1)-> A(0) nil :: [] -(0)-> A(0) s :: [A(12)] -(12)-> A(12) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) copy :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) f :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: f(cons(nil(),y)) -> y 2. Weak: copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) * Step 4: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) - Weak TRS: copy(0(),y,z) -> f(z) f(cons(nil(),y)) -> y - Signature: {copy/3,f/1} / {0/0,cons/2,n/0,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {copy,f} and constructors {0,cons,n,nil,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(13) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(6) copy :: [A(13) x A(5) x A(2)] -(9)-> A(0) f :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(0) s :: [A(13)] -(13)-> A(13) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) copy :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) f :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) 2. Weak: * Step 5: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: copy(0(),y,z) -> f(z) copy(s(x),y,z) -> copy(x,y,cons(f(y),z)) f(cons(nil(),y)) -> y - Signature: {copy/3,f/1} / {0/0,cons/2,n/0,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {copy,f} and constructors {0,cons,n,nil,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))