/export/starexec/sandbox2/solver/bin/starexec_run_Default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE Input TRS: 1: U101(tt(),N,XS) -> fst(splitAt(activate(N),activate(XS))) 2: U11(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS))) 3: U21(tt(),X) -> activate(X) 4: U31(tt(),N) -> activate(N) 5: U41(tt(),N) -> cons(activate(N),n__natsFrom(s(activate(N)))) 6: U51(tt(),N,XS) -> head(afterNth(activate(N),activate(XS))) 7: U61(tt(),Y) -> activate(Y) 8: U71(tt(),XS) -> pair(nil(),activate(XS)) 9: U81(tt(),N,X,XS) -> U82(splitAt(activate(N),activate(XS)),activate(X)) 10: U82(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS) 11: U91(tt(),XS) -> activate(XS) 12: afterNth(N,XS) -> U11(and(isNatural(N),n__isLNat(XS)),N,XS) 13: and(tt(),X) -> activate(X) 14: fst(pair(X,Y)) -> U21(and(isLNat(X),n__isLNat(Y)),X) 15: head(cons(N,XS)) -> U31(and(isNatural(N),n__isLNat(activate(XS))),N) 16: isLNat(n__nil()) -> tt() 17: isLNat(n__afterNth(V1,V2)) -> and(isNatural(activate(V1)),n__isLNat(activate(V2))) 18: isLNat(n__cons(V1,V2)) -> and(isNatural(activate(V1)),n__isLNat(activate(V2))) 19: isLNat(n__fst(V1)) -> isPLNat(activate(V1)) 20: isLNat(n__natsFrom(V1)) -> isNatural(activate(V1)) 21: isLNat(n__snd(V1)) -> isPLNat(activate(V1)) 22: isLNat(n__tail(V1)) -> isLNat(activate(V1)) 23: isLNat(n__take(V1,V2)) -> and(isNatural(activate(V1)),n__isLNat(activate(V2))) 24: isNatural(n__0()) -> tt() 25: isNatural(n__head(V1)) -> isLNat(activate(V1)) 26: isNatural(n__s(V1)) -> isNatural(activate(V1)) 27: isNatural(n__sel(V1,V2)) -> and(isNatural(activate(V1)),n__isLNat(activate(V2))) 28: isPLNat(n__pair(V1,V2)) -> and(isLNat(activate(V1)),n__isLNat(activate(V2))) 29: isPLNat(n__splitAt(V1,V2)) -> and(isNatural(activate(V1)),n__isLNat(activate(V2))) 30: natsFrom(N) -> U41(isNatural(N),N) 31: sel(N,XS) -> U51(and(isNatural(N),n__isLNat(XS)),N,XS) 32: snd(pair(X,Y)) -> U61(and(isLNat(X),n__isLNat(Y)),Y) 33: splitAt(0(),XS) -> U71(isLNat(XS),XS) 34: splitAt(s(N),cons(X,XS)) -> U81(and(isNatural(N),n__and(isNatural(X),n__isLNat(activate(XS)))),N,X,activate(XS)) 35: tail(cons(N,XS)) -> U91(and(isNatural(N),n__isLNat(activate(XS))),activate(XS)) 36: take(N,XS) -> U101(and(isNatural(N),n__isLNat(XS)),N,XS) 37: natsFrom(X) -> n__natsFrom(X) 38: isLNat(X) -> n__isLNat(X) 39: nil() -> n__nil() 40: afterNth(X1,X2) -> n__afterNth(X1,X2) 41: cons(X1,X2) -> n__cons(X1,X2) 42: fst(X) -> n__fst(X) 43: snd(X) -> n__snd(X) 44: tail(X) -> n__tail(X) 45: take(X1,X2) -> n__take(X1,X2) 46: 0() -> n__0() 47: head(X) -> n__head(X) 48: s(X) -> n__s(X) 49: sel(X1,X2) -> n__sel(X1,X2) 50: pair(X1,X2) -> n__pair(X1,X2) 51: splitAt(X1,X2) -> n__splitAt(X1,X2) 52: and(X1,X2) -> n__and(X1,X2) 53: activate(n__natsFrom(X)) -> natsFrom(X) 54: activate(n__isLNat(X)) -> isLNat(X) 55: activate(n__nil()) -> nil() 56: activate(n__afterNth(X1,X2)) -> afterNth(X1,X2) 57: activate(n__cons(X1,X2)) -> cons(X1,X2) 58: activate(n__fst(X)) -> fst(X) 59: activate(n__snd(X)) -> snd(X) 60: activate(n__tail(X)) -> tail(X) 61: activate(n__take(X1,X2)) -> take(X1,X2) 62: activate(n__0()) -> 0() 63: activate(n__head(X)) -> head(X) 64: activate(n__s(X)) -> s(X) 65: activate(n__sel(X1,X2)) -> sel(X1,X2) 66: activate(n__pair(X1,X2)) -> pair(X1,X2) 67: activate(n__splitAt(X1,X2)) -> splitAt(X1,X2) 68: activate(n__and(X1,X2)) -> and(X1,X2) 69: activate(X) -> X Number of strict rules: 69 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #U11(tt(),N,XS) -> #snd(splitAt(activate(N),activate(XS))) #2: #U11(tt(),N,XS) -> #splitAt(activate(N),activate(XS)) #3: #U11(tt(),N,XS) -> #activate(N) #4: #U11(tt(),N,XS) -> #activate(XS) #5: #isPLNat(n__splitAt(V1,V2)) -> #and(isNatural(activate(V1)),n__isLNat(activate(V2))) #6: #isPLNat(n__splitAt(V1,V2)) -> #isNatural(activate(V1)) #7: #isPLNat(n__splitAt(V1,V2)) -> #activate(V1) #8: #isPLNat(n__splitAt(V1,V2)) -> #activate(V2) #9: #tail(cons(N,XS)) -> #U91(and(isNatural(N),n__isLNat(activate(XS))),activate(XS)) #10: #tail(cons(N,XS)) -> #and(isNatural(N),n__isLNat(activate(XS))) #11: #tail(cons(N,XS)) -> #isNatural(N) #12: #tail(cons(N,XS)) -> #activate(XS) #13: #tail(cons(N,XS)) -> #activate(XS) #14: #activate(n__pair(X1,X2)) -> #pair(X1,X2) #15: #activate(n__natsFrom(X)) -> #natsFrom(X) #16: #activate(n__fst(X)) -> #fst(X) #17: #activate(n__take(X1,X2)) -> #take(X1,X2) #18: #U51(tt(),N,XS) -> #head(afterNth(activate(N),activate(XS))) #19: #U51(tt(),N,XS) -> #afterNth(activate(N),activate(XS)) #20: #U51(tt(),N,XS) -> #activate(N) #21: #U51(tt(),N,XS) -> #activate(XS) #22: #activate(n__snd(X)) -> #snd(X) #23: #activate(n__nil()) -> #nil() #24: #activate(n__splitAt(X1,X2)) -> #splitAt(X1,X2) #25: #and(tt(),X) -> #activate(X) #26: #U81(tt(),N,X,XS) -> #U82(splitAt(activate(N),activate(XS)),activate(X)) #27: #U81(tt(),N,X,XS) -> #splitAt(activate(N),activate(XS)) #28: #U81(tt(),N,X,XS) -> #activate(N) #29: #U81(tt(),N,X,XS) -> #activate(XS) #30: #U81(tt(),N,X,XS) -> #activate(X) #31: #U91(tt(),XS) -> #activate(XS) #32: #activate(n__cons(X1,X2)) -> #cons(X1,X2) #33: #isLNat(n__take(V1,V2)) -> #and(isNatural(activate(V1)),n__isLNat(activate(V2))) #34: #isLNat(n__take(V1,V2)) -> #isNatural(activate(V1)) #35: #isLNat(n__take(V1,V2)) -> #activate(V1) #36: #isLNat(n__take(V1,V2)) -> #activate(V2) #37: #afterNth(N,XS) -> #U11(and(isNatural(N),n__isLNat(XS)),N,XS) #38: #afterNth(N,XS) -> #and(isNatural(N),n__isLNat(XS)) #39: #afterNth(N,XS) -> #isNatural(N) #40: #sel(N,XS) -> #U51(and(isNatural(N),n__isLNat(XS)),N,XS) #41: #sel(N,XS) -> #and(isNatural(N),n__isLNat(XS)) #42: #sel(N,XS) -> #isNatural(N) #43: #activate(n__afterNth(X1,X2)) -> #afterNth(X1,X2) #44: #fst(pair(X,Y)) -> #U21(and(isLNat(X),n__isLNat(Y)),X) #45: #fst(pair(X,Y)) -> #and(isLNat(X),n__isLNat(Y)) #46: #fst(pair(X,Y)) -> #isLNat(X) #47: #activate(n__0()) -> #0() #48: #natsFrom(N) -> #U41(isNatural(N),N) #49: #natsFrom(N) -> #isNatural(N) #50: #isNatural(n__head(V1)) -> #isLNat(activate(V1)) #51: #isNatural(n__head(V1)) -> #activate(V1) #52: #isLNat(n__natsFrom(V1)) -> #isNatural(activate(V1)) #53: #isLNat(n__natsFrom(V1)) -> #activate(V1) #54: #U61(tt(),Y) -> #activate(Y) #55: #U82(pair(YS,ZS),X) -> #pair(cons(activate(X),YS),ZS) #56: #U82(pair(YS,ZS),X) -> #cons(activate(X),YS) #57: #U82(pair(YS,ZS),X) -> #activate(X) #58: #activate(n__s(X)) -> #s(X) #59: #splitAt(0(),XS) -> #U71(isLNat(XS),XS) #60: #splitAt(0(),XS) -> #isLNat(XS) #61: #U41(tt(),N) -> #cons(activate(N),n__natsFrom(s(activate(N)))) #62: #U41(tt(),N) -> #activate(N) #63: #U41(tt(),N) -> #s(activate(N)) #64: #U41(tt(),N) -> #activate(N) #65: #activate(n__sel(X1,X2)) -> #sel(X1,X2) #66: #isPLNat(n__pair(V1,V2)) -> #and(isLNat(activate(V1)),n__isLNat(activate(V2))) #67: #isPLNat(n__pair(V1,V2)) -> #isLNat(activate(V1)) #68: #isPLNat(n__pair(V1,V2)) -> #activate(V1) #69: #isPLNat(n__pair(V1,V2)) -> #activate(V2) #70: #isLNat(n__tail(V1)) -> #isLNat(activate(V1)) #71: #isLNat(n__tail(V1)) -> #activate(V1) #72: #splitAt(s(N),cons(X,XS)) -> #U81(and(isNatural(N),n__and(isNatural(X),n__isLNat(activate(XS)))),N,X,activate(XS)) #73: #splitAt(s(N),cons(X,XS)) -> #and(isNatural(N),n__and(isNatural(X),n__isLNat(activate(XS)))) #74: #splitAt(s(N),cons(X,XS)) -> #isNatural(N) #75: #splitAt(s(N),cons(X,XS)) -> #isNatural(X) #76: #splitAt(s(N),cons(X,XS)) -> #activate(XS) #77: #splitAt(s(N),cons(X,XS)) -> #activate(XS) #78: #isNatural(n__sel(V1,V2)) -> #and(isNatural(activate(V1)),n__isLNat(activate(V2))) #79: #isNatural(n__sel(V1,V2)) -> #isNatural(activate(V1)) #80: #isNatural(n__sel(V1,V2)) -> #activate(V1) #81: #isNatural(n__sel(V1,V2)) -> #activate(V2) #82: #activate(n__tail(X)) -> #tail(X) #83: #isLNat(n__afterNth(V1,V2)) -> #and(isNatural(activate(V1)),n__isLNat(activate(V2))) #84: #isLNat(n__afterNth(V1,V2)) -> #isNatural(activate(V1)) #85: #isLNat(n__afterNth(V1,V2)) -> #activate(V1) #86: #isLNat(n__afterNth(V1,V2)) -> #activate(V2) #87: #snd(pair(X,Y)) -> #U61(and(isLNat(X),n__isLNat(Y)),Y) #88: #snd(pair(X,Y)) -> #and(isLNat(X),n__isLNat(Y)) #89: #snd(pair(X,Y)) -> #isLNat(X) #90: #isLNat(n__fst(V1)) -> #isPLNat(activate(V1)) #91: #isLNat(n__fst(V1)) -> #activate(V1) #92: #activate(n__head(X)) -> #head(X) #93: #isNatural(n__s(V1)) -> #isNatural(activate(V1)) #94: #isNatural(n__s(V1)) -> #activate(V1) #95: #activate(n__and(X1,X2)) -> #and(X1,X2) #96: #take(N,XS) -> #U101(and(isNatural(N),n__isLNat(XS)),N,XS) #97: #take(N,XS) -> #and(isNatural(N),n__isLNat(XS)) #98: #take(N,XS) -> #isNatural(N) #99: #isLNat(n__snd(V1)) -> #isPLNat(activate(V1)) #100: #isLNat(n__snd(V1)) -> #activate(V1) #101: #U21(tt(),X) -> #activate(X) #102: #U101(tt(),N,XS) -> #fst(splitAt(activate(N),activate(XS))) #103: #U101(tt(),N,XS) -> #splitAt(activate(N),activate(XS)) #104: #U101(tt(),N,XS) -> #activate(N) #105: #U101(tt(),N,XS) -> #activate(XS) #106: #activate(n__isLNat(X)) -> #isLNat(X) #107: #U71(tt(),XS) -> #pair(nil(),activate(XS)) #108: #U71(tt(),XS) -> #nil() #109: #U71(tt(),XS) -> #activate(XS) #110: #head(cons(N,XS)) -> #U31(and(isNatural(N),n__isLNat(activate(XS))),N) #111: #head(cons(N,XS)) -> #and(isNatural(N),n__isLNat(activate(XS))) #112: #head(cons(N,XS)) -> #isNatural(N) #113: #head(cons(N,XS)) -> #activate(XS) #114: #U31(tt(),N) -> #activate(N) #115: #isLNat(n__cons(V1,V2)) -> #and(isNatural(activate(V1)),n__isLNat(activate(V2))) #116: #isLNat(n__cons(V1,V2)) -> #isNatural(activate(V1)) #117: #isLNat(n__cons(V1,V2)) -> #activate(V1) #118: #isLNat(n__cons(V1,V2)) -> #activate(V2) Number of SCCs: 1, DPs: 107 SCC { #1..13 #15..22 #24..31 #33..46 #48..54 #57 #59 #60 #62 #64..106 #109..118 } POLO(Sum)... POLO(max)... succeeded. #0 w: 0 U21 w: max(x1, x2) U11 w: max(x2 + 22, x3 + 22) #cons w: 0 s w: x1 n__pair w: max(x1 + 9, x2 + 15) #take w: max(x1 + 28, x2 + 31) isPLNat w: x1 U91 w: max(x2 + 3) #U101 w: max(x2 + 27, x3 + 27) activate w: x1 n__isLNat w: x1 + 2 #U82 w: max(x1, x2 + 9) take w: max(x1 + 22, x2 + 24) U71 w: max(x1 + 5, x2 + 15) #U81 w: max(x1 + 13, x2 + 22, x3 + 20, x4 + 16) and w: max(x1 + 3, x2) U101 w: max(x2 + 22, x3 + 16) pair w: max(x1 + 9, x2 + 15) fst w: x1 + 1 #activate w: x1 + 8 natsFrom w: x1 + 5 #head w: x1 + 16 splitAt w: max(x1 + 21, x2 + 15) #fst w: x1 + 5 n__nil w: 6 n__natsFrom w: x1 + 5 isNatural w: x1 + 4 n__snd w: x1 + 1 n__s w: x1 n__splitAt w: max(x1 + 21, x2 + 15) tail w: x1 + 9 0 w: 1 n__take w: max(x1 + 22, x2 + 24) #sel w: max(x1 + 47, x2 + 45) #isLNat w: x1 + 10 sel w: max(x1 + 41, x2 + 42) #s w: 0 afterNth w: max(x1 + 24, x2 + 22) n__cons w: max(x1 + 5, x2) #isPLNat w: x1 + 6 nil w: 6 isLNat w: x1 + 2 n__sel w: max(x1 + 41, x2 + 42) #tail w: x1 + 16 #splitAt w: max(x1 + 22, x2 + 16) #nil w: 0 n__tail w: x1 + 9 #afterNth w: max(x1 + 31, x2 + 28) n__0 w: 1 n__afterNth w: max(x1 + 24, x2 + 22) U61 w: max(x2) #U51 w: max(x1 + 37, x2 + 46, x3 + 41) n__fst w: x1 + 1 #U11 w: max(x1 + 23, x2 + 27, x3 + 27) U31 w: max(x2 + 10) head w: x1 + 9 #snd w: x1 + 5 #U41 w: max(x1 + 5, x2 + 9) cons w: max(x1 + 5, x2) #natsFrom w: x1 + 10 snd w: x1 + 1 #U21 w: max(x2 + 9) U81 w: max(x1 + 9, x2 + 21, x3 + 14, x4 + 15) U82 w: max(x1, x2 + 14) tt w: 4 n__and w: max(x1 + 3, x2) #U71 w: max(x2 + 9) #isNatural w: x1 + 9 #pair w: 0 n__head w: x1 + 9 U51 w: max(x1 + 26, x2 + 33, x3 + 42) U41 w: max(x1 + 1, x2 + 5) #U31 w: max(x2 + 9) #and w: max(x1 + 11, x2 + 8) #U91 w: max(x2 + 9) #U61 w: max(x2 + 15) USABLE RULES: { 1..69 } Removed DPs: #1..13 #15..22 #24 #26 #28..31 #33..46 #48..54 #57 #59 #60 #62 #64..71 #73..92 #94 #96..105 #109..114 #116..118 Number of SCCs: 3, DPs: 7 SCC { #93 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded. #0 s: [] p: 0 w: 0 U21 s: [2] p: 2 w: max(x2 + 4) U11 s: [3] p: 5 w: max(x3 + 6) #cons s: [] p: 0 w: max(x2) s s: [1] p: 5 w: x1 n__pair s: [1,2] p: 1 w: max(x1, x2 + 3) #take s: [1,2] p: 0 w: x1 + x2 + 1 isPLNat s: [] p: 1 w: 13 U91 s: [2] p: 5 w: max(x2 + 1) #U101 s: [3,1] p: 0 w: x1 + x3 + 1 activate s: 1 n__isLNat s: [] p: 1 w: 13 #U82 s: [2] p: 0 w: x2 + 1 take s: [1] p: 6 w: x1 + x2 + 12 U71 s: [2] p: 3 w: max(x2 + 4) #U81 s: [3,2] p: 0 w: max(x2, x3) and s: 2 U101 s: [] p: 6 w: max(x2 + 11, x3 + 11) pair s: [1,2] p: 1 w: max(x1, x2 + 3) fst s: [] p: 5 w: x1 + 5 #activate s: [] p: 0 w: 0 natsFrom s: [] p: 6 w: x1 + 15 #head s: [] p: 0 w: 0 splitAt s: [] p: 4 w: max(x2 + 5) #fst s: [] p: 0 w: 1 n__nil s: [] p: 5 w: 1 n__natsFrom s: [] p: 6 w: x1 + 15 isNatural s: [] p: 1 w: 13 n__snd s: [1] p: 4 w: x1 n__s s: [1] p: 5 w: x1 n__splitAt s: [] p: 4 w: max(x2 + 5) tail s: [] p: 6 w: x1 + 1 0 s: [] p: 0 w: 0 n__take s: [1] p: 6 w: x1 + x2 + 12 #sel s: [] p: 0 w: x1 #isLNat s: [] p: 0 w: 1 sel s: [2,1] p: 6 w: x1 + x2 + 29 #s s: [] p: 0 w: 0 afterNth s: [2] p: 5 w: max(x2 + 7) n__cons s: [] p: 3 w: max(x1 + 14, x2) #isPLNat s: [] p: 0 w: 1 nil s: [] p: 5 w: 1 isLNat s: [] p: 1 w: 13 n__sel s: [2,1] p: 6 w: x1 + x2 + 29 #tail s: [] p: 0 w: 1 #splitAt s: [] p: 0 w: 0 #nil s: [] p: 0 w: 0 n__tail s: [] p: 6 w: x1 + 1 #afterNth s: [] p: 0 w: 1 n__0 s: [] p: 0 w: 0 n__afterNth s: [2] p: 5 w: max(x2 + 7) U61 s: [] p: 1 w: max(x2 + 1) #U51 s: [3] p: 0 w: x2 + x3 n__fst s: [] p: 5 w: x1 + 5 #U11 s: [1,3] p: 0 w: x1 + x2 + x3 + 1 U31 s: [] p: 4 w: max(x2 + 15) head s: [] p: 4 w: x1 + 9 #snd s: [] p: 0 w: 1 #U41 s: [2,1] p: 0 w: x1 + x2 + 1 cons s: [] p: 3 w: max(x1 + 14, x2) #natsFrom s: [] p: 0 w: 0 snd s: [1] p: 4 w: x1 #U21 s: [] p: 0 w: x2 U81 s: [3] p: 3 w: max(x3 + 14, x4 + 5) U82 s: [2] p: 3 w: max(x1, x2 + 14) tt s: [] p: 4 w: 2 n__and s: 2 #U71 s: [] p: 0 w: x2 #isNatural s: [1] p: 0 w: x1 + 1 #pair s: [] p: 0 w: max(x2) n__head s: [] p: 4 w: x1 + 9 U51 s: [3,1] p: 5 w: max(x1 + 15, x2 + 8, x3 + 17) U41 s: [] p: 6 w: max(x2 + 15) #U31 s: [1] p: 0 w: x1 + 1 #and s: [] p: 0 w: max(x1 + 1) #U91 s: [1,2] p: 0 w: x1 + x2 + 1 #U61 s: [] p: 0 w: 0 USABLE RULES: { 1..69 } Removed DPs: #93 Number of SCCs: 2, DPs: 6 SCC { #25 #95 #106 #115 } POLO(Sum)... succeeded. #0 w: 0 U21 w: x1 + x2 + 4 U11 w: x3 + 8 #cons w: 0 s w: x1 + 7 n__pair w: 1 #take w: 2 isPLNat w: 16 U91 w: x1 + x2 + 5 #U101 w: 2 activate w: x1 + 5 n__isLNat w: 1 #U82 w: 2 take w: 10 U71 w: x2 + 11 #U81 w: 2 and w: x1 U101 w: x1 + 17 pair w: x1 + 7 fst w: x1 + 9 #activate w: x1 + 2 natsFrom w: x1 + 28 #head w: 2 splitAt w: x1 + 3 #fst w: 2 n__nil w: 1 n__natsFrom w: x1 + 4 isNatural w: 17 n__snd w: 2 n__s w: 1 n__splitAt w: 4 tail w: x1 + 26 0 w: 7 n__take w: x2 + 4 #sel w: 2 #isLNat w: 3 sel w: x2 #s w: 0 afterNth w: x1 + x2 + 7 n__cons w: x1 + x2 + 2 #isPLNat w: 2 nil w: 7 isLNat w: x1 + 13 n__sel w: x2 + 1 #tail w: 2 #splitAt w: 2 #nil w: 0 n__tail w: 27 #afterNth w: 2 n__0 w: 1 n__afterNth w: x1 + 1 U61 w: x2 + 9 #U51 w: 2 n__fst w: x1 + 3 #U11 w: 2 U31 w: 0 head w: x1 + 7 #snd w: 2 #U41 w: 2 cons w: x2 + 1 #natsFrom w: 2 snd w: x1 + 1 #U21 w: 2 U81 w: 11 U82 w: 4 tt w: 0 n__and w: x2 + 1 #U71 w: 2 #isNatural w: 2 #pair w: 0 n__head w: 1 U51 w: 0 U41 w: x1 + x2 + 18 #U31 w: 2 #and w: x2 + 2 #U91 w: 2 #U61 w: 2 USABLE RULES: { 39 50 } Removed DPs: #95 Number of SCCs: 2, DPs: 5 SCC { #25 #106 #115 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed. Finding a loop... failed.