WORST_CASE(?,O(n^2)) * Step 1: Ara WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: choice(cons(x,xs)) -> x choice(cons(x,xs)) -> choice(xs) eq(0(x),1(y)) -> false() eq(1(x),0(y)) -> false() eq(1(x),1(y)) -> eq(x,y) eq(O(x),0(y)) -> eq(x,y) eq(nil(),nil()) -> true() guess(cons(clause,cnf)) -> cons(choice(clause),guess(cnf)) guess(nil()) -> nil() if(false(),t,e) -> e if(true(),t,e) -> t member(x,cons(y,ys)) -> if(eq(x,y),true(),member(x,ys)) member(x,nil()) -> false() negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) sat(cnf) -> satck(cnf,guess(cnf)) satck(cnf,assign) -> if(verify(assign),assign,unsat()) verify(cons(l,ls)) -> if(member(negate(l),ls),false(),verify(ls)) verify(nil()) -> true() - Signature: {choice/1,eq/2,guess/1,if/3,member/2,negate/1,sat/1,satck/2,verify/1} / {0/1,1/1,O/1,cons/2,false/0,nil/0 ,true/0,unsat/0} - Obligation: innermost runtime complexity wrt. defined symbols {choice,eq,guess,if,member,negate,sat,satck ,verify} and constructors {0,1,O,cons,false,nil,true,unsat} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 3, araTimeout = 60, araFindStrictRules = Nothing, araSmtSolver = Z3} + Details: Signatures used: ---------------- 0 :: [A(0, 0)] -(0)-> A(0, 0) 0 :: [A(1, 0)] -(1)-> A(1, 0) 0 :: [A(7, 0)] -(7)-> A(7, 0) 0 :: [A(3, 0)] -(3)-> A(3, 3) 1 :: [A(1, 0)] -(1)-> A(1, 0) 1 :: [A(0, 0)] -(0)-> A(0, 0) 1 :: [A(7, 0)] -(7)-> A(7, 0) 1 :: [A(6, 0)] -(3)-> A(3, 3) O :: [A(0, 0)] -(0)-> A(0, 0) choice :: [A(0, 13)] -(0)-> A(12, 12) cons :: [A(13, 13) x A(13, 13)] -(13)-> A(0, 13) cons :: [A(5, 0) x A(5, 0)] -(5)-> A(5, 0) cons :: [A(12, 12) x A(12, 12)] -(12)-> A(0, 12) eq :: [A(0, 0) x A(1, 0)] -(1)-> A(12, 12) false :: [] -(0)-> A(0, 0) false :: [] -(0)-> A(15, 15) false :: [] -(0)-> A(7, 7) guess :: [A(0, 13)] -(2)-> A(0, 12) if :: [A(0, 0) x A(0, 0) x A(9, 9)] -(1)-> A(0, 0) member :: [A(0, 0) x A(5, 0)] -(4)-> A(0, 0) negate :: [A(7, 0)] -(0)-> A(3, 2) nil :: [] -(0)-> A(0, 0) nil :: [] -(0)-> A(1, 0) nil :: [] -(0)-> A(0, 13) nil :: [] -(0)-> A(5, 0) nil :: [] -(0)-> A(0, 12) nil :: [] -(0)-> A(7, 15) sat :: [A(13, 15)] -(15)-> A(0, 0) satck :: [A(0, 0) x A(0, 12)] -(12)-> A(0, 0) true :: [] -(0)-> A(0, 0) true :: [] -(0)-> A(15, 15) true :: [] -(0)-> A(7, 7) unsat :: [] -(0)-> A(14, 14) verify :: [A(0, 12)] -(3)-> A(0, 0) Cost-free Signatures used: -------------------------- 0 :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) 0 :: [A_cf(0, 0)] -(0)-> A_cf(0, 4) 1 :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) O :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) choice :: [A_cf(13, 0)] -(0)-> A_cf(0, 0) choice :: [A_cf(12, 0)] -(0)-> A_cf(12, 0) cons :: [A_cf(13, 0) x A_cf(13, 0)] -(13)-> A_cf(13, 0) cons :: [A_cf(12, 0) x A_cf(12, 0)] -(12)-> A_cf(12, 0) cons :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) eq :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) eq :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(13, 13) false :: [] -(0)-> A_cf(0, 0) false :: [] -(0)-> A_cf(1, 1) false :: [] -(0)-> A_cf(15, 15) false :: [] -(0)-> A_cf(11, 11) false :: [] -(0)-> A_cf(15, 11) false :: [] -(0)-> A_cf(13, 13) guess :: [A_cf(13, 0)] -(0)-> A_cf(12, 0) if :: [A_cf(1, 1) x A_cf(13, 10) x A_cf(9, 9)] -(0)-> A_cf(9, 9) if :: [A_cf(1, 1) x A_cf(12, 12) x A_cf(12, 12)] -(0)-> A_cf(12, 12) if :: [A_cf(1, 1) x A_cf(14, 6) x A_cf(14, 6)] -(0)-> A_cf(14, 6) member :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(9, 9) member :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(14, 6) negate :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(13, 0) nil :: [] -(0)-> A_cf(15, 2) true :: [] -(0)-> A_cf(0, 0) true :: [] -(0)-> A_cf(1, 1) true :: [] -(0)-> A_cf(15, 15) true :: [] -(0)-> A_cf(13, 13) true :: [] -(0)-> A_cf(14, 14) verify :: [A_cf(0, 0)] -(4)-> A_cf(12, 12) Base Constructor Signatures used: --------------------------------- 0_A :: [A(1, 0)] -(1)-> A(1, 0) 0_A :: [A(0, 0)] -(0)-> A(0, 1) 1_A :: [A(1, 0)] -(1)-> A(1, 0) 1_A :: [A(1, 0)] -(0)-> A(0, 1) O_A :: [A(0, 0)] -(1)-> A(1, 0) O_A :: [A(0, 0)] -(0)-> A(0, 1) cons_A :: [A(1, 0) x A(1, 0)] -(1)-> A(1, 0) cons_A :: [A(1, 1) x A(1, 1)] -(1)-> A(0, 1) false_A :: [] -(0)-> A(1, 0) false_A :: [] -(0)-> A(0, 1) nil_A :: [] -(0)-> A(1, 0) nil_A :: [] -(0)-> A(0, 1) true_A :: [] -(0)-> A(1, 0) true_A :: [] -(0)-> A(0, 1) unsat_A :: [] -(0)-> A(1, 0) unsat_A :: [] -(0)-> A(0, 1) * Step 2: Open MAYBE - Strict TRS: choice(cons(x,xs)) -> x choice(cons(x,xs)) -> choice(xs) eq(0(x),1(y)) -> false() eq(1(x),0(y)) -> false() eq(1(x),1(y)) -> eq(x,y) eq(O(x),0(y)) -> eq(x,y) eq(nil(),nil()) -> true() guess(cons(clause,cnf)) -> cons(choice(clause),guess(cnf)) guess(nil()) -> nil() if(false(),t,e) -> e if(true(),t,e) -> t member(x,cons(y,ys)) -> if(eq(x,y),true(),member(x,ys)) member(x,nil()) -> false() negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) sat(cnf) -> satck(cnf,guess(cnf)) satck(cnf,assign) -> if(verify(assign),assign,unsat()) verify(cons(l,ls)) -> if(member(negate(l),ls),false(),verify(ls)) verify(nil()) -> true() - Signature: {choice/1,eq/2,guess/1,if/3,member/2,negate/1,sat/1,satck/2,verify/1} / {0/1,1/1,O/1,cons/2,false/0,nil/0 ,true/0,unsat/0} - Obligation: innermost runtime complexity wrt. defined symbols {choice,eq,guess,if,member,negate,sat,satck ,verify} and constructors {0,1,O,cons,false,nil,true,unsat} Following problems could not be solved: - Strict TRS: choice(cons(x,xs)) -> x choice(cons(x,xs)) -> choice(xs) eq(0(x),1(y)) -> false() eq(1(x),0(y)) -> false() eq(1(x),1(y)) -> eq(x,y) eq(O(x),0(y)) -> eq(x,y) eq(nil(),nil()) -> true() guess(cons(clause,cnf)) -> cons(choice(clause),guess(cnf)) guess(nil()) -> nil() if(false(),t,e) -> e if(true(),t,e) -> t member(x,cons(y,ys)) -> if(eq(x,y),true(),member(x,ys)) member(x,nil()) -> false() negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) sat(cnf) -> satck(cnf,guess(cnf)) satck(cnf,assign) -> if(verify(assign),assign,unsat()) verify(cons(l,ls)) -> if(member(negate(l),ls),false(),verify(ls)) verify(nil()) -> true() - Signature: {choice/1,eq/2,guess/1,if/3,member/2,negate/1,sat/1,satck/2,verify/1} / {0/1,1/1,O/1,cons/2,false/0,nil/0 ,true/0,unsat/0} - Obligation: innermost runtime complexity wrt. defined symbols {choice,eq,guess,if,member,negate,sat,satck ,verify} and constructors {0,1,O,cons,false,nil,true,unsat} WORST_CASE(?,O(n^2))