YES Problem: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Proof: DP Processor: DPs: find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) complete#(u,cons(v,S),E) -> complete#(u,S,E) complete#(u,cons(v,S),E) -> find#(u,v,E) complete#(u,cons(v,S),E) -> ite#(find(u,v,E),complete(u,S,E),ff()) clique#(cons(u,K),E) -> clique#(K,E) clique#(cons(u,K),E) -> complete#(u,K,E) clique#(cons(u,K),E) -> ite#(complete(u,K,E),clique(K,E),ff()) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) ADG Processor: DPs: find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) complete#(u,cons(v,S),E) -> complete#(u,S,E) complete#(u,cons(v,S),E) -> find#(u,v,E) complete#(u,cons(v,S),E) -> ite#(find(u,v,E),complete(u,S,E),ff()) clique#(cons(u,K),E) -> clique#(K,E) clique#(cons(u,K),E) -> complete#(u,K,E) clique#(cons(u,K),E) -> ite#(complete(u,K,E),clique(K,E),ff()) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) graph: clique#(cons(u,K),E) -> clique#(K,E) -> clique#(cons(u,K),E) -> clique#(K,E) clique#(cons(u,K),E) -> clique#(K,E) -> clique#(cons(u,K),E) -> complete#(u,K,E) clique#(cons(u,K),E) -> clique#(K,E) -> clique#(cons(u,K),E) -> ite#(complete(u,K,E),clique(K,E),ff()) clique#(cons(u,K),E) -> complete#(u,K,E) -> complete#(u,cons(v,S),E) -> complete#(u,S,E) clique#(cons(u,K),E) -> complete#(u,K,E) -> complete#(u,cons(v,S),E) -> find#(u,v,E) clique#(cons(u,K),E) -> complete#(u,K,E) -> complete#(u,cons(v,S),E) -> ite#(find(u,v,E),complete(u,S,E),ff()) complete#(u,cons(v,S),E) -> complete#(u,S,E) -> complete#(u,cons(v,S),E) -> complete#(u,S,E) complete#(u,cons(v,S),E) -> complete#(u,S,E) -> complete#(u,cons(v,S),E) -> find#(u,v,E) complete#(u,cons(v,S),E) -> complete#(u,S,E) -> complete#(u,cons(v,S),E) -> ite#(find(u,v,E),complete(u,S,E),ff()) complete#(u,cons(v,S),E) -> find#(u,v,E) -> find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) -> find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) Restore Modifier: DPs: find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) complete#(u,cons(v,S),E) -> complete#(u,S,E) complete#(u,cons(v,S),E) -> find#(u,v,E) complete#(u,cons(v,S),E) -> ite#(find(u,v,E),complete(u,S,E),ff()) clique#(cons(u,K),E) -> clique#(K,E) clique#(cons(u,K),E) -> complete#(u,K,E) clique#(cons(u,K),E) -> ite#(complete(u,K,E),clique(K,E),ff()) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) SCC Processor: #sccs: 3 #rules: 3 #arcs: 11/49 DPs: clique#(cons(u,K),E) -> clique#(K,E) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Matrix Interpretation Processor: dimension: 1 interpretation: [clique#](x0, x1) = x0 + 1, [clique](x0, x1) = 0, [complete](x0, x1, x2) = 0, [cons](x0, x1) = x1 + 1, [find](x0, x1, x2) = 0, [nil] = 0, [ff] = 0, [ite](x0, x1, x2) = x1 + x2, [tt] = 0 orientation: clique#(cons(u,K),E) = K + 2 >= K + 1 = clique#(K,E) ite(tt(),u,v) = u + v >= u = u ite(ff(),u,v) = u + v >= v = v find(u,v,nil()) = 0 >= 0 = ff() find(u,v,cons(cons(u,v),E)) = 0 >= 0 = tt() find(u,v,cons(cons(u2,v2),E)) = 0 >= 0 = find(u,v,E) complete(u,nil(),E) = 0 >= 0 = tt() complete(u,cons(v,S),E) = 0 >= 0 = ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) = 0 >= 0 = tt() clique(cons(u,K),E) = 0 >= 0 = ite(complete(u,K,E),clique(K,E),ff()) problem: DPs: TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Qed DPs: complete#(u,cons(v,S),E) -> complete#(u,S,E) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Matrix Interpretation Processor: dimension: 1 interpretation: [complete#](x0, x1, x2) = x1, [clique](x0, x1) = 0, [complete](x0, x1, x2) = 0, [cons](x0, x1) = x0 + x1 + 1, [find](x0, x1, x2) = 0, [nil] = 0, [ff] = 0, [ite](x0, x1, x2) = x1 + x2, [tt] = 0 orientation: complete#(u,cons(v,S),E) = S + v + 1 >= S = complete#(u,S,E) ite(tt(),u,v) = u + v >= u = u ite(ff(),u,v) = u + v >= v = v find(u,v,nil()) = 0 >= 0 = ff() find(u,v,cons(cons(u,v),E)) = 0 >= 0 = tt() find(u,v,cons(cons(u2,v2),E)) = 0 >= 0 = find(u,v,E) complete(u,nil(),E) = 0 >= 0 = tt() complete(u,cons(v,S),E) = 0 >= 0 = ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) = 0 >= 0 = tt() clique(cons(u,K),E) = 0 >= 0 = ite(complete(u,K,E),clique(K,E),ff()) problem: DPs: TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Qed DPs: find#(u,v,cons(cons(u2,v2),E)) -> find#(u,v,E) TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Matrix Interpretation Processor: dimension: 1 interpretation: [find#](x0, x1, x2) = x2 + 1, [clique](x0, x1) = 0, [complete](x0, x1, x2) = 0, [cons](x0, x1) = x1 + 1, [find](x0, x1, x2) = 0, [nil] = 0, [ff] = 0, [ite](x0, x1, x2) = x1 + x2, [tt] = 0 orientation: find#(u,v,cons(cons(u2,v2),E)) = E + 2 >= E + 1 = find#(u,v,E) ite(tt(),u,v) = u + v >= u = u ite(ff(),u,v) = u + v >= v = v find(u,v,nil()) = 0 >= 0 = ff() find(u,v,cons(cons(u,v),E)) = 0 >= 0 = tt() find(u,v,cons(cons(u2,v2),E)) = 0 >= 0 = find(u,v,E) complete(u,nil(),E) = 0 >= 0 = tt() complete(u,cons(v,S),E) = 0 >= 0 = ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) = 0 >= 0 = tt() clique(cons(u,K),E) = 0 >= 0 = ite(complete(u,K,E),clique(K,E),ff()) problem: DPs: TRS: ite(tt(),u,v) -> u ite(ff(),u,v) -> v find(u,v,nil()) -> ff() find(u,v,cons(cons(u,v),E)) -> tt() find(u,v,cons(cons(u2,v2),E)) -> find(u,v,E) complete(u,nil(),E) -> tt() complete(u,cons(v,S),E) -> ite(find(u,v,E),complete(u,S,E),ff()) clique(nil(),E) -> tt() clique(cons(u,K),E) -> ite(complete(u,K,E),clique(K,E),ff()) Qed