/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Input TRS: 1: a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N))) 2: a__sqr(0()) -> 0() 3: a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)),a__dbl(mark(X)))) 4: a__dbl(0()) -> 0() 5: a__dbl(s(X)) -> s(s(a__dbl(mark(X)))) 6: a__add(0(),X) -> mark(X) 7: a__add(s(X),Y) -> s(a__add(mark(X),mark(Y))) 8: a__first(0(),X) -> nil() 9: a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) 10: a__half(0()) -> 0() 11: a__half(s(0())) -> 0() 12: a__half(s(s(X))) -> s(a__half(mark(X))) 13: a__half(dbl(X)) -> mark(X) 14: mark(terms(X)) -> a__terms(mark(X)) 15: mark(sqr(X)) -> a__sqr(mark(X)) 16: mark(add(X1,X2)) -> a__add(mark(X1),mark(X2)) 17: mark(dbl(X)) -> a__dbl(mark(X)) 18: mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) 19: mark(half(X)) -> a__half(mark(X)) 20: mark(cons(X1,X2)) -> cons(mark(X1),X2) 21: mark(recip(X)) -> recip(mark(X)) 22: mark(s(X)) -> s(mark(X)) 23: mark(0()) -> 0() 24: mark(nil()) -> nil() 25: a__terms(X) -> terms(X) 26: a__sqr(X) -> sqr(X) 27: a__add(X1,X2) -> add(X1,X2) 28: a__dbl(X) -> dbl(X) 29: a__first(X1,X2) -> first(X1,X2) 30: a__half(X) -> half(X) Number of strict rules: 30 Direct poly ... failed. Freezing ... failed. Dependency Pairs: #1: #a__add(0(),X) -> #mark(X) #2: #a__half(dbl(X)) -> #mark(X) #3: #a__first(s(X),cons(Y,Z)) -> #mark(Y) #4: #a__half(s(s(X))) -> #a__half(mark(X)) #5: #a__half(s(s(X))) -> #mark(X) #6: #mark(terms(X)) -> #a__terms(mark(X)) #7: #mark(terms(X)) -> #mark(X) #8: #mark(cons(X1,X2)) -> #mark(X1) #9: #a__add(s(X),Y) -> #a__add(mark(X),mark(Y)) #10: #a__add(s(X),Y) -> #mark(X) #11: #a__add(s(X),Y) -> #mark(Y) #12: #a__dbl(s(X)) -> #a__dbl(mark(X)) #13: #a__dbl(s(X)) -> #mark(X) #14: #mark(s(X)) -> #mark(X) #15: #mark(dbl(X)) -> #a__dbl(mark(X)) #16: #mark(dbl(X)) -> #mark(X) #17: #mark(half(X)) -> #a__half(mark(X)) #18: #mark(half(X)) -> #mark(X) #19: #mark(recip(X)) -> #mark(X) #20: #mark(add(X1,X2)) -> #a__add(mark(X1),mark(X2)) #21: #mark(add(X1,X2)) -> #mark(X1) #22: #mark(add(X1,X2)) -> #mark(X2) #23: #a__sqr(s(X)) -> #a__add(a__sqr(mark(X)),a__dbl(mark(X))) #24: #a__sqr(s(X)) -> #a__sqr(mark(X)) #25: #a__sqr(s(X)) -> #mark(X) #26: #a__sqr(s(X)) -> #a__dbl(mark(X)) #27: #a__sqr(s(X)) -> #mark(X) #28: #a__terms(N) -> #a__sqr(mark(N)) #29: #a__terms(N) -> #mark(N) #30: #mark(sqr(X)) -> #a__sqr(mark(X)) #31: #mark(sqr(X)) -> #mark(X) #32: #mark(first(X1,X2)) -> #a__first(mark(X1),mark(X2)) #33: #mark(first(X1,X2)) -> #mark(X1) #34: #mark(first(X1,X2)) -> #mark(X2) Number of SCCs: 1, DPs: 34 SCC { #1..34 } Sum... Max... succeeded. s(x1) w: (x1) #a__first(x1,x2) w: (max{2 + x2, 0}) recip(x1) w: (12213 + x1) dbl(x1) w: (20586 + x1) a__half(x1) w: (31599 + x1) #a__add(x1,x2) w: (max{1 + x2, 1 + x1}) a__add(x1,x2) w: (max{x2, x1}) a__dbl(x1) w: (20586 + x1) #a__half(x1) w: (31599 + x1) a__sqr(x1) w: (20587 + x1) half(x1) w: (31599 + x1) #a__terms(x1) w: (20589 + x1) #mark(x1) w: (1 + x1) 0() w: (17067) nil() w: (17068) #a__dbl(x1) w: (20586 + x1) mark(x1) w: (x1) first(x1,x2) w: (max{31113 + x2, x1}) a__first(x1,x2) w: (max{31113 + x2, x1}) cons(x1,x2) w: (max{x2, 31114 + x1}) add(x1,x2) w: (max{x2, x1}) sqr(x1) w: (20587 + x1) a__terms(x1) w: (63914 + x1) #a__sqr(x1) w: (20588 + x1) terms(x1) w: (63914 + x1) USABLE RULES: { 1..30 } Removed DPs: #2 #3 #5..8 #13 #15..19 #25..29 #31 #32 #34 Number of SCCs: 3, DPs: 14 SCC { #12 } Sum... Max... QLPOpS... succeeded. s(x1) 1[x1] #a__first(x1,x2) 0[x2,x1] recip(x1) 1[] dbl(x1) 3[x1] a__half(x1) 1[x1] #a__add(x1,x2) 0[x1,x2] a__add(x1,x2) 2[x1,x2] a__dbl(x1) 3[x1] #a__half(x1) 0[] a__sqr(x1) 3[x1] half(x1) 1[x1] #a__terms(x1) 0[] #mark(x1) 0[] 0() 1 nil() 1 #a__dbl(x1) 0[x1] mark(x1) x1 first(x1,x2) x1 a__first(x1,x2) x1 cons(x1,x2) x2 add(x1,x2) 2[x1,x2] sqr(x1) 3[x1] a__terms(x1) 1[] #a__sqr(x1) 0[] terms(x1) 1[] USABLE RULES: { 1..30 } Removed DPs: #12 Number of SCCs: 2, DPs: 13 SCC { #4 } Sum... Max... QLPOpS... succeeded. s(x1) 1[x1] #a__first(x1,x2) 0[x2,x1] recip(x1) 1[] dbl(x1) 3[x1] a__half(x1) 1[x1] #a__add(x1,x2) 0[x1,x2] a__add(x1,x2) 2[x1,x2] a__dbl(x1) 3[x1] #a__half(x1) 0[x1] a__sqr(x1) 3[x1] half(x1) 1[x1] #a__terms(x1) 0[] #mark(x1) 0[] 0() 1 nil() 1 #a__dbl(x1) 0[x1] mark(x1) x1 first(x1,x2) x1 a__first(x1,x2) x1 cons(x1,x2) x2 add(x1,x2) 2[x1,x2] sqr(x1) 3[x1] a__terms(x1) 1[] #a__sqr(x1) 0[] terms(x1) 1[] USABLE RULES: { 1..30 } Removed DPs: #4 Number of SCCs: 1, DPs: 12 SCC { #1 #9..11 #14 #20..24 #30 #33 } Sum... Max... succeeded. s(x1) w: (x1) #a__first(x1,x2) w: (0) recip(x1) w: (18748) dbl(x1) w: (x1) a__half(x1) w: (19621 + x1) #a__add(x1,x2) w: (max{25192 + x2, 25192 + x1}) a__add(x1,x2) w: (max{x2, x1}) a__dbl(x1) w: (x1) #a__half(x1) w: (31599) a__sqr(x1) w: (x1) half(x1) w: (19621 + x1) #a__terms(x1) w: (20589) #mark(x1) w: (25192 + x1) 0() w: (1) nil() w: (26053) #a__dbl(x1) w: (20586) mark(x1) w: (x1) first(x1,x2) w: (max{1 + x2, 26052 + x1}) a__first(x1,x2) w: (max{1 + x2, 26052 + x1}) cons(x1,x2) w: (0) add(x1,x2) w: (max{x2, x1}) sqr(x1) w: (x1) a__terms(x1) w: (120 + x1) #a__sqr(x1) w: (25192 + x1) terms(x1) w: (120 + x1) USABLE RULES: { 1..30 } Removed DPs: #33 Number of SCCs: 1, DPs: 11 SCC { #1 #9..11 #14 #20..24 #30 } Sum... Max... succeeded. s(x1) w: (x1) #a__first(x1,x2) w: (0) recip(x1) w: (3418) dbl(x1) w: (8573 + x1) a__half(x1) w: (28471 + x1) #a__add(x1,x2) w: (max{29645 + x2, 29644 + x1}) a__add(x1,x2) w: (max{2 + x2, x1}) a__dbl(x1) w: (8573 + x1) #a__half(x1) w: (31599) a__sqr(x1) w: (8575 + x1) half(x1) w: (28471 + x1) #a__terms(x1) w: (20589) #mark(x1) w: (29644 + x1) 0() w: (1) nil() w: (28257) #a__dbl(x1) w: (20586) mark(x1) w: (x1) first(x1,x2) w: (max{1 + x2, 28256 + x1}) a__first(x1,x2) w: (max{1 + x2, 28256 + x1}) cons(x1,x2) w: (max{0, 28257 + x1}) add(x1,x2) w: (max{2 + x2, x1}) sqr(x1) w: (8575 + x1) a__terms(x1) w: (31675) #a__sqr(x1) w: (38219 + x1) terms(x1) w: (31675) USABLE RULES: { 1..30 } Removed DPs: #1 #11 #22 Number of SCCs: 1, DPs: 8 SCC { #9 #10 #14 #20 #21 #23 #24 #30 } Sum... Max... QLPOpS... succeeded. s(x1) 2[x1] #a__first(x1,x2) 0[x2,x1] recip(x1) 2[] dbl(x1) 3[x1] a__half(x1) 2[x1] #a__add(x1,x2) 0[x1] a__add(x1,x2) 3[x1,x2] a__dbl(x1) 3[x1] #a__half(x1) 0[x1] a__sqr(x1) 4[x1] half(x1) 2[x1] #a__terms(x1) 0[] #mark(x1) x1 0() 2 nil() 2 #a__dbl(x1) 0[x1] mark(x1) x1 first(x1,x2) x1 a__first(x1,x2) x1 cons(x1,x2) x2 add(x1,x2) 3[x1,x2] sqr(x1) 4[x1] a__terms(x1) 2[] #a__sqr(x1) 4[x1] terms(x1) 2[] USABLE RULES: { 1..30 } Removed DPs: #9 #10 #14 #20 #21 #23 #24 Number of SCCs: 0, DPs: 0