WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: e1(x1,x1,x,y,z) -> e5(x1,x,y,z) e1(h1(),h2(),x,y,z) -> e2(x,x,y,z,z) e2(x,x,y,z,z) -> e6(x,y,z) e2(f1(),x,y,z,f2()) -> e3(x,y,x,y,y,z,y,z,x,y,z) e2(i(),x,y,z,i()) -> e6(x,y,z) e3(x,y,x,y,y,z,y,z,x,y,z) -> e6(x,y,z) e3(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) -> e4(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) e4(x,x,x,x,x,x,x,x,x,x,x) -> e6(x,x,x) e4(g1(),x1,g2(),x1,g1(),x1,g2(),x1,x,y,z) -> e1(x1,x1,x,y,z) e4(i(),x1,i(),x1,i(),x1,i(),x1,x,y,z) -> e5(x1,x,y,z) e5(i(),x,y,z) -> e6(x,y,z) f1() -> g1() f1() -> g2() f2() -> g1() f2() -> g2() g1() -> h1() g1() -> h2() g2() -> h1() g2() -> h2() h1() -> i() h2() -> i() - Signature: {e1/5,e2/5,e3/11,e4/11,e5/4,f1/0,f2/0,g1/0,g2/0,h1/0,h2/0} / {e6/3,i/0} - Obligation: innermost runtime complexity wrt. defined symbols {e1,e2,e3,e4,e5,f1,f2,g1,g2,h1,h2} and constructors {e6,i} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 3, araTimeout = 60, araFindStrictRules = Nothing, araSmtSolver = Z3} + Details: Signatures used: ---------------- e1 :: [A(0) x A(0) x A(9) x A(4) x A(0)] -(15)-> A(5) e2 :: [A(0) x A(9) x A(4) x A(0) x A(0)] -(12)-> A(5) e3 :: [A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(9) x A(4) x A(0)] -(15)-> A(5) e4 :: [A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(0) x A(9) x A(4) x A(0)] -(14)-> A(5) e5 :: [A(0) x A(9) x A(0) x A(0)] -(10)-> A(6) e6 :: [A(9) x A(0) x A(0)] -(9)-> A(9) e6 :: [A(7) x A(0) x A(0)] -(7)-> A(7) e6 :: [A(13) x A(0) x A(0)] -(13)-> A(13) f1 :: [] -(15)-> A(0) f2 :: [] -(8)-> A(0) g1 :: [] -(6)-> A(0) g2 :: [] -(6)-> A(0) h1 :: [] -(5)-> A(0) h2 :: [] -(1)-> A(0) i :: [] -(0)-> A(0) i :: [] -(0)-> A(6) Cost-free Signatures used: -------------------------- e1 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) e2 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) e3 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) e4 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) e5 :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) e6 :: [A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) f1 :: [] -(0)-> A_cf(0) f2 :: [] -(0)-> A_cf(0) g1 :: [] -(0)-> A_cf(0) g2 :: [] -(0)-> A_cf(0) h1 :: [] -(0)-> A_cf(0) h2 :: [] -(0)-> A_cf(0) i :: [] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- e6_A :: [A(1) x A(0) x A(0)] -(1)-> A(1) i_A :: [] -(0)-> A(1) * Step 2: Open MAYBE - Strict TRS: e1(x1,x1,x,y,z) -> e5(x1,x,y,z) e1(h1(),h2(),x,y,z) -> e2(x,x,y,z,z) e2(x,x,y,z,z) -> e6(x,y,z) e2(f1(),x,y,z,f2()) -> e3(x,y,x,y,y,z,y,z,x,y,z) e2(i(),x,y,z,i()) -> e6(x,y,z) e3(x,y,x,y,y,z,y,z,x,y,z) -> e6(x,y,z) e3(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) -> e4(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) e4(x,x,x,x,x,x,x,x,x,x,x) -> e6(x,x,x) e4(g1(),x1,g2(),x1,g1(),x1,g2(),x1,x,y,z) -> e1(x1,x1,x,y,z) e4(i(),x1,i(),x1,i(),x1,i(),x1,x,y,z) -> e5(x1,x,y,z) e5(i(),x,y,z) -> e6(x,y,z) f1() -> g1() f1() -> g2() f2() -> g1() f2() -> g2() g1() -> h1() g1() -> h2() g2() -> h1() g2() -> h2() h1() -> i() h2() -> i() - Signature: {e1/5,e2/5,e3/11,e4/11,e5/4,f1/0,f2/0,g1/0,g2/0,h1/0,h2/0} / {e6/3,i/0} - Obligation: innermost runtime complexity wrt. defined symbols {e1,e2,e3,e4,e5,f1,f2,g1,g2,h1,h2} and constructors {e6,i} Following problems could not be solved: - Strict TRS: e1(x1,x1,x,y,z) -> e5(x1,x,y,z) e1(h1(),h2(),x,y,z) -> e2(x,x,y,z,z) e2(x,x,y,z,z) -> e6(x,y,z) e2(f1(),x,y,z,f2()) -> e3(x,y,x,y,y,z,y,z,x,y,z) e2(i(),x,y,z,i()) -> e6(x,y,z) e3(x,y,x,y,y,z,y,z,x,y,z) -> e6(x,y,z) e3(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) -> e4(x1,x1,x2,x2,x3,x3,x4,x4,x,y,z) e4(x,x,x,x,x,x,x,x,x,x,x) -> e6(x,x,x) e4(g1(),x1,g2(),x1,g1(),x1,g2(),x1,x,y,z) -> e1(x1,x1,x,y,z) e4(i(),x1,i(),x1,i(),x1,i(),x1,x,y,z) -> e5(x1,x,y,z) e5(i(),x,y,z) -> e6(x,y,z) f1() -> g1() f1() -> g2() f2() -> g1() f2() -> g2() g1() -> h1() g1() -> h2() g2() -> h1() g2() -> h2() h1() -> i() h2() -> i() - Signature: {e1/5,e2/5,e3/11,e4/11,e5/4,f1/0,f2/0,g1/0,g2/0,h1/0,h2/0} / {e6/3,i/0} - Obligation: innermost runtime complexity wrt. defined symbols {e1,e2,e3,e4,e5,f1,f2,g1,g2,h1,h2} and constructors {e6,i} WORST_CASE(?,O(n^1))