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 = MiniSMT} + Details: Signatures used: ---------------- 0 :: [A(0, 0)] -(0)-> A(0, 0) 0 :: [A(2, 0)] -(2)-> A(2, 0) 0 :: [A(4, 0)] -(4)-> A(4, 0) 0 :: [A(0, 0)] -(0)-> A(0, 4) 1 :: [A(2, 0)] -(2)-> A(2, 0) 1 :: [A(0, 0)] -(0)-> A(0, 0) 1 :: [A(4, 0)] -(4)-> A(4, 0) 1 :: [A(3, 0)] -(3)-> A(3, 2) O :: [A(0, 0)] -(0)-> A(0, 0) choice :: [A(6, 0)] -(0)-> A(6, 0) cons :: [A(6, 0) x A(6, 0)] -(6)-> A(6, 0) cons :: [A(7, 0) x A(7, 3)] -(4)-> A(4, 3) cons :: [A(3, 0) x A(3, 0)] -(3)-> A(3, 0) cons :: [A(6, 0) x A(6, 3)] -(3)-> A(3, 3) eq :: [A(0, 0) x A(2, 0)] -(1)-> A(0, 0) false :: [] -(0)-> A(0, 0) false :: [] -(0)-> A(1, 5) false :: [] -(0)-> A(2, 3) guess :: [A(4, 3)] -(1)-> A(3, 3) if :: [A(0, 0) x A(0, 0) x A(0, 0)] -(1)-> A(0, 0) member :: [A(0, 0) x A(3, 0)] -(1)-> A(0, 0) negate :: [A(4, 0)] -(0)-> A(0, 2) nil :: [] -(0)-> A(0, 0) nil :: [] -(0)-> A(2, 0) nil :: [] -(0)-> A(4, 3) nil :: [] -(0)-> A(3, 0) nil :: [] -(0)-> A(3, 3) nil :: [] -(0)-> A(3, 4) sat :: [A(5, 3)] -(7)-> A(0, 0) satck :: [A(0, 0) x A(3, 3)] -(4)-> A(0, 0) true :: [] -(0)-> A(0, 0) true :: [] -(0)-> A(4, 3) true :: [] -(0)-> A(1, 2) unsat :: [] -(0)-> A(0, 0) verify :: [A(3, 3)] -(2)-> A(0, 0) Cost-free Signatures used: -------------------------- 0 :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) 1 :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) O :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) choice :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) choice :: [A_cf(3, 0)] -(0)-> A_cf(3, 0) cons :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) cons :: [A_cf(3, 0) x A_cf(3, 0)] -(3)-> A_cf(3, 0) eq :: [A_cf(0, 0) x A_cf(0, 0)] -(1)-> A_cf(0, 0) eq :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) false :: [] -(0)-> A_cf(0, 0) false :: [] -(0)-> A_cf(0, 4) false :: [] -(0)-> A_cf(1, 0) guess :: [A_cf(3, 0)] -(0)-> A_cf(3, 0) if :: [A_cf(0, 0) x A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) member :: [A_cf(0, 0) x A_cf(0, 0)] -(0)-> A_cf(0, 0) negate :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(0, 0) nil :: [] -(0)-> A_cf(3, 0) true :: [] -(0)-> A_cf(5, 0) true :: [] -(0)-> A_cf(0, 0) verify :: [A_cf(0, 0)] -(0)-> A_cf(0, 0) 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(0, 0)] -(0)-> A(0, 1) O_A :: [A(1, 0)] -(0)-> 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, 0) x A(1, 1)] -(0)-> 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 :: [] -(1)-> 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))