WORST_CASE(?,O(n^2)) * Step 1: Ara WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: append(@l1,@l2) -> append#1(@l1,@l2) append#1(::(@x,@xs),@l2) -> ::(@x,append(@xs,@l2)) append#1(nil(),@l2) -> @l2 subtrees(@t) -> subtrees#1(@t) subtrees#1(leaf()) -> nil() subtrees#1(node(@x,@t1,@t2)) -> subtrees#2(subtrees(@t1),@t1,@t2,@x) subtrees#2(@l1,@t1,@t2,@x) -> subtrees#3(subtrees(@t2),@l1,@t1,@t2,@x) subtrees#3(@l2,@l1,@t1,@t2,@x) -> ::(node(@x,@t1,@t2),append(@l1,@l2)) - Signature: {append/2,append#1/2,subtrees/1,subtrees#1/1,subtrees#2/4,subtrees#3/5} / {::/2,leaf/0,nil/0,node/3} - Obligation: innermost runtime complexity wrt. defined symbols {append,append#1,subtrees,subtrees#1,subtrees#2 ,subtrees#3} and constructors {::,leaf,nil,node} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 3, araTimeout = 60, araFindStrictRules = Nothing, araSmtSolver = Z3} + Details: Signatures used: ---------------- :: :: [A(0, 0) x A(15, 0)] -(15)-> A(15, 0) :: :: [A(0, 0) x A(1, 0)] -(1)-> A(1, 0) :: :: [A(0, 0) x A(0, 0)] -(0)-> A(0, 1) append :: [A(15, 0) x A(3, 0)] -(2)-> A(1, 0) append#1 :: [A(15, 0) x A(3, 0)] -(1)-> A(1, 0) leaf :: [] -(0)-> A(0, 15) nil :: [] -(0)-> A(15, 0) nil :: [] -(0)-> A(7, 7) node :: [A(15, 15) x A(15, 15) x A(15, 15)] -(15)-> A(0, 15) node :: [A(0, 0) x A(0, 0) x A(0, 0)] -(0)-> A(0, 0) subtrees :: [A(7, 15)] -(4)-> A(7, 1) subtrees#1 :: [A(0, 15)] -(3)-> A(0, 1) subtrees#2 :: [A(15, 1) x A(0, 0) x A(7, 15) x A(7, 0)] -(8)-> A(0, 1) subtrees#3 :: [A(4, 3) x A(15, 1) x A(0, 0) x A(0, 0) x A(1, 0)] -(3)-> A(0, 1) Cost-free Signatures used: -------------------------- :: :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) :: :: [A_cf(0, 0) x A_cf(7, 0)] -(7)-> A_cf(7, 2) :: :: [A_cf(0, 0) x A_cf(7, 0)] -(7)-> A_cf(7, 0) :: :: [A_cf(0, 0) x A_cf(7, 0)] -(7)-> A_cf(7, 8) :: :: [A_cf(0, 0) x A_cf(8, 0)] -(8)-> A_cf(8, 8) :: :: [A_cf(0, 0) x A_cf(8, 0)] -(8)-> A_cf(8, 0) :: :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 10) :: :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 8) append :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) append :: [A_cf(7, 0) x A_cf(7, 0)] -(0)-> A_cf(7, 0) append :: [A_cf(8, 0) x A_cf(8, 0)] -(0)-> A_cf(8, 0) append :: [A_cf(0, 0) x A_cf(0, 8)] -(0)-> A_cf(0, 8) append#1 :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) append#1 :: [A_cf(7, 0) x A_cf(7, 0)] -(0)-> A_cf(7, 0) append#1 :: [A_cf(8, 0) x A_cf(8, 0)] -(0)-> A_cf(8, 0) append#1 :: [A_cf(0, 0) x A_cf(0, 8)] -(0)-> A_cf(0, 8) leaf :: [] -(0)-> A_cf(7, 0) leaf :: [] -(0)-> A_cf(8, 0) leaf :: [] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(11, 2) nil :: [] -(0)-> A_cf(7, 0) nil :: [] -(0)-> A_cf(2, 2) nil :: [] -(0)-> A_cf(10, 2) nil :: [] -(0)-> A_cf(8, 0) nil :: [] -(0)-> A_cf(2, 10) node :: [A_cf(7, 0) x A_cf(7, 0) x A_cf(7, 0)] -(7)-> A_cf(7, 0) node :: [A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) node :: [A_cf(8, 0) x A_cf(8, 0) x A_cf(8, 0)] -(8)-> A_cf(8, 0) subtrees :: [A_cf(7, 0)] -(0)-> A_cf(7, 0) subtrees :: [A_cf(8, 0)] -(0)-> A_cf(0, 0) subtrees :: [A_cf(8, 0)] -(0)-> A_cf(8, 0) subtrees :: [A_cf(0, 0)] -(0)-> A_cf(0, 8) subtrees#1 :: [A_cf(7, 0)] -(0)-> A_cf(7, 0) subtrees#1 :: [A_cf(8, 0)] -(0)-> A_cf(0, 0) subtrees#1 :: [A_cf(8, 0)] -(0)-> A_cf(8, 0) subtrees#1 :: [A_cf(0, 0)] -(0)-> A_cf(0, 8) subtrees#2 :: [A_cf(7, 0) x A_cf(0, 0) x A_cf(7, 0) x A_cf(2, 0)] -(7)-> A_cf(7, 0) subtrees#2 :: [A_cf(0, 0) x A_cf(0, 0) x A_cf(8, 0) x A_cf(0, 0)] -(4)-> A_cf(0, 0) subtrees#2 :: [A_cf(8, 0) x A_cf(0, 0) x A_cf(8, 0) x A_cf(0, 0)] -(8)-> A_cf(8, 0) subtrees#2 :: [A_cf(0, 8) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 8) subtrees#3 :: [A_cf(7, 0) x A_cf(7, 0) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(7)-> A_cf(7, 0) subtrees#3 :: [A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(4)-> A_cf(0, 0) subtrees#3 :: [A_cf(8, 0) x A_cf(8, 0) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(8)-> A_cf(8, 0) subtrees#3 :: [A_cf(0, 8) x A_cf(0, 2) x A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 8) Base Constructor Signatures used: --------------------------------- ::_A :: [A(0) x A(0)] -(0)-> A(0) leaf_A :: [] -(0)-> A(1, 0) leaf_A :: [] -(0)-> A(0, 1) nil_A :: [] -(0)-> A(1, 0) nil_A :: [] -(0)-> A(0, 1) node_A :: [A(1, 0) x A(1, 0) x A(1, 0)] -(1)-> A(1, 0) node_A :: [A(1, 1) x A(1, 1) x A(1, 1)] -(1)-> A(0, 1) * Step 2: Open MAYBE - Strict TRS: append(@l1,@l2) -> append#1(@l1,@l2) append#1(::(@x,@xs),@l2) -> ::(@x,append(@xs,@l2)) append#1(nil(),@l2) -> @l2 subtrees(@t) -> subtrees#1(@t) subtrees#1(leaf()) -> nil() subtrees#1(node(@x,@t1,@t2)) -> subtrees#2(subtrees(@t1),@t1,@t2,@x) subtrees#2(@l1,@t1,@t2,@x) -> subtrees#3(subtrees(@t2),@l1,@t1,@t2,@x) subtrees#3(@l2,@l1,@t1,@t2,@x) -> ::(node(@x,@t1,@t2),append(@l1,@l2)) - Signature: {append/2,append#1/2,subtrees/1,subtrees#1/1,subtrees#2/4,subtrees#3/5} / {::/2,leaf/0,nil/0,node/3} - Obligation: innermost runtime complexity wrt. defined symbols {append,append#1,subtrees,subtrees#1,subtrees#2 ,subtrees#3} and constructors {::,leaf,nil,node} Following problems could not be solved: - Strict TRS: append(@l1,@l2) -> append#1(@l1,@l2) append#1(::(@x,@xs),@l2) -> ::(@x,append(@xs,@l2)) append#1(nil(),@l2) -> @l2 subtrees(@t) -> subtrees#1(@t) subtrees#1(leaf()) -> nil() subtrees#1(node(@x,@t1,@t2)) -> subtrees#2(subtrees(@t1),@t1,@t2,@x) subtrees#2(@l1,@t1,@t2,@x) -> subtrees#3(subtrees(@t2),@l1,@t1,@t2,@x) subtrees#3(@l2,@l1,@t1,@t2,@x) -> ::(node(@x,@t1,@t2),append(@l1,@l2)) - Signature: {append/2,append#1/2,subtrees/1,subtrees#1/1,subtrees#2/4,subtrees#3/5} / {::/2,leaf/0,nil/0,node/3} - Obligation: innermost runtime complexity wrt. defined symbols {append,append#1,subtrees,subtrees#1,subtrees#2 ,subtrees#3} and constructors {::,leaf,nil,node} WORST_CASE(?,O(n^2))