Input TRS: 1: active(fib(N)) -> mark(sel(N,fib1(s(0()),s(0())))) 2: active(fib1(X,Y)) -> mark(cons(X,fib1(Y,add(X,Y)))) 3: active(add(0(),X)) -> mark(X) 4: active(add(s(X),Y)) -> mark(s(add(X,Y))) 5: active(sel(0(),cons(X,XS))) -> mark(X) 6: active(sel(s(N),cons(X,XS))) -> mark(sel(N,XS)) 7: active(fib(X)) -> fib(active(X)) 8: active(sel(X1,X2)) -> sel(active(X1),X2) 9: active(sel(X1,X2)) -> sel(X1,active(X2)) 10: active(fib1(X1,X2)) -> fib1(active(X1),X2) 11: active(fib1(X1,X2)) -> fib1(X1,active(X2)) 12: active(s(X)) -> s(active(X)) 13: active(cons(X1,X2)) -> cons(active(X1),X2) 14: active(add(X1,X2)) -> add(active(X1),X2) 15: active(add(X1,X2)) -> add(X1,active(X2)) 16: fib(mark(X)) -> mark(fib(X)) 17: sel(mark(X1),X2) -> mark(sel(X1,X2)) 18: sel(X1,mark(X2)) -> mark(sel(X1,X2)) 19: fib1(mark(X1),X2) -> mark(fib1(X1,X2)) 20: fib1(X1,mark(X2)) -> mark(fib1(X1,X2)) 21: s(mark(X)) -> mark(s(X)) 22: cons(mark(X1),X2) -> mark(cons(X1,X2)) 23: add(mark(X1),X2) -> mark(add(X1,X2)) 24: add(X1,mark(X2)) -> mark(add(X1,X2)) 25: proper(fib(X)) -> fib(proper(X)) 26: proper(sel(X1,X2)) -> sel(proper(X1),proper(X2)) 27: proper(fib1(X1,X2)) -> fib1(proper(X1),proper(X2)) 28: proper(s(X)) -> s(proper(X)) 29: proper(0()) -> ok(0()) 30: proper(cons(X1,X2)) -> cons(proper(X1),proper(X2)) 31: proper(add(X1,X2)) -> add(proper(X1),proper(X2)) 32: fib(ok(X)) -> ok(fib(X)) 33: sel(ok(X1),ok(X2)) -> ok(sel(X1,X2)) 34: fib1(ok(X1),ok(X2)) -> ok(fib1(X1,X2)) 35: s(ok(X)) -> ok(s(X)) 36: cons(ok(X1),ok(X2)) -> ok(cons(X1,X2)) 37: add(ok(X1),ok(X2)) -> ok(add(X1,X2)) 38: top(mark(X)) -> top(proper(X)) 39: top(ok(X)) -> top(active(X)) Number of strict rules: 39 Direct Order(PosReal,>,Poly) ... failed. Freezing ... failed. Dependency Pairs: #1: #active(fib1(X,Y)) -> #cons(X,fib1(Y,add(X,Y))) #2: #active(fib1(X,Y)) -> #fib1(Y,add(X,Y)) #3: #active(fib1(X,Y)) -> #add(X,Y) #4: #s(ok(X)) -> #s(X) #5: #add(ok(X1),ok(X2)) -> #add(X1,X2) #6: #top(mark(X)) -> #top(proper(X)) #7: #top(mark(X)) -> #proper(X) #8: #active(sel(s(N),cons(X,XS))) -> #sel(N,XS) #9: #active(cons(X1,X2)) -> #cons(active(X1),X2) #10: #active(cons(X1,X2)) -> #active(X1) #11: #active(sel(X1,X2)) -> #sel(X1,active(X2)) #12: #active(sel(X1,X2)) -> #active(X2) #13: #active(fib1(X1,X2)) -> #fib1(X1,active(X2)) #14: #active(fib1(X1,X2)) -> #active(X2) #15: #add(X1,mark(X2)) -> #add(X1,X2) #16: #add(mark(X1),X2) -> #add(X1,X2) #17: #active(s(X)) -> #s(active(X)) #18: #active(s(X)) -> #active(X) #19: #proper(add(X1,X2)) -> #add(proper(X1),proper(X2)) #20: #proper(add(X1,X2)) -> #proper(X1) #21: #proper(add(X1,X2)) -> #proper(X2) #22: #active(add(X1,X2)) -> #add(active(X1),X2) #23: #active(add(X1,X2)) -> #active(X1) #24: #proper(cons(X1,X2)) -> #cons(proper(X1),proper(X2)) #25: #proper(cons(X1,X2)) -> #proper(X1) #26: #proper(cons(X1,X2)) -> #proper(X2) #27: #proper(fib(X)) -> #fib(proper(X)) #28: #proper(fib(X)) -> #proper(X) #29: #fib1(X1,mark(X2)) -> #fib1(X1,X2) #30: #active(fib(X)) -> #fib(active(X)) #31: #active(fib(X)) -> #active(X) #32: #top(ok(X)) -> #top(active(X)) #33: #top(ok(X)) -> #active(X) #34: #active(fib1(X1,X2)) -> #fib1(active(X1),X2) #35: #active(fib1(X1,X2)) -> #active(X1) #36: #sel(ok(X1),ok(X2)) -> #sel(X1,X2) #37: #proper(s(X)) -> #s(proper(X)) #38: #proper(s(X)) -> #proper(X) #39: #cons(mark(X1),X2) -> #cons(X1,X2) #40: #fib1(ok(X1),ok(X2)) -> #fib1(X1,X2) #41: #proper(fib1(X1,X2)) -> #fib1(proper(X1),proper(X2)) #42: #proper(fib1(X1,X2)) -> #proper(X1) #43: #proper(fib1(X1,X2)) -> #proper(X2) #44: #sel(mark(X1),X2) -> #sel(X1,X2) #45: #fib(ok(X)) -> #fib(X) #46: #fib1(mark(X1),X2) -> #fib1(X1,X2) #47: #proper(sel(X1,X2)) -> #sel(proper(X1),proper(X2)) #48: #proper(sel(X1,X2)) -> #proper(X1) #49: #proper(sel(X1,X2)) -> #proper(X2) #50: #cons(ok(X1),ok(X2)) -> #cons(X1,X2) #51: #s(mark(X)) -> #s(X) #52: #fib(mark(X)) -> #fib(X) #53: #active(fib(N)) -> #sel(N,fib1(s(0()),s(0()))) #54: #active(fib(N)) -> #fib1(s(0()),s(0())) #55: #active(fib(N)) -> #s(0()) #56: #active(fib(N)) -> #s(0()) #57: #active(sel(X1,X2)) -> #sel(active(X1),X2) #58: #active(sel(X1,X2)) -> #active(X1) #59: #active(add(X1,X2)) -> #add(X1,active(X2)) #60: #active(add(X1,X2)) -> #active(X2) #61: #active(add(s(X),Y)) -> #s(add(X,Y)) #62: #active(add(s(X),Y)) -> #add(X,Y) #63: #sel(X1,mark(X2)) -> #sel(X1,X2) Number of SCCs: 9, DPs: 36, edges: 224 SCC { #4 #51 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: 0 proper(x1) weight: 0 fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: 0 #s(x1) weight: x1 mark(x1) weight: (/ 1 2) + x1 #proper(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 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #4 #51 Number of SCCs: 8, DPs: 34, edges: 220 SCC { #45 #52 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: 0 proper(x1) weight: 0 fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: 0 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(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 #fib(x1) weight: x1 Usable rules: { } Removed DPs: #45 #52 Number of SCCs: 7, DPs: 32, edges: 216 SCC { #6 #32 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... QLPOpS... Order(PosReal,>,MaxSum)... QWPOpS(PosReal,>,MaxSum)... succeeded. #cons(x1,x2) weight: (/ 1 8) status: [] precedence above: s(x1) weight: x1 status: [x1] precedence above: mark top(x1) weight: x1 status: [] precedence above: #top(x1) weight: (/ 1 8) + x1 status: [x1] precedence above: #fib1(x1,x2) weight: (/ 1 8) + x2 status: [x2] precedence above: fib1(x1,x2) weight: max{(/ 1 4) + x2, (/ 1 4) + x1} status: [x1,x2] precedence above: s proper ok mark active cons add proper(x1) weight: x1 status: x1 fib(x1) weight: (/ 5 8) + x1 status: [x1] precedence above: s 0 mark ok(x1) weight: x1 status: x1 0() weight: (/ 1 8) status: [] precedence above: #sel(x1,x2) weight: (/ 1 8) + x2 status: [x2] precedence above: sel(x1,x2) weight: (/ 1 8) + x2 + x1 status: [x1,x2] precedence above: s mark #s(x1) weight: (/ 1 8) status: [] precedence above: mark(x1) weight: x1 status: [x1] precedence above: s #proper(x1) weight: x1 status: [] precedence above: active(x1) weight: x1 status: x1 cons(x1,x2) weight: max{x2, (/ 1 8) + x1} status: [x1] precedence above: s mark #active(x1) weight: x1 status: [] precedence above: #add(x1,x2) weight: (/ 1 8) + x2 status: [x2] precedence above: add(x1,x2) weight: max{x2, x1} status: [x1,x2] precedence above: s ok mark active #fib(x1) weight: (/ 1 8) status: [] precedence above: Usable rules: { 1..37 } Removed DPs: #6 Number of SCCs: 7, DPs: 31, edges: 213 SCC { #32 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: x1 top(x1) weight: 0 #top(x1) weight: x1 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: x1 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: 0 #proper(x1) weight: 0 active(x1) weight: (/ 1 4) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { 1..24 32..37 } Removed DPs: #32 Number of SCCs: 6, DPs: 30, edges: 212 SCC { #39 #50 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: x2 s(x1) weight: x1 top(x1) weight: 0 #top(x1) weight: x1 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: x1 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: 0 #proper(x1) weight: 0 active(x1) weight: (/ 1 4) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #50 Number of SCCs: 7, DPs: 29, edges: 209 SCC { #39 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: x1 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #39 Number of SCCs: 6, DPs: 28, edges: 208 SCC { #36 #44 #63 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: x1 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #36 #44 Number of SCCs: 7, DPs: 26, edges: 200 SCC { #63 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: x2 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #63 Number of SCCs: 6, DPs: 25, edges: 199 SCC { #29 #40 #46 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: x2 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #29 #40 Number of SCCs: 7, DPs: 23, edges: 191 SCC { #46 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: x1 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #46 Number of SCCs: 6, DPs: 22, edges: 190 SCC { #5 #15 #16 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: x2 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #5 #15 Number of SCCs: 7, DPs: 20, edges: 182 SCC { #16 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: 0 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: x2 proper(x1) weight: (/ 1 2) fib(x1) weight: 0 ok(x1) weight: (/ 1 2) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: x2 #s(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: x1 #active(x1) weight: 0 #add(x1,x2) weight: x1 add(x1,x2) weight: x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #16 Number of SCCs: 6, DPs: 19, edges: 181 SCC { #10 #12 #14 #18 #23 #31 #35 #58 #60 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 8) + x1 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: (/ 1 8) + x1 + x2 proper(x1) weight: (/ 1 8) fib(x1) weight: (/ 1 8) + x1 ok(x1) weight: (/ 1 8) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: (/ 1 8) + x1 + x2 #s(x1) weight: 0 mark(x1) weight: x1 #proper(x1) weight: 0 active(x1) weight: (/ 1 2) cons(x1,x2) weight: (/ 1 8) + x1 #active(x1) weight: x1 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 8) + x1 + x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #10 #12 #14 #18 #23 #31 #35 #58 #60 Number of SCCs: 6, DPs: 10, edges: 100 SCC { #20 #21 #25 #26 #28 #38 #42 #43 #48 #49 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 8) + x1 top(x1) weight: 0 #top(x1) weight: 0 #fib1(x1,x2) weight: 0 fib1(x1,x2) weight: (/ 1 8) + x1 + x2 proper(x1) weight: (/ 1 8) fib(x1) weight: (/ 1 8) + x1 ok(x1) weight: (/ 1 8) + x1 0() weight: 0 #sel(x1,x2) weight: 0 sel(x1,x2) weight: (/ 1 8) + x1 + x2 #s(x1) weight: 0 mark(x1) weight: x1 #proper(x1) weight: x1 active(x1) weight: (/ 1 2) cons(x1,x2) weight: (/ 1 8) + x1 + x2 #active(x1) weight: 0 #add(x1,x2) weight: 0 add(x1,x2) weight: (/ 1 8) + x1 + x2 #fib(x1) weight: 0 Usable rules: { } Removed DPs: #20 #21 #25 #26 #28 #38 #42 #43 #48 #49 Number of SCCs: 5, DPs: 0, edges: 0 YES