Input TRS: 1: active(fst(0(),Z)) -> mark(nil()) 2: active(fst(s(X),cons(Y,Z))) -> mark(cons(Y,fst(X,Z))) 3: active(from(X)) -> mark(cons(X,from(s(X)))) 4: active(add(0(),X)) -> mark(X) 5: active(add(s(X),Y)) -> mark(s(add(X,Y))) 6: active(len(nil())) -> mark(0()) 7: active(len(cons(X,Z))) -> mark(s(len(Z))) 8: active(cons(X1,X2)) -> cons(active(X1),X2) 9: active(fst(X1,X2)) -> fst(active(X1),X2) 10: active(fst(X1,X2)) -> fst(X1,active(X2)) 11: active(from(X)) -> from(active(X)) 12: active(add(X1,X2)) -> add(active(X1),X2) 13: active(add(X1,X2)) -> add(X1,active(X2)) 14: active(len(X)) -> len(active(X)) 15: cons(mark(X1),X2) -> mark(cons(X1,X2)) 16: fst(mark(X1),X2) -> mark(fst(X1,X2)) 17: fst(X1,mark(X2)) -> mark(fst(X1,X2)) 18: from(mark(X)) -> mark(from(X)) 19: add(mark(X1),X2) -> mark(add(X1,X2)) 20: add(X1,mark(X2)) -> mark(add(X1,X2)) 21: len(mark(X)) -> mark(len(X)) 22: proper(0()) -> ok(0()) 23: proper(s(X)) -> s(proper(X)) 24: proper(nil()) -> ok(nil()) 25: proper(cons(X1,X2)) -> cons(proper(X1),proper(X2)) 26: proper(fst(X1,X2)) -> fst(proper(X1),proper(X2)) 27: proper(from(X)) -> from(proper(X)) 28: proper(add(X1,X2)) -> add(proper(X1),proper(X2)) 29: proper(len(X)) -> len(proper(X)) 30: s(ok(X)) -> ok(s(X)) 31: cons(ok(X1),ok(X2)) -> ok(cons(X1,X2)) 32: fst(ok(X1),ok(X2)) -> ok(fst(X1,X2)) 33: from(ok(X)) -> ok(from(X)) 34: add(ok(X1),ok(X2)) -> ok(add(X1,X2)) 35: len(ok(X)) -> ok(len(X)) 36: top(mark(X)) -> top(proper(X)) 37: top(ok(X)) -> top(active(X)) Number of strict rules: 37 Direct Order(PosReal,>,Poly) ... failed. Freezing ... failed. Dependency Pairs: #1: #active(fst(s(X),cons(Y,Z))) -> #cons(Y,fst(X,Z)) #2: #active(fst(s(X),cons(Y,Z))) -> #fst(X,Z) #3: #proper(len(X)) -> #len(proper(X)) #4: #proper(len(X)) -> #proper(X) #5: #len(ok(X)) -> #len(X) #6: #top(ok(X)) -> #top(active(X)) #7: #top(ok(X)) -> #active(X) #8: #active(add(X1,X2)) -> #add(X1,active(X2)) #9: #active(add(X1,X2)) -> #active(X2) #10: #active(fst(X1,X2)) -> #fst(active(X1),X2) #11: #active(fst(X1,X2)) -> #active(X1) #12: #active(from(X)) -> #from(active(X)) #13: #active(from(X)) -> #active(X) #14: #proper(s(X)) -> #s(proper(X)) #15: #proper(s(X)) -> #proper(X) #16: #active(add(X1,X2)) -> #add(active(X1),X2) #17: #active(add(X1,X2)) -> #active(X1) #18: #cons(ok(X1),ok(X2)) -> #cons(X1,X2) #19: #active(len(X)) -> #len(active(X)) #20: #active(len(X)) -> #active(X) #21: #s(ok(X)) -> #s(X) #22: #proper(cons(X1,X2)) -> #cons(proper(X1),proper(X2)) #23: #proper(cons(X1,X2)) -> #proper(X1) #24: #proper(cons(X1,X2)) -> #proper(X2) #25: #add(X1,mark(X2)) -> #add(X1,X2) #26: #active(len(cons(X,Z))) -> #s(len(Z)) #27: #active(len(cons(X,Z))) -> #len(Z) #28: #active(fst(X1,X2)) -> #fst(X1,active(X2)) #29: #active(fst(X1,X2)) -> #active(X2) #30: #from(ok(X)) -> #from(X) #31: #active(add(s(X),Y)) -> #s(add(X,Y)) #32: #active(add(s(X),Y)) -> #add(X,Y) #33: #proper(add(X1,X2)) -> #add(proper(X1),proper(X2)) #34: #proper(add(X1,X2)) -> #proper(X1) #35: #proper(add(X1,X2)) -> #proper(X2) #36: #add(ok(X1),ok(X2)) -> #add(X1,X2) #37: #proper(from(X)) -> #from(proper(X)) #38: #proper(from(X)) -> #proper(X) #39: #fst(X1,mark(X2)) -> #fst(X1,X2) #40: #fst(ok(X1),ok(X2)) -> #fst(X1,X2) #41: #add(mark(X1),X2) -> #add(X1,X2) #42: #proper(fst(X1,X2)) -> #fst(proper(X1),proper(X2)) #43: #proper(fst(X1,X2)) -> #proper(X1) #44: #proper(fst(X1,X2)) -> #proper(X2) #45: #top(mark(X)) -> #top(proper(X)) #46: #top(mark(X)) -> #proper(X) #47: #len(mark(X)) -> #len(X) #48: #fst(mark(X1),X2) -> #fst(X1,X2) #49: #active(from(X)) -> #cons(X,from(s(X))) #50: #active(from(X)) -> #from(s(X)) #51: #active(from(X)) -> #s(X) #52: #active(cons(X1,X2)) -> #cons(active(X1),X2) #53: #active(cons(X1,X2)) -> #active(X1) #54: #cons(mark(X1),X2) -> #cons(X1,X2) #55: #from(mark(X)) -> #from(X) Number of SCCs: 9, DPs: 31, edges: 165 SCC { #21 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: 0 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: 0 #s(x1) weight: x1 nil() weight: 0 mark(x1) weight: 0 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: 0 cons(x1,x2) weight: 0 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: 0 len(x1) weight: 0 Usable rules: { } Removed DPs: #21 Number of SCCs: 8, DPs: 30, edges: 164 SCC { #30 #55 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: 0 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: 0 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: x1 active(x1) weight: 0 cons(x1,x2) weight: 0 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: 0 len(x1) weight: 0 Usable rules: { } Removed DPs: #30 #55 Number of SCCs: 7, DPs: 28, edges: 160 SCC { #5 #47 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: x1 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: 0 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: 0 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: 0 cons(x1,x2) weight: 0 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: 0 len(x1) weight: 0 Usable rules: { } Removed DPs: #5 #47 Number of SCCs: 6, DPs: 26, edges: 156 SCC { #6 #45 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 4) top(x1) weight: 0 fst(x1,x2) weight: (/ 1 4) + x1 + x2 #top(x1) weight: x1 #fst(x1,x2) weight: 0 proper(x1) weight: x1 ok(x1) weight: x1 0() weight: 0 from(x1) weight: (/ 1 2) + x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 4) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: (/ 1 4) + x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 4) + x1 + x2 len(x1) weight: (/ 1 4) + x1 Usable rules: { 1..35 } Removed DPs: #45 Number of SCCs: 6, DPs: 25, edges: 153 SCC { #6 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: x1 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: x1 #fst(x1,x2) weight: 0 proper(x1) weight: (/ 1 2) ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: 0 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: (/ 1 4) + x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x1 len(x1) weight: x1 Usable rules: { 1..21 30..35 } Removed DPs: #6 Number of SCCs: 5, DPs: 24, edges: 152 SCC { #18 #54 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: x2 s(x1) weight: x1 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: x1 #fst(x1,x2) weight: 0 proper(x1) weight: (/ 1 2) ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: 0 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: (/ 1 4) + x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x1 len(x1) weight: x1 Usable rules: { } Removed DPs: #18 Number of SCCs: 6, DPs: 23, edges: 149 SCC { #54 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: x1 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: (/ 1 2) #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 len(x1) weight: x1 Usable rules: { } Removed DPs: #54 Number of SCCs: 5, DPs: 22, edges: 148 SCC { #25 #36 #41 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: (/ 1 2) #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: x2 add(x1,x2) weight: x2 len(x1) weight: x1 Usable rules: { } Removed DPs: #25 #36 Number of SCCs: 6, DPs: 20, edges: 140 SCC { #41 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: (/ 1 2) #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: x1 add(x1,x2) weight: x2 len(x1) weight: x1 Usable rules: { } Removed DPs: #41 Number of SCCs: 5, DPs: 19, edges: 139 SCC { #39 #40 #48 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: 0 #fst(x1,x2) weight: x2 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: (/ 1 2) #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 len(x1) weight: x1 Usable rules: { } Removed DPs: #39 #40 Number of SCCs: 6, DPs: 17, edges: 131 SCC { #48 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x2 #top(x1) weight: 0 #fst(x1,x2) weight: x1 proper(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 from(x1) weight: (/ 1 2) #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 len(x1) weight: x1 Usable rules: { } Removed DPs: #48 Number of SCCs: 5, DPs: 16, edges: 130 SCC { #9 #11 #13 #17 #20 #29 #53 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: x1 + x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 4) + x1 0() weight: 0 from(x1) weight: (/ 1 4) + x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: (/ 1 4) + x1 + x2 #active(x1) weight: x1 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 4) + x1 + x2 len(x1) weight: (/ 1 4) + x1 Usable rules: { } Removed DPs: #9 #13 #17 #20 #53 Number of SCCs: 6, DPs: 11, edges: 85 SCC { #11 #29 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 fst(x1,x2) weight: (/ 1 4) + x1 + x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: 0 ok(x1) weight: (/ 1 4) + x1 0() weight: 0 from(x1) weight: (/ 1 4) + x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: x1 #proper(x1) weight: 0 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: (/ 1 4) + x1 + x2 #active(x1) weight: x1 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 4) + x1 + x2 len(x1) weight: (/ 1 4) + x1 Usable rules: { } Removed DPs: #11 #29 Number of SCCs: 5, DPs: 9, edges: 81 SCC { #4 #15 #23 #24 #34 #35 #38 #43 #44 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 4) + x1 top(x1) weight: 0 fst(x1,x2) weight: (/ 1 4) + x1 + x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: x1 ok(x1) weight: (/ 1 4) + x1 0() weight: 0 from(x1) weight: (/ 1 4) + x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: 0 #proper(x1) weight: x1 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: (/ 1 4) + x1 + x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x1 + x2 len(x1) weight: (/ 1 4) + x1 Usable rules: { } Removed DPs: #4 #15 #23 #24 #38 #43 #44 Number of SCCs: 6, DPs: 2, edges: 4 SCC { #34 #35 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #len(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 4) + x1 top(x1) weight: 0 fst(x1,x2) weight: (/ 1 4) + x1 + x2 #top(x1) weight: 0 #fst(x1,x2) weight: 0 proper(x1) weight: x1 ok(x1) weight: (/ 1 4) + x1 0() weight: 0 from(x1) weight: (/ 1 4) + x1 #s(x1) weight: 0 nil() weight: 0 mark(x1) weight: 0 #proper(x1) weight: x1 #from(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: (/ 1 4) + x1 + x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 4) + x1 + x2 len(x1) weight: (/ 1 4) + x1 Usable rules: { } Removed DPs: #34 #35 Number of SCCs: 5, DPs: 0, edges: 0 YES