/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Input TRS: 1: a__U11(tt(),V2) -> a__U12(a__isNat(V2)) 2: a__U12(tt()) -> tt() 3: a__U21(tt()) -> tt() 4: a__U31(tt(),V2) -> a__U32(a__isNat(V2)) 5: a__U32(tt()) -> tt() 6: a__U41(tt(),N) -> mark(N) 7: a__U51(tt(),M,N) -> a__U52(a__isNat(N),M,N) 8: a__U52(tt(),M,N) -> s(a__plus(mark(N),mark(M))) 9: a__U61(tt()) -> 0() 10: a__U71(tt(),M,N) -> a__U72(a__isNat(N),M,N) 11: a__U72(tt(),M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N)) 12: a__isNat(0()) -> tt() 13: a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2) 14: a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 15: a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2) 16: a__plus(N,0()) -> a__U41(a__isNat(N),N) 17: a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N) 18: a__x(N,0()) -> a__U61(a__isNat(N)) 19: a__x(N,s(M)) -> a__U71(a__isNat(M),M,N) 20: mark(U11(X1,X2)) -> a__U11(mark(X1),X2) 21: mark(U12(X)) -> a__U12(mark(X)) 22: mark(isNat(X)) -> a__isNat(X) 23: mark(U21(X)) -> a__U21(mark(X)) 24: mark(U31(X1,X2)) -> a__U31(mark(X1),X2) 25: mark(U32(X)) -> a__U32(mark(X)) 26: mark(U41(X1,X2)) -> a__U41(mark(X1),X2) 27: mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3) 28: mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3) 29: mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2)) 30: mark(U61(X)) -> a__U61(mark(X)) 31: mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3) 32: mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3) 33: mark(x(X1,X2)) -> a__x(mark(X1),mark(X2)) 34: mark(tt()) -> tt() 35: mark(s(X)) -> s(mark(X)) 36: mark(0()) -> 0() 37: a__U11(X1,X2) -> U11(X1,X2) 38: a__U12(X) -> U12(X) 39: a__isNat(X) -> isNat(X) 40: a__U21(X) -> U21(X) 41: a__U31(X1,X2) -> U31(X1,X2) 42: a__U32(X) -> U32(X) 43: a__U41(X1,X2) -> U41(X1,X2) 44: a__U51(X1,X2,X3) -> U51(X1,X2,X3) 45: a__U52(X1,X2,X3) -> U52(X1,X2,X3) 46: a__plus(X1,X2) -> plus(X1,X2) 47: a__U61(X) -> U61(X) 48: a__U71(X1,X2,X3) -> U71(X1,X2,X3) 49: a__U72(X1,X2,X3) -> U72(X1,X2,X3) 50: a__x(X1,X2) -> x(X1,X2) Number of strict rules: 50 Direct poly ... failed. Freezing ... failed. Dependency Pairs: #1: #mark(plus(X1,X2)) -> #a__plus(mark(X1),mark(X2)) #2: #mark(plus(X1,X2)) -> #mark(X1) #3: #mark(plus(X1,X2)) -> #mark(X2) #4: #mark(s(X)) -> #mark(X) #5: #a__U41(tt(),N) -> #mark(N) #6: #a__isNat(plus(V1,V2)) -> #a__U11(a__isNat(V1),V2) #7: #a__isNat(plus(V1,V2)) -> #a__isNat(V1) #8: #a__U72(tt(),M,N) -> #a__plus(a__x(mark(N),mark(M)),mark(N)) #9: #a__U72(tt(),M,N) -> #a__x(mark(N),mark(M)) #10: #a__U72(tt(),M,N) -> #mark(N) #11: #a__U72(tt(),M,N) -> #mark(M) #12: #a__U72(tt(),M,N) -> #mark(N) #13: #mark(U31(X1,X2)) -> #a__U31(mark(X1),X2) #14: #mark(U31(X1,X2)) -> #mark(X1) #15: #mark(U21(X)) -> #a__U21(mark(X)) #16: #mark(U21(X)) -> #mark(X) #17: #mark(U71(X1,X2,X3)) -> #a__U71(mark(X1),X2,X3) #18: #mark(U71(X1,X2,X3)) -> #mark(X1) #19: #a__isNat(s(V1)) -> #a__U21(a__isNat(V1)) #20: #a__isNat(s(V1)) -> #a__isNat(V1) #21: #mark(U61(X)) -> #a__U61(mark(X)) #22: #mark(U61(X)) -> #mark(X) #23: #mark(U32(X)) -> #a__U32(mark(X)) #24: #mark(U32(X)) -> #mark(X) #25: #mark(U11(X1,X2)) -> #a__U11(mark(X1),X2) #26: #mark(U11(X1,X2)) -> #mark(X1) #27: #a__U51(tt(),M,N) -> #a__U52(a__isNat(N),M,N) #28: #a__U51(tt(),M,N) -> #a__isNat(N) #29: #a__U71(tt(),M,N) -> #a__U72(a__isNat(N),M,N) #30: #a__U71(tt(),M,N) -> #a__isNat(N) #31: #mark(x(X1,X2)) -> #a__x(mark(X1),mark(X2)) #32: #mark(x(X1,X2)) -> #mark(X1) #33: #mark(x(X1,X2)) -> #mark(X2) #34: #mark(U52(X1,X2,X3)) -> #a__U52(mark(X1),X2,X3) #35: #mark(U52(X1,X2,X3)) -> #mark(X1) #36: #mark(isNat(X)) -> #a__isNat(X) #37: #mark(U51(X1,X2,X3)) -> #a__U51(mark(X1),X2,X3) #38: #mark(U51(X1,X2,X3)) -> #mark(X1) #39: #a__plus(N,s(M)) -> #a__U51(a__isNat(M),M,N) #40: #a__plus(N,s(M)) -> #a__isNat(M) #41: #mark(U72(X1,X2,X3)) -> #a__U72(mark(X1),X2,X3) #42: #mark(U72(X1,X2,X3)) -> #mark(X1) #43: #a__x(N,s(M)) -> #a__U71(a__isNat(M),M,N) #44: #a__x(N,s(M)) -> #a__isNat(M) #45: #mark(U41(X1,X2)) -> #a__U41(mark(X1),X2) #46: #mark(U41(X1,X2)) -> #mark(X1) #47: #mark(U12(X)) -> #a__U12(mark(X)) #48: #mark(U12(X)) -> #mark(X) #49: #a__plus(N,0()) -> #a__U41(a__isNat(N),N) #50: #a__plus(N,0()) -> #a__isNat(N) #51: #a__U11(tt(),V2) -> #a__U12(a__isNat(V2)) #52: #a__U11(tt(),V2) -> #a__isNat(V2) #53: #a__U52(tt(),M,N) -> #a__plus(mark(N),mark(M)) #54: #a__U52(tt(),M,N) -> #mark(N) #55: #a__U52(tt(),M,N) -> #mark(M) #56: #a__isNat(x(V1,V2)) -> #a__U31(a__isNat(V1),V2) #57: #a__isNat(x(V1,V2)) -> #a__isNat(V1) #58: #a__U31(tt(),V2) -> #a__U32(a__isNat(V2)) #59: #a__U31(tt(),V2) -> #a__isNat(V2) #60: #a__x(N,0()) -> #a__U61(a__isNat(N)) #61: #a__x(N,0()) -> #a__isNat(N) Number of SCCs: 2, DPs: 44 SCC { #6 #7 #20 #52 #56 #57 #59 } Sum... succeeded. a__plus(x1,x2) w: (0) U21(x1) w: (0) #a__U72(x1,x2,x3) w: (0) #a__U71(x1,x2,x3) w: (0) U11(x1,x2) w: (0) s(x1) w: (2 + x1) #a__U31(x1,x2) w: (2 + x2 + x1) #a__isNat(x1) w: (x1) U71(x1,x2,x3) w: (0) #a__U51(x1,x2,x3) w: (0) #a__x(x1,x2) w: (0) U72(x1,x2,x3) w: (0) #a__U11(x1,x2) w: (8855 + x2 + x1) a__U31(x1,x2) w: (4 + x2 + x1) a__U51(x1,x2,x3) w: (0) a__x(x1,x2) w: (0) U12(x1) w: (0) a__U41(x1,x2) w: (0) x(x1,x2) w: (11801 + x2 + x1) #a__U12(x1) w: (0) #a__U21(x1) w: (0) #a__U61(x1) w: (0) #a__plus(x1,x2) w: (0) #mark(x1) w: (0) 0() w: (1) a__U21(x1) w: (2 + x1) a__U32(x1) w: (3 + x1) #a__U52(x1,x2,x3) w: (0) mark(x1) w: (0) a__U72(x1,x2,x3) w: (0) a__U11(x1,x2) w: (x2 + x1) U32(x1) w: (0) a__U52(x1,x2,x3) w: (0) a__U12(x1) w: (x1) isNat(x1) w: (0) U52(x1,x2,x3) w: (0) plus(x1,x2) w: (8857 + x2 + x1) U61(x1) w: (0) U31(x1,x2) w: (0) a__U71(x1,x2,x3) w: (0) a__U61(x1) w: (0) #a__U41(x1,x2) w: (0) tt() w: (1) a__isNat(x1) w: (1 + x1) U51(x1,x2,x3) w: (0) U41(x1,x2) w: (0) #a__U32(x1) w: (0) USABLE RULES: { 1..5 12..15 37..42 } Removed DPs: #6 #7 #20 #52 #56 #57 #59 Number of SCCs: 1, DPs: 37 SCC { #1..5 #8..12 #14 #16..18 #22 #24 #26 #27 #29 #31..35 #37..39 #41..43 #45 #46 #48 #49 #53..55 } Sum... Max... succeeded. a__plus(x1,x2) w: (max{4 + x2, x1}) U21(x1) w: (x1) #a__U72(x1,x2,x3) w: (max{8 + x3, 12 + x2, 3 + x1}) #a__U71(x1,x2,x3) w: (max{8 + x3, 12 + x2, 7 + x1}) U11(x1,x2) w: (max{0, x1}) s(x1) w: (x1) #a__U31(x1,x2) w: (0) #a__isNat(x1) w: (0) U71(x1,x2,x3) w: (max{6 + x3, 10 + x2, 7 + x1}) #a__U51(x1,x2,x3) w: (max{2 + x3, 4 + x2, 0}) #a__x(x1,x2) w: (max{12 + x2, 8 + x1}) U72(x1,x2,x3) w: (max{6 + x3, 10 + x2, 1 + x1}) #a__U11(x1,x2) w: (0) a__U31(x1,x2) w: (max{0, x1}) a__U51(x1,x2,x3) w: (max{x3, 4 + x2, 1 + x1}) a__x(x1,x2) w: (max{10 + x2, 6 + x1}) U12(x1) w: (x1) a__U41(x1,x2) w: (max{x2, 2 + x1}) x(x1,x2) w: (max{10 + x2, 6 + x1}) #a__U12(x1) w: (0) #a__U21(x1) w: (0) #a__U61(x1) w: (0) #a__plus(x1,x2) w: (max{4 + x2, 2 + x1}) #mark(x1) w: (2 + x1) 0() w: (1) a__U21(x1) w: (x1) a__U32(x1) w: (x1) #a__U52(x1,x2,x3) w: (max{2 + x3, 4 + x2, 1 + x1}) mark(x1) w: (x1) a__U72(x1,x2,x3) w: (max{6 + x3, 10 + x2, 1 + x1}) a__U11(x1,x2) w: (max{0, x1}) U32(x1) w: (x1) a__U52(x1,x2,x3) w: (max{x3, 4 + x2, 1 + x1}) a__U12(x1) w: (x1) isNat(x1) w: (2) U52(x1,x2,x3) w: (max{x3, 4 + x2, 1 + x1}) plus(x1,x2) w: (max{4 + x2, x1}) U61(x1) w: (5 + x1) U31(x1,x2) w: (max{0, x1}) a__U71(x1,x2,x3) w: (max{6 + x3, 10 + x2, 7 + x1}) a__U61(x1) w: (5 + x1) #a__U41(x1,x2) w: (max{2 + x2, 0}) tt() w: (2) a__isNat(x1) w: (2) U51(x1,x2,x3) w: (max{x3, 4 + x2, 1 + x1}) U41(x1,x2) w: (max{x2, 2 + x1}) #a__U32(x1) w: (0) USABLE RULES: { 1..50 } Removed DPs: #3 #10..12 #18 #22 #32 #33 #35 #38 #42 #46 #55 Number of SCCs: 1, DPs: 24 SCC { #1 #2 #4 #5 #8 #9 #14 #16 #17 #24 #26 #27 #29 #31 #34 #37 #39 #41 #43 #45 #48 #49 #53 #54 } Sum... Max... succeeded. a__plus(x1,x2) w: (max{1 + x2, x1}) U21(x1) w: (x1) #a__U72(x1,x2,x3) w: (max{2 + x3, 1187 + x2, 0}) #a__U71(x1,x2,x3) w: (max{2 + x3, 1187 + x2, 0}) U11(x1,x2) w: (max{1 + x2, x1}) s(x1) w: (x1) #a__U31(x1,x2) w: (0) #a__isNat(x1) w: (0) U71(x1,x2,x3) w: (max{1 + x3, 1186 + x2, 1185 + x1}) #a__U51(x1,x2,x3) w: (max{1 + x3, 0}) #a__x(x1,x2) w: (max{1187 + x2, 2 + x1}) U72(x1,x2,x3) w: (max{1 + x3, 1186 + x2, 0}) #a__U11(x1,x2) w: (0) a__U31(x1,x2) w: (max{1 + x2, 1 + x1}) a__U51(x1,x2,x3) w: (max{x3, 1 + x2, 0}) a__x(x1,x2) w: (max{1186 + x2, 1 + x1}) U12(x1) w: (1 + x1) a__U41(x1,x2) w: (max{x2, 0}) x(x1,x2) w: (max{1186 + x2, 1 + x1}) #a__U12(x1) w: (0) #a__U21(x1) w: (0) #a__U61(x1) w: (0) #a__plus(x1,x2) w: (max{0, 1 + x1}) #mark(x1) w: (1 + x1) 0() w: (1) a__U21(x1) w: (x1) a__U32(x1) w: (1 + x1) #a__U52(x1,x2,x3) w: (max{1 + x3, 0, x1}) mark(x1) w: (x1) a__U72(x1,x2,x3) w: (max{1 + x3, 1186 + x2, 0}) a__U11(x1,x2) w: (max{1 + x2, x1}) U32(x1) w: (1 + x1) a__U52(x1,x2,x3) w: (max{x3, 1 + x2, x1}) a__U12(x1) w: (1 + x1) isNat(x1) w: (x1) U52(x1,x2,x3) w: (max{x3, 1 + x2, x1}) plus(x1,x2) w: (max{1 + x2, x1}) U61(x1) w: (1) U31(x1,x2) w: (max{1 + x2, 1 + x1}) a__U71(x1,x2,x3) w: (max{1 + x3, 1186 + x2, 1185 + x1}) a__U61(x1) w: (1) #a__U41(x1,x2) w: (max{1 + x2, 0}) tt() w: (1) a__isNat(x1) w: (x1) U51(x1,x2,x3) w: (max{x3, 1 + x2, 0}) U41(x1,x2) w: (max{x2, 0}) #a__U32(x1) w: (0) USABLE RULES: { 1..50 } Removed DPs: #14 #24 #48 Number of SCCs: 1, DPs: 21 SCC { #1 #2 #4 #5 #8 #9 #16 #17 #26 #27 #29 #31 #34 #37 #39 #41 #43 #45 #49 #53 #54 } Sum... Max... QLPOpS... succeeded. a__plus(x1,x2) 5[x2,x1] U21(x1) x1 #a__U72(x1,x2,x3) 6[x3,x2] #a__U71(x1,x2,x3) 6[x3,x2] U11(x1,x2) x1 s(x1) 4[x1] #a__U31(x1,x2) 0[] #a__isNat(x1) 0[] U71(x1,x2,x3) 6[x3,x2,x1] #a__U51(x1,x2,x3) x3 #a__x(x1,x2) 6[x1,x2] U72(x1,x2,x3) 6[x3,x2,x1] #a__U11(x1,x2) 0[x2,x1] a__U31(x1,x2) 4[] a__U51(x1,x2,x3) 5[x2,x3,x1] a__x(x1,x2) 6[x1,x2] U12(x1) 4[] a__U41(x1,x2) 1[x2] x(x1,x2) 6[x1,x2] #a__U12(x1) 0[] #a__U21(x1) 0[] #a__U61(x1) 0[] #a__plus(x1,x2) x1 #mark(x1) x1 0() 3 a__U21(x1) x1 a__U32(x1) x1 #a__U52(x1,x2,x3) x3 mark(x1) x1 a__U72(x1,x2,x3) 6[x3,x2,x1] a__U11(x1,x2) x1 U32(x1) x1 a__U52(x1,x2,x3) 5[x2,x3,x1] a__U12(x1) 4[] isNat(x1) 4[] U52(x1,x2,x3) 5[x2,x3,x1] plus(x1,x2) 5[x2,x1] U61(x1) 3[] U31(x1,x2) 4[] a__U71(x1,x2,x3) 6[x3,x2,x1] a__U61(x1) 3[] #a__U41(x1,x2) x2 tt() 4 a__isNat(x1) 4[] U51(x1,x2,x3) 5[x2,x3,x1] U41(x1,x2) 1[x2] #a__U32(x1) 0[] USABLE RULES: { 1..50 } Removed DPs: #1 #2 #4 #17 #34 #37 #41 #43 #45 Number of SCCs: 2, DPs: 5 SCC { #16 #26 } Sum... succeeded. a__plus(x1,x2) w: (5) U21(x1) w: (21 + x1) #a__U72(x1,x2,x3) w: (17) #a__U71(x1,x2,x3) w: (16) U11(x1,x2) w: (10 + x1) s(x1) w: (17) #a__U31(x1,x2) w: (2) #a__isNat(x1) w: (0) U71(x1,x2,x3) w: (4 + x3) #a__U51(x1,x2,x3) w: (16) #a__x(x1,x2) w: (17) U72(x1,x2,x3) w: (5) #a__U11(x1,x2) w: (8855) a__U31(x1,x2) w: (8 + x2) a__U51(x1,x2,x3) w: (6 + x3 + x2) a__x(x1,x2) w: (2) U12(x1) w: (11) a__U41(x1,x2) w: (6) x(x1,x2) w: (5) #a__U12(x1) w: (0) #a__U21(x1) w: (0) #a__U61(x1) w: (0) #a__plus(x1,x2) w: (16) #mark(x1) w: (16 + x1) 0() w: (5) a__U21(x1) w: (20) a__U32(x1) w: (9) #a__U52(x1,x2,x3) w: (16) mark(x1) w: (1) a__U72(x1,x2,x3) w: (4 + x3 + x2) a__U11(x1,x2) w: (9 + x2) U32(x1) w: (10) a__U52(x1,x2,x3) w: (5 + x3 + x2 + x1) a__U12(x1) w: (10) isNat(x1) w: (3 + x1) U52(x1,x2,x3) w: (8) plus(x1,x2) w: (6 + x1) U61(x1) w: (5) U31(x1,x2) w: (9) a__U71(x1,x2,x3) w: (3) a__U61(x1) w: (4) #a__U41(x1,x2) w: (16) tt() w: (11) a__isNat(x1) w: (2 + x1) U51(x1,x2,x3) w: (7 + x1) U41(x1,x2) w: (7 + x2 + x1) #a__U32(x1) w: (0) USABLE RULES: { } Removed DPs: #16 #26 Number of SCCs: 1, DPs: 3 SCC { #27 #39 #53 } Sum... Max... QLPOpS... succeeded. a__plus(x1,x2) 5[x2,x1] U21(x1) x1 #a__U72(x1,x2,x3) 6[x3,x2] #a__U71(x1,x2,x3) 6[x3,x2] U11(x1,x2) x1 s(x1) 4[x1] #a__U31(x1,x2) 0[] #a__isNat(x1) 0[] U71(x1,x2,x3) 6[x3,x2,x1] #a__U51(x1,x2,x3) 1[x2,x3,x1] #a__x(x1,x2) 6[x1,x2] U72(x1,x2,x3) 6[x3,x2,x1] #a__U11(x1,x2) 0[x2,x1] a__U31(x1,x2) 4[] a__U51(x1,x2,x3) 5[x2,x3,x1] a__x(x1,x2) 6[x1,x2] U12(x1) 4[] a__U41(x1,x2) 1[x2] x(x1,x2) 6[x1,x2] #a__U12(x1) 0[] #a__U21(x1) 0[] #a__U61(x1) 0[] #a__plus(x1,x2) 1[x2,x1] #mark(x1) x1 0() 3 a__U21(x1) x1 a__U32(x1) x1 #a__U52(x1,x2,x3) 1[x2,x3] mark(x1) x1 a__U72(x1,x2,x3) 6[x3,x2,x1] a__U11(x1,x2) x1 U32(x1) x1 a__U52(x1,x2,x3) 5[x2,x3,x1] a__U12(x1) 4[] isNat(x1) 4[] U52(x1,x2,x3) 5[x2,x3,x1] plus(x1,x2) 5[x2,x1] U61(x1) 3[] U31(x1,x2) 4[] a__U71(x1,x2,x3) 6[x3,x2,x1] a__U61(x1) 3[] #a__U41(x1,x2) x2 tt() 4 a__isNat(x1) 4[] U51(x1,x2,x3) 5[x2,x3,x1] U41(x1,x2) 1[x2] #a__U32(x1) 0[] USABLE RULES: { 1..50 } Removed DPs: #27 #39 Number of SCCs: 0, DPs: 0