/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We split firstr-order part and higher-order part, and do modular checking by a general modularity. ******** FO SN check ******** Check SN using NaTT (Nagoya Termination Tool) Input TRS: 1: active(from(X)) -> mark(cons(X,from(s(X)))) 2: active(sel(0(),cons(Y,U))) -> mark(Y) 3: active(sel(s(V),cons(W,P))) -> mark(sel(V,P)) 4: active(minus(X1,0())) -> mark(0()) 5: active(minus(s(Y1),s(U1))) -> mark(minus(Y1,U1)) 6: active(quot(0(),s(V1))) -> mark(0()) 7: active(quot(s(W1),s(P1))) -> mark(s(quot(minus(W1,P1),s(P1)))) 8: active(zWquot(X2,nil())) -> mark(nil()) 9: active(zWquot(nil(),Y2)) -> mark(nil()) 10: active(zWquot(cons(U2,V2),cons(W2,P2))) -> mark(cons(quot(U2,W2),zWquot(V2,P2))) 11: mark(from(X3)) -> active(from(mark(X3))) 12: mark(cons(Y3,U3)) -> active(cons(mark(Y3),U3)) 13: mark(s(V3)) -> active(s(mark(V3))) 14: mark(sel(W3,P3)) -> active(sel(mark(W3),mark(P3))) 15: mark(0()) -> active(0()) 16: mark(minus(X4,Y4)) -> active(minus(mark(X4),mark(Y4))) 17: mark(quot(U4,V4)) -> active(quot(mark(U4),mark(V4))) 18: mark(zWquot(W4,P4)) -> active(zWquot(mark(W4),mark(P4))) 19: mark(nil()) -> active(nil()) 20: from(mark(X5)) -> from(X5) 21: from(active(Y5)) -> from(Y5) 22: cons(mark(U5),V5) -> cons(U5,V5) 23: cons(W5,mark(P5)) -> cons(W5,P5) 24: cons(active(X6),Y6) -> cons(X6,Y6) 25: cons(U6,active(V6)) -> cons(U6,V6) 26: s(mark(W6)) -> s(W6) 27: s(active(P6)) -> s(P6) 28: sel(mark(X7),Y7) -> sel(X7,Y7) 29: sel(U7,mark(V7)) -> sel(U7,V7) 30: sel(active(W7),P7) -> sel(W7,P7) 31: sel(X8,active(Y8)) -> sel(X8,Y8) 32: minus(mark(U8),V8) -> minus(U8,V8) 33: minus(W8,mark(P8)) -> minus(W8,P8) 34: minus(active(X9),Y9) -> minus(X9,Y9) 35: minus(U9,active(V9)) -> minus(U9,V9) 36: quot(mark(W9),P9) -> quot(W9,P9) 37: quot(X10,mark(Y10)) -> quot(X10,Y10) 38: quot(active(U10),V10) -> quot(U10,V10) 39: quot(W10,active(P10)) -> quot(W10,P10) 40: zWquot(mark(X11),Y11) -> zWquot(X11,Y11) 41: zWquot(U11,mark(V11)) -> zWquot(U11,V11) 42: zWquot(active(W11),P11) -> zWquot(W11,P11) 43: zWquot(X12,active(Y12)) -> zWquot(X12,Y12) 44: _(X1,X2) -> X1 45: _(X1,X2) -> X2 Number of strict rules: 45 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #active(sel(0(),cons(Y,U))) -> #mark(Y) #2: #zWquot(X12,active(Y12)) -> #zWquot(X12,Y12) #3: #sel(U7,mark(V7)) -> #sel(U7,V7) #4: #minus(U9,active(V9)) -> #minus(U9,V9) #5: #zWquot(active(W11),P11) -> #zWquot(W11,P11) #6: #zWquot(U11,mark(V11)) -> #zWquot(U11,V11) #7: #quot(X10,mark(Y10)) -> #quot(X10,Y10) #8: #quot(active(U10),V10) -> #quot(U10,V10) #9: #active(quot(0(),s(V1))) -> #mark(0()) #10: #zWquot(mark(X11),Y11) -> #zWquot(X11,Y11) #11: #mark(s(V3)) -> #active(s(mark(V3))) #12: #mark(s(V3)) -> #s(mark(V3)) #13: #mark(s(V3)) -> #mark(V3) #14: #active(zWquot(nil(),Y2)) -> #mark(nil()) #15: #mark(from(X3)) -> #active(from(mark(X3))) #16: #mark(from(X3)) -> #from(mark(X3)) #17: #mark(from(X3)) -> #mark(X3) #18: #cons(active(X6),Y6) -> #cons(X6,Y6) #19: #cons(W5,mark(P5)) -> #cons(W5,P5) #20: #mark(cons(Y3,U3)) -> #active(cons(mark(Y3),U3)) #21: #mark(cons(Y3,U3)) -> #cons(mark(Y3),U3) #22: #mark(cons(Y3,U3)) -> #mark(Y3) #23: #sel(X8,active(Y8)) -> #sel(X8,Y8) #24: #mark(sel(W3,P3)) -> #active(sel(mark(W3),mark(P3))) #25: #mark(sel(W3,P3)) -> #sel(mark(W3),mark(P3)) #26: #mark(sel(W3,P3)) -> #mark(W3) #27: #mark(sel(W3,P3)) -> #mark(P3) #28: #sel(active(W7),P7) -> #sel(W7,P7) #29: #cons(U6,active(V6)) -> #cons(U6,V6) #30: #from(mark(X5)) -> #from(X5) #31: #active(quot(s(W1),s(P1))) -> #mark(s(quot(minus(W1,P1),s(P1)))) #32: #active(quot(s(W1),s(P1))) -> #s(quot(minus(W1,P1),s(P1))) #33: #active(quot(s(W1),s(P1))) -> #quot(minus(W1,P1),s(P1)) #34: #active(quot(s(W1),s(P1))) -> #minus(W1,P1) #35: #quot(W10,active(P10)) -> #quot(W10,P10) #36: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #mark(cons(quot(U2,W2),zWquot(V2,P2))) #37: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #cons(quot(U2,W2),zWquot(V2,P2)) #38: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #quot(U2,W2) #39: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #zWquot(V2,P2) #40: #minus(W8,mark(P8)) -> #minus(W8,P8) #41: #active(minus(s(Y1),s(U1))) -> #mark(minus(Y1,U1)) #42: #active(minus(s(Y1),s(U1))) -> #minus(Y1,U1) #43: #sel(mark(X7),Y7) -> #sel(X7,Y7) #44: #cons(mark(U5),V5) -> #cons(U5,V5) #45: #minus(active(X9),Y9) -> #minus(X9,Y9) #46: #s(active(P6)) -> #s(P6) #47: #mark(quot(U4,V4)) -> #active(quot(mark(U4),mark(V4))) #48: #mark(quot(U4,V4)) -> #quot(mark(U4),mark(V4)) #49: #mark(quot(U4,V4)) -> #mark(U4) #50: #mark(quot(U4,V4)) -> #mark(V4) #51: #minus(mark(U8),V8) -> #minus(U8,V8) #52: #mark(nil()) -> #active(nil()) #53: #s(mark(W6)) -> #s(W6) #54: #quot(mark(W9),P9) -> #quot(W9,P9) #55: #from(active(Y5)) -> #from(Y5) #56: #mark(minus(X4,Y4)) -> #active(minus(mark(X4),mark(Y4))) #57: #mark(minus(X4,Y4)) -> #minus(mark(X4),mark(Y4)) #58: #mark(minus(X4,Y4)) -> #mark(X4) #59: #mark(minus(X4,Y4)) -> #mark(Y4) #60: #active(sel(s(V),cons(W,P))) -> #mark(sel(V,P)) #61: #active(sel(s(V),cons(W,P))) -> #sel(V,P) #62: #active(from(X)) -> #mark(cons(X,from(s(X)))) #63: #active(from(X)) -> #cons(X,from(s(X))) #64: #active(from(X)) -> #from(s(X)) #65: #active(from(X)) -> #s(X) #66: #active(zWquot(X2,nil())) -> #mark(nil()) #67: #mark(0()) -> #active(0()) #68: #active(minus(X1,0())) -> #mark(0()) #69: #mark(zWquot(W4,P4)) -> #active(zWquot(mark(W4),mark(P4))) #70: #mark(zWquot(W4,P4)) -> #zWquot(mark(W4),mark(P4)) #71: #mark(zWquot(W4,P4)) -> #mark(W4) #72: #mark(zWquot(W4,P4)) -> #mark(P4) Number of SCCs: 8, DPs: 46 SCC { #30 #55 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: x1 active w: x1 + 7720 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #30 #55 Number of SCCs: 7, DPs: 44 SCC { #46 #53 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: x1 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 1797 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #46 #53 Number of SCCs: 6, DPs: 42 SCC { #4 #40 #45 #51 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: x1 #_ w: 0 #from w: 0 active w: x1 + 2283 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #45 #51 Number of SCCs: 6, DPs: 40 SCC { #4 #40 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: x2 #_ w: 0 #from w: 0 active w: x1 + 8099 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #4 #40 Number of SCCs: 5, DPs: 38 SCC { #7 #8 #35 #54 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 282 cons w: 0 #active w: 0 #quot w: x1 USABLE RULES: { } Removed DPs: #8 #54 Number of SCCs: 5, DPs: 36 SCC { #7 #35 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 6284 cons w: 0 #active w: 0 #quot w: x2 USABLE RULES: { } Removed DPs: #7 #35 Number of SCCs: 4, DPs: 34 SCC { #18 #19 #29 #44 } POLO(Sum)... succeeded. #cons w: x1 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 4680 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #18 #44 Number of SCCs: 4, DPs: 32 SCC { #19 #29 } POLO(Sum)... succeeded. #cons w: x2 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 5905 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #19 #29 Number of SCCs: 3, DPs: 30 SCC { #3 #23 #28 #43 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: x2 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 1324 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #3 #23 Number of SCCs: 3, DPs: 28 SCC { #28 #43 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: x1 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 2276 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #28 #43 Number of SCCs: 2, DPs: 26 SCC { #2 #5 #6 #10 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: x1 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 841 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #5 #10 Number of SCCs: 2, DPs: 24 SCC { #2 #6 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: x2 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 3610 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #2 #6 Number of SCCs: 1, DPs: 22 SCC { #1 #13 #15 #17 #22 #24 #26 #27 #31 #36 #41 #47 #49 #50 #56 #58..60 #62 #69 #71 #72 } POLO(Sum)... POLO(max)... succeeded. #cons w: 0 s w: x1 #zWquot w: 0 minus w: max(x1, x2 + 1) zWquot w: max(x1 + 5, x2 + 7) _ w: 0 #mark w: x1 + 1 0 w: 9535 quot w: max(x1 + 1, x2 + 3) #sel w: 0 from w: x1 + 8223 sel w: max(x1 + 870, x2 + 868) #s w: 0 nil w: 8 mark w: x1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 cons w: max(x1 + 1, x2) #active w: x1 + 1 #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #1 #17 #22 #26 #27 #49 #50 #59 #71 #72 Number of SCCs: 2, DPs: 8 SCC { #24 #60 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded. #cons s: [1] p: 0 w: max(x1) s s: [1] p: 1 w: x1 #zWquot s: [1] p: 0 w: x1 + 1 minus s: [] p: 1 w: 0 zWquot s: [1] p: 4 w: x1 + x2 + 19384 _ s: [1] p: 0 w: x1 #mark s: [1] p: 0 w: x1 0 s: [] p: 1 w: 0 quot s: [1] p: 3 w: max(x1 + 625, x2 + 9495) #sel s: [1,2] p: 0 w: x1 + x2 from s: [] p: 4 w: x1 + 3649 sel s: [1,2] p: 2 w: x1 + x2 + 4260 #s s: [] p: 0 w: 0 nil s: [] p: 5 w: 1392 mark s: 1 #minus s: [] p: 0 w: max(x1) #_ s: [2] p: 0 w: x2 + 1 #from s: [] p: 0 w: 1 active s: 1 cons s: [1] p: 3 w: max(x1 + 625, x2) #active s: [1] p: 0 w: x1 #quot s: [] p: 0 w: 0 USABLE RULES: { 1..43 } Removed DPs: #60 Number of SCCs: 1, DPs: 6 SCC { #13 #31 #41 #47 #56 #58 } POLO(Sum)... POLO(max)... succeeded. #cons w: 0 s w: x1 #zWquot w: 0 minus w: max(x1 + 9620, x2 + 15954) zWquot w: max(x2 + 9559) _ w: 0 #mark w: x1 + 1 0 w: 0 quot w: max(x2 + 6933) #sel w: 0 from w: x1 sel w: max(x2) #s w: 0 nil w: 2748 mark w: x1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 cons w: max(x1, x2) #active w: x1 + 1 #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #58 Number of SCCs: 2, DPs: 5 SCC { #41 #56 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded. #cons w: 0 s w: max(x1 + 1948, 0) #zWquot w: 0 minus w: max(x1, 0) zWquot w: max(x1 + 3600, 0) _ w: 0 #mark w: max(x1 + 1, 0) 0 w: 0 quot w: max(x1 + 3600, 0) #sel w: max(x1 - 1, 0) from w: max(x1 + 8760, 0) sel w: max(x1 + x2 + 4722, 0) #s w: max(x1 - 1, 0) nil w: 1 mark w: max(x1, 0) #minus w: 0 #_ w: max(x2 - 1, 0) #from w: 0 active w: max(x1, 0) cons w: max(x1 - 1949, x2 - 1948, 0) #active w: max(x1 - 1, 0) #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #41 #56 Number of SCCs: 1, DPs: 3 SCC { #13 #31 #47 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded. #cons w: 0 s w: max(x1 + 798, 0) #zWquot w: 0 minus w: max(x1, 0) zWquot w: max(x1 + 7473, 0) _ w: 0 #mark w: max(x1 + 1, 0) 0 w: 0 quot w: max(x1 + 6966, 0) #sel w: max(x1 - 1, 0) from w: max(x1 + 7919, 0) sel w: max(x1 + x2 + 4259, 0) #s w: max(x1 - 1, 0) nil w: 1 mark w: max(x1, 0) #minus w: 0 #_ w: max(x2 - 1, 0) #from w: 0 active w: max(x1, 0) cons w: max(x1 - 1981, x2 - 798, 0) #active w: max(x1 + 1, 0) #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #13 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: active(from(X)) -> mark(cons(X,from(s(X)))) 2: active(sel(0(),cons(Y,U))) -> mark(Y) 3: active(sel(s(V),cons(W,P))) -> mark(sel(V,P)) 4: active(minus(X1,0())) -> mark(0()) 5: active(minus(s(Y1),s(U1))) -> mark(minus(Y1,U1)) 6: active(quot(0(),s(V1))) -> mark(0()) 7: active(quot(s(W1),s(P1))) -> mark(s(quot(minus(W1,P1),s(P1)))) 8: active(zWquot(X2,nil())) -> mark(nil()) 9: active(zWquot(nil(),Y2)) -> mark(nil()) 10: active(zWquot(cons(U2,V2),cons(W2,P2))) -> mark(cons(quot(U2,W2),zWquot(V2,P2))) 11: mark(from(X3)) -> active(from(mark(X3))) 12: mark(cons(Y3,U3)) -> active(cons(mark(Y3),U3)) 13: mark(s(V3)) -> active(s(mark(V3))) 14: mark(sel(W3,P3)) -> active(sel(mark(W3),mark(P3))) 15: mark(0()) -> active(0()) 16: mark(minus(X4,Y4)) -> active(minus(mark(X4),mark(Y4))) 17: mark(quot(U4,V4)) -> active(quot(mark(U4),mark(V4))) 18: mark(zWquot(W4,P4)) -> active(zWquot(mark(W4),mark(P4))) 19: mark(nil()) -> active(nil()) 20: from(mark(X5)) -> from(X5) 21: from(active(Y5)) -> from(Y5) 22: cons(mark(U5),V5) -> cons(U5,V5) 23: cons(W5,mark(P5)) -> cons(W5,P5) 24: cons(active(X6),Y6) -> cons(X6,Y6) 25: cons(U6,active(V6)) -> cons(U6,V6) 26: s(mark(W6)) -> s(W6) 27: s(active(P6)) -> s(P6) 28: sel(mark(X7),Y7) -> sel(X7,Y7) 29: sel(U7,mark(V7)) -> sel(U7,V7) 30: sel(active(W7),P7) -> sel(W7,P7) 31: sel(X8,active(Y8)) -> sel(X8,Y8) 32: minus(mark(U8),V8) -> minus(U8,V8) 33: minus(W8,mark(P8)) -> minus(W8,P8) 34: minus(active(X9),Y9) -> minus(X9,Y9) 35: minus(U9,active(V9)) -> minus(U9,V9) 36: quot(mark(W9),P9) -> quot(W9,P9) 37: quot(X10,mark(Y10)) -> quot(X10,Y10) 38: quot(active(U10),V10) -> quot(U10,V10) 39: quot(W10,active(P10)) -> quot(W10,P10) 40: zWquot(mark(X11),Y11) -> zWquot(X11,Y11) 41: zWquot(U11,mark(V11)) -> zWquot(U11,V11) 42: zWquot(active(W11),P11) -> zWquot(W11,P11) 43: zWquot(X12,active(Y12)) -> zWquot(X12,Y12) 44: _(X1,X2) -> X1 45: _(X1,X2) -> X2 Number of strict rules: 45 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #active(sel(0(),cons(Y,U))) -> #mark(Y) #2: #zWquot(X12,active(Y12)) -> #zWquot(X12,Y12) #3: #sel(U7,mark(V7)) -> #sel(U7,V7) #4: #minus(U9,active(V9)) -> #minus(U9,V9) #5: #zWquot(active(W11),P11) -> #zWquot(W11,P11) #6: #zWquot(U11,mark(V11)) -> #zWquot(U11,V11) #7: #quot(X10,mark(Y10)) -> #quot(X10,Y10) #8: #quot(active(U10),V10) -> #quot(U10,V10) #9: #active(quot(0(),s(V1))) -> #mark(0()) #10: #zWquot(mark(X11),Y11) -> #zWquot(X11,Y11) #11: #mark(s(V3)) -> #active(s(mark(V3))) #12: #mark(s(V3)) -> #s(mark(V3)) #13: #mark(s(V3)) -> #mark(V3) #14: #active(zWquot(nil(),Y2)) -> #mark(nil()) #15: #mark(from(X3)) -> #active(from(mark(X3))) #16: #mark(from(X3)) -> #from(mark(X3)) #17: #mark(from(X3)) -> #mark(X3) #18: #cons(active(X6),Y6) -> #cons(X6,Y6) #19: #cons(W5,mark(P5)) -> #cons(W5,P5) #20: #mark(cons(Y3,U3)) -> #active(cons(mark(Y3),U3)) #21: #mark(cons(Y3,U3)) -> #cons(mark(Y3),U3) #22: #mark(cons(Y3,U3)) -> #mark(Y3) #23: #sel(X8,active(Y8)) -> #sel(X8,Y8) #24: #mark(sel(W3,P3)) -> #active(sel(mark(W3),mark(P3))) #25: #mark(sel(W3,P3)) -> #sel(mark(W3),mark(P3)) #26: #mark(sel(W3,P3)) -> #mark(W3) #27: #mark(sel(W3,P3)) -> #mark(P3) #28: #sel(active(W7),P7) -> #sel(W7,P7) #29: #cons(U6,active(V6)) -> #cons(U6,V6) #30: #from(mark(X5)) -> #from(X5) #31: #active(quot(s(W1),s(P1))) -> #mark(s(quot(minus(W1,P1),s(P1)))) #32: #active(quot(s(W1),s(P1))) -> #s(quot(minus(W1,P1),s(P1))) #33: #active(quot(s(W1),s(P1))) -> #quot(minus(W1,P1),s(P1)) #34: #active(quot(s(W1),s(P1))) -> #minus(W1,P1) #35: #quot(W10,active(P10)) -> #quot(W10,P10) #36: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #mark(cons(quot(U2,W2),zWquot(V2,P2))) #37: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #cons(quot(U2,W2),zWquot(V2,P2)) #38: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #quot(U2,W2) #39: #active(zWquot(cons(U2,V2),cons(W2,P2))) -> #zWquot(V2,P2) #40: #minus(W8,mark(P8)) -> #minus(W8,P8) #41: #active(minus(s(Y1),s(U1))) -> #mark(minus(Y1,U1)) #42: #active(minus(s(Y1),s(U1))) -> #minus(Y1,U1) #43: #sel(mark(X7),Y7) -> #sel(X7,Y7) #44: #cons(mark(U5),V5) -> #cons(U5,V5) #45: #minus(active(X9),Y9) -> #minus(X9,Y9) #46: #s(active(P6)) -> #s(P6) #47: #mark(quot(U4,V4)) -> #active(quot(mark(U4),mark(V4))) #48: #mark(quot(U4,V4)) -> #quot(mark(U4),mark(V4)) #49: #mark(quot(U4,V4)) -> #mark(U4) #50: #mark(quot(U4,V4)) -> #mark(V4) #51: #minus(mark(U8),V8) -> #minus(U8,V8) #52: #mark(nil()) -> #active(nil()) #53: #s(mark(W6)) -> #s(W6) #54: #quot(mark(W9),P9) -> #quot(W9,P9) #55: #from(active(Y5)) -> #from(Y5) #56: #mark(minus(X4,Y4)) -> #active(minus(mark(X4),mark(Y4))) #57: #mark(minus(X4,Y4)) -> #minus(mark(X4),mark(Y4)) #58: #mark(minus(X4,Y4)) -> #mark(X4) #59: #mark(minus(X4,Y4)) -> #mark(Y4) #60: #active(sel(s(V),cons(W,P))) -> #mark(sel(V,P)) #61: #active(sel(s(V),cons(W,P))) -> #sel(V,P) #62: #active(from(X)) -> #mark(cons(X,from(s(X)))) #63: #active(from(X)) -> #cons(X,from(s(X))) #64: #active(from(X)) -> #from(s(X)) #65: #active(from(X)) -> #s(X) #66: #active(zWquot(X2,nil())) -> #mark(nil()) #67: #mark(0()) -> #active(0()) #68: #active(minus(X1,0())) -> #mark(0()) #69: #mark(zWquot(W4,P4)) -> #active(zWquot(mark(W4),mark(P4))) #70: #mark(zWquot(W4,P4)) -> #zWquot(mark(W4),mark(P4)) #71: #mark(zWquot(W4,P4)) -> #mark(W4) #72: #mark(zWquot(W4,P4)) -> #mark(P4) Number of SCCs: 8, DPs: 46 SCC { #30 #55 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: x1 active w: x1 + 7720 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #30 #55 Number of SCCs: 7, DPs: 44 SCC { #46 #53 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: x1 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 1797 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #46 #53 Number of SCCs: 6, DPs: 42 SCC { #4 #40 #45 #51 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: x1 #_ w: 0 #from w: 0 active w: x1 + 2283 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #45 #51 Number of SCCs: 6, DPs: 40 SCC { #4 #40 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: x2 #_ w: 0 #from w: 0 active w: x1 + 8099 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #4 #40 Number of SCCs: 5, DPs: 38 SCC { #7 #8 #35 #54 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 282 cons w: 0 #active w: 0 #quot w: x1 USABLE RULES: { } Removed DPs: #8 #54 Number of SCCs: 5, DPs: 36 SCC { #7 #35 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 6284 cons w: 0 #active w: 0 #quot w: x2 USABLE RULES: { } Removed DPs: #7 #35 Number of SCCs: 4, DPs: 34 SCC { #18 #19 #29 #44 } POLO(Sum)... succeeded. #cons w: x1 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 4680 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #18 #44 Number of SCCs: 4, DPs: 32 SCC { #19 #29 } POLO(Sum)... succeeded. #cons w: x2 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 5905 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #19 #29 Number of SCCs: 3, DPs: 30 SCC { #3 #23 #28 #43 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: x2 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 1324 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #3 #23 Number of SCCs: 3, DPs: 28 SCC { #28 #43 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: 0 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: x1 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 2276 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #28 #43 Number of SCCs: 2, DPs: 26 SCC { #2 #5 #6 #10 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: x1 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 841 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #5 #10 Number of SCCs: 2, DPs: 24 SCC { #2 #6 } POLO(Sum)... succeeded. #cons w: 0 s w: 0 #zWquot w: x2 minus w: 0 zWquot w: 0 _ w: 0 #mark w: 0 0 w: 0 quot w: 0 #sel w: 0 from w: 0 sel w: 0 #s w: 0 nil w: 0 mark w: x1 + 1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 + 3610 cons w: 0 #active w: 0 #quot w: 0 USABLE RULES: { } Removed DPs: #2 #6 Number of SCCs: 1, DPs: 22 SCC { #1 #13 #15 #17 #22 #24 #26 #27 #31 #36 #41 #47 #49 #50 #56 #58..60 #62 #69 #71 #72 } POLO(Sum)... POLO(max)... succeeded. #cons w: 0 s w: x1 #zWquot w: 0 minus w: max(x1, x2 + 1) zWquot w: max(x1 + 5, x2 + 7) _ w: 0 #mark w: x1 + 1 0 w: 9535 quot w: max(x1 + 1, x2 + 3) #sel w: 0 from w: x1 + 8223 sel w: max(x1 + 870, x2 + 868) #s w: 0 nil w: 8 mark w: x1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 cons w: max(x1 + 1, x2) #active w: x1 + 1 #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #1 #17 #22 #26 #27 #49 #50 #59 #71 #72 Number of SCCs: 2, DPs: 8 SCC { #24 #60 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded. #cons s: [1] p: 0 w: max(x1) s s: [1] p: 1 w: x1 #zWquot s: [1] p: 0 w: x1 + 1 minus s: [] p: 1 w: 0 zWquot s: [1] p: 4 w: x1 + x2 + 19384 _ s: [1] p: 0 w: x1 #mark s: [1] p: 0 w: x1 0 s: [] p: 1 w: 0 quot s: [1] p: 3 w: max(x1 + 625, x2 + 9495) #sel s: [1,2] p: 0 w: x1 + x2 from s: [] p: 4 w: x1 + 3649 sel s: [1,2] p: 2 w: x1 + x2 + 4260 #s s: [] p: 0 w: 0 nil s: [] p: 5 w: 1392 mark s: 1 #minus s: [] p: 0 w: max(x1) #_ s: [2] p: 0 w: x2 + 1 #from s: [] p: 0 w: 1 active s: 1 cons s: [1] p: 3 w: max(x1 + 625, x2) #active s: [1] p: 0 w: x1 #quot s: [] p: 0 w: 0 USABLE RULES: { 1..43 } Removed DPs: #60 Number of SCCs: 1, DPs: 6 SCC { #13 #31 #41 #47 #56 #58 } POLO(Sum)... POLO(max)... succeeded. #cons w: 0 s w: x1 #zWquot w: 0 minus w: max(x1 + 9620, x2 + 15954) zWquot w: max(x2 + 9559) _ w: 0 #mark w: x1 + 1 0 w: 0 quot w: max(x2 + 6933) #sel w: 0 from w: x1 sel w: max(x2) #s w: 0 nil w: 2748 mark w: x1 #minus w: 0 #_ w: 0 #from w: 0 active w: x1 cons w: max(x1, x2) #active w: x1 + 1 #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #58 Number of SCCs: 2, DPs: 5 SCC { #41 #56 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded. #cons w: 0 s w: max(x1 + 1948, 0) #zWquot w: 0 minus w: max(x1, 0) zWquot w: max(x1 + 3600, 0) _ w: 0 #mark w: max(x1 + 1, 0) 0 w: 0 quot w: max(x1 + 3600, 0) #sel w: max(x1 - 1, 0) from w: max(x1 + 8760, 0) sel w: max(x1 + x2 + 4722, 0) #s w: max(x1 - 1, 0) nil w: 1 mark w: max(x1, 0) #minus w: 0 #_ w: max(x2 - 1, 0) #from w: 0 active w: max(x1, 0) cons w: max(x1 - 1949, x2 - 1948, 0) #active w: max(x1 - 1, 0) #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #41 #56 Number of SCCs: 1, DPs: 3 SCC { #13 #31 #47 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded. #cons w: 0 s w: max(x1 + 798, 0) #zWquot w: 0 minus w: max(x1, 0) zWquot w: max(x1 + 7473, 0) _ w: 0 #mark w: max(x1 + 1, 0) 0 w: 0 quot w: max(x1 + 6966, 0) #sel w: max(x1 - 1, 0) from w: max(x1 + 7919, 0) sel w: max(x1 + x2 + 4259, 0) #s w: max(x1 - 1, 0) nil w: 1 mark w: max(x1, 0) #minus w: 0 #_ w: max(x2 - 1, 0) #from w: 0 active w: max(x1, 0) cons w: max(x1 - 1981, x2 - 798, 0) #active w: max(x1 + 1, 0) #quot w: 0 USABLE RULES: { 1..43 } Removed DPs: #13 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((A -> A),A) -> A nil : A cons : (A,A) -> A app : ((A -> A),A) -> A foldr : (((A,A) -> A),A,A) -> A ******** Computation rules ******** (44) map(%X.G12[%X],nil) => nil (45) map(%Y.H12[%Y],cons(W12,P12)) => cons(H12[W12],map(%Z.H12[%Z],P12)) (46) %U.F13[%U]@Y13 => F13[Y13] (47) foldr(%W.%V.G13[%W,%V],V13,nil) => V13 (48) foldr(%G.%F.I13[%G,%F],P13,cons(X14,Y14)) => I13[X14,foldr(%I.%H.I13[%I,%H],P13,Y14)] ******** General Schema criterion ******** Found constructors: 0, nil Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: mark, active Checking (1) active(from(X)) => mark(cons(X,from(s(X)))) (fun active=mark) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) active(from(X)) => mark(cons(X,from(s(X)))) (fun active=mark) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) active(from(X)) => mark(cons(X,from(s(X)))) (fun active=mark) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (44) map(%X.G12[%X],nil) => nil (fun map>nil) >>True Checking (45) map(%Y.H12[%Y],cons(W12,P12)) => cons(H12[W12],map(%Z.H12[%Z],P12)) (fun map>cons) (meta H12)[is acc in %Y.H12[%Y],cons(W12,P12)] [is acc in H12[%Y]] (meta W12)[is acc in %Y.H12[%Y],cons(W12,P12)] [is positive in cons(W12,P12)] [is acc in W12] (fun map=map) subterm comparison of args w. LR LR (meta H12)[is acc in %Y.H12[%Y],cons(W12,P12)] [is acc in H12[%Y]] (meta P12)[is acc in %Y.H12[%Y],cons(W12,P12)] [is positive in cons(W12,P12)] [is acc in P12] >>True Checking (46) %U.F13[%U]@Y13 => F13[Y13] (meta F13)[is acc in %U.F13[%U],Y13] [is acc in F13[%U]] (meta Y13)[is acc in %U.F13[%U],Y13] [is acc in Y13] >>True Checking (47) foldr(%W.%V.G13[%W,%V],V13,nil) => V13 (meta V13)[is acc in %W.%V.G13[%W,%V],V13,nil] [is acc in V13] >>True Checking (48) foldr(%G.%F.I13[%G,%F],P13,cons(X14,Y14)) => I13[X14,foldr(%I.%H.I13[%I,%H],P13,Y14)] (meta I13)[is acc in %G.%F.I13[%G,%F],P13,cons(X14,Y14)] [is acc in I13[%G,%F]] (meta X14)[is acc in %G.%F.I13[%G,%F],P13,cons(X14,Y14)] [is positive in cons(X14,Y14)] [is acc in X14] (fun foldr=foldr) subterm comparison of args w. LR LR (meta I13)[is acc in %G.%F.I13[%G,%F],P13,cons(X14,Y14)] [is acc in I13[%G,%F]] (meta P13)[is acc in %G.%F.I13[%G,%F],P13,cons(X14,Y14)] [is acc in P13] (meta Y14)[is acc in %G.%F.I13[%G,%F],P13,cons(X14,Y14)] [is positive in cons(X14,Y14)] [is acc in Y14] >>True #SN! ******** Signature ******** 0 : A active : A -> A app : ((A -> A),A) -> A cons : (A,A) -> A foldr : (((A,A) -> A),A,A) -> A from : A -> A map : ((A -> A),A) -> A mark : A -> A minus : (A,A) -> A nil : A quot : (A,A) -> A s : A -> A sel : (A,A) -> A zWquot : (A,A) -> A ******** Computation Rules ******** (1) active(from(X)) => mark(cons(X,from(s(X)))) (2) active(sel(0,cons(Y,U))) => mark(Y) (3) active(sel(s(V),cons(W,P))) => mark(sel(V,P)) (4) active(minus(X1,0)) => mark(0) (5) active(minus(s(Y1),s(U1))) => mark(minus(Y1,U1)) (6) active(quot(0,s(V1))) => mark(0) (7) active(quot(s(W1),s(P1))) => mark(s(quot(minus(W1,P1),s(P1)))) (8) active(zWquot(X2,nil)) => mark(nil) (9) active(zWquot(nil,Y2)) => mark(nil) (10) active(zWquot(cons(U2,V2),cons(W2,P2))) => mark(cons(quot(U2,W2),zWquot(V2,P2))) (11) mark(from(X3)) => active(from(mark(X3))) (12) mark(cons(Y3,U3)) => active(cons(mark(Y3),U3)) (13) mark(s(V3)) => active(s(mark(V3))) (14) mark(sel(W3,P3)) => active(sel(mark(W3),mark(P3))) (15) mark(0) => active(0) (16) mark(minus(X4,Y4)) => active(minus(mark(X4),mark(Y4))) (17) mark(quot(U4,V4)) => active(quot(mark(U4),mark(V4))) (18) mark(zWquot(W4,P4)) => active(zWquot(mark(W4),mark(P4))) (19) mark(nil) => active(nil) (20) from(mark(X5)) => from(X5) (21) from(active(Y5)) => from(Y5) (22) cons(mark(U5),V5) => cons(U5,V5) (23) cons(W5,mark(P5)) => cons(W5,P5) (24) cons(active(X6),Y6) => cons(X6,Y6) (25) cons(U6,active(V6)) => cons(U6,V6) (26) s(mark(W6)) => s(W6) (27) s(active(P6)) => s(P6) (28) sel(mark(X7),Y7) => sel(X7,Y7) (29) sel(U7,mark(V7)) => sel(U7,V7) (30) sel(active(W7),P7) => sel(W7,P7) (31) sel(X8,active(Y8)) => sel(X8,Y8) (32) minus(mark(U8),V8) => minus(U8,V8) (33) minus(W8,mark(P8)) => minus(W8,P8) (34) minus(active(X9),Y9) => minus(X9,Y9) (35) minus(U9,active(V9)) => minus(U9,V9) (36) quot(mark(W9),P9) => quot(W9,P9) (37) quot(X10,mark(Y10)) => quot(X10,Y10) (38) quot(active(U10),V10) => quot(U10,V10) (39) quot(W10,active(P10)) => quot(W10,P10) (40) zWquot(mark(X11),Y11) => zWquot(X11,Y11) (41) zWquot(U11,mark(V11)) => zWquot(U11,V11) (42) zWquot(active(W11),P11) => zWquot(W11,P11) (43) zWquot(X12,active(Y12)) => zWquot(X12,Y12) (44) map(%X.G12[%X],nil) => nil (45) map(%Y.H12[%Y],cons(W12,P12)) => cons(H12[W12],map(%Z.H12[%Z],P12)) (46) %U.F13[%U]@Y13 => F13[Y13] (47) foldr(%W.%V.G13[%W,%V],V13,nil) => V13 (48) foldr(%G.%F.I13[%G,%F],P13,cons(X14,Y14)) => I13[X14,foldr(%I.%H.I13[%I,%H],P13,Y14)] YES