WORST_CASE(?,O(n^2)) * Step 1: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#0(),y) -> #0() #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [1] p(#add) = [1] x1 + [1] x2 + [0] p(#mult) = [7] p(#natadd) = [1] x2 + [5] p(#natmult) = [0] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [3] p(#pred) = [1] x1 + [0] p(#s) = [1] x1 + [0] p(#succ) = [1] x1 + [0] p(dd) = [1] x1 + [1] x2 + [0] p(dyade) = [0] p(dyade#1) = [0] p(mult) = [0] p(mult#1) = [5] p(nil) = [0] Following rules are strictly oriented: #add(#0(),y) = [1] y + [1] > [1] y + [0] = y #add(#neg(#s(#0())),y) = [1] y + [1] > [1] y + [0] = #pred(y) #add(#pos(#s(#0())),y) = [1] y + [4] > [1] y + [0] = #succ(y) #mult(#0(),#0()) = [7] > [1] = #0() #mult(#0(),#neg(y)) = [7] > [1] = #0() #mult(#0(),#pos(y)) = [7] > [1] = #0() #mult(#neg(x),#0()) = [7] > [1] = #0() #mult(#neg(x),#neg(y)) = [7] > [3] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [7] > [0] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [7] > [1] = #0() #mult(#pos(x),#neg(y)) = [7] > [0] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [7] > [3] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [5] > [1] y + [0] = y #pred(#pos(#s(#0()))) = [4] > [1] = #0() mult#1(dd(x,xs),n) = [5] > [0] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [5] > [0] = nil() Following rules are (at-least) weakly oriented: #add(#neg(#s(#s(x))),y) = [1] x + [1] y + [0] >= [1] x + [1] y + [3] = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#s(x))),y) = [1] x + [1] y + [3] >= [1] x + [1] y + [3] = #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) = [1] y + [5] >= [1] y + [5] = #s(#natadd(x,y)) #natmult(#0(),y) = [0] >= [1] = #0() #natmult(#s(x),y) = [0] >= [5] = #natadd(y,#natmult(x,y)) #pred(#0()) = [1] >= [1] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [0] >= [1] x + [0] = #neg(#s(#s(x))) #pred(#pos(#s(#s(x)))) = [1] x + [3] >= [1] x + [3] = #pos(#s(x)) #succ(#0()) = [1] >= [4] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [1] >= [1] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [0] >= [1] x + [0] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [3] >= [1] x + [3] = #pos(#s(#s(x))) dyade(l1,l2) = [0] >= [0] = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = [0] >= [0] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [0] >= [0] = nil() mult(n,l) = [0] >= [5] = mult#1(l,n) mult(x,y) = [0] >= [7] = #mult(x,y) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#0(),y) -> #0() #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#pos(#s(#0())),y) -> #succ(y) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #pred(#pos(#s(#0()))) -> #0() mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [1] p(#add) = [1] x1 + [2] x2 + [5] p(#mult) = [7] p(#natadd) = [1] x2 + [0] p(#natmult) = [2] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [0] p(#s) = [1] x1 + [1] p(#succ) = [1] x1 + [5] p(dd) = [1] x1 + [1] x2 + [0] p(dyade) = [3] p(dyade#1) = [7] p(mult) = [0] p(mult#1) = [0] p(nil) = [0] Following rules are strictly oriented: #add(#neg(#s(#s(x))),y) = [1] x + [2] y + [7] > [1] x + [2] y + [6] = #pred(#add(#pos(#s(x)),y)) #natmult(#0(),y) = [2] > [1] = #0() #pred(#pos(#s(#s(x)))) = [1] x + [2] > [1] x + [1] = #pos(#s(x)) #succ(#0()) = [6] > [2] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [7] > [1] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [7] > [1] x + [1] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [6] > [1] x + [2] = #pos(#s(#s(x))) dyade#1(dd(x,xs),l2) = [7] > [3] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [7] > [0] = nil() Following rules are (at-least) weakly oriented: #add(#0(),y) = [2] y + [6] >= [1] y + [0] = y #add(#neg(#s(#0())),y) = [2] y + [7] >= [1] y + [0] = #pred(y) #add(#pos(#s(#0())),y) = [2] y + [7] >= [1] y + [5] = #succ(y) #add(#pos(#s(#s(x))),y) = [1] x + [2] y + [7] >= [1] x + [2] y + [11] = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = [7] >= [1] = #0() #mult(#0(),#neg(y)) = [7] >= [1] = #0() #mult(#0(),#pos(y)) = [7] >= [1] = #0() #mult(#neg(x),#0()) = [7] >= [1] = #0() #mult(#neg(x),#neg(y)) = [7] >= [2] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [7] >= [2] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [7] >= [1] = #0() #mult(#pos(x),#neg(y)) = [7] >= [2] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [7] >= [2] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [0] >= [1] y + [0] = y #natadd(#s(x),y) = [1] y + [0] >= [1] y + [1] = #s(#natadd(x,y)) #natmult(#s(x),y) = [2] >= [2] = #natadd(y,#natmult(x,y)) #pred(#0()) = [1] >= [2] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [1] >= [1] x + [2] = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = [2] >= [1] = #0() dyade(l1,l2) = [3] >= [7] = dyade#1(l1,l2) mult(n,l) = [0] >= [0] = mult#1(l,n) mult(x,y) = [0] >= [7] = #mult(x,y) mult#1(dd(x,xs),n) = [0] >= [0] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [0] >= [0] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [0] p(#add) = [1] x1 + [1] x2 + [5] p(#mult) = [2] p(#natadd) = [1] x2 + [7] p(#natmult) = [1] p(#neg) = [1] x1 + [1] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [0] p(#s) = [1] x1 + [4] p(#succ) = [1] x1 + [6] p(dd) = [1] x1 + [1] x2 + [2] p(dyade) = [4] x1 + [4] p(dyade#1) = [4] x1 + [0] p(mult) = [2] p(mult#1) = [7] p(nil) = [1] Following rules are strictly oriented: dyade(l1,l2) = [4] l1 + [4] > [4] l1 + [0] = dyade#1(l1,l2) Following rules are (at-least) weakly oriented: #add(#0(),y) = [1] y + [5] >= [1] y + [0] = y #add(#neg(#s(#0())),y) = [1] y + [10] >= [1] y + [0] = #pred(y) #add(#neg(#s(#s(x))),y) = [1] x + [1] y + [14] >= [1] x + [1] y + [9] = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = [1] y + [9] >= [1] y + [6] = #succ(y) #add(#pos(#s(#s(x))),y) = [1] x + [1] y + [13] >= [1] x + [1] y + [15] = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = [2] >= [0] = #0() #mult(#0(),#neg(y)) = [2] >= [0] = #0() #mult(#0(),#pos(y)) = [2] >= [0] = #0() #mult(#neg(x),#0()) = [2] >= [0] = #0() #mult(#neg(x),#neg(y)) = [2] >= [1] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [2] >= [2] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [2] >= [0] = #0() #mult(#pos(x),#neg(y)) = [2] >= [2] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [2] >= [1] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [7] >= [1] y + [0] = y #natadd(#s(x),y) = [1] y + [7] >= [1] y + [11] = #s(#natadd(x,y)) #natmult(#0(),y) = [1] >= [0] = #0() #natmult(#s(x),y) = [1] >= [8] = #natadd(y,#natmult(x,y)) #pred(#0()) = [0] >= [5] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [5] >= [1] x + [9] = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = [4] >= [0] = #0() #pred(#pos(#s(#s(x)))) = [1] x + [8] >= [1] x + [4] = #pos(#s(x)) #succ(#0()) = [6] >= [4] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [11] >= [0] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [15] >= [1] x + [5] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [10] >= [1] x + [8] = #pos(#s(#s(x))) dyade#1(dd(x,xs),l2) = [4] x + [4] xs + [8] >= [4] xs + [8] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [4] >= [1] = nil() mult(n,l) = [2] >= [7] = mult#1(l,n) mult(x,y) = [2] >= [2] = #mult(x,y) mult#1(dd(x,xs),n) = [7] >= [6] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [7] >= [1] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [0] p(#add) = [4] x1 + [1] x2 + [0] p(#mult) = [1] p(#natadd) = [1] x2 + [0] p(#natmult) = [0] p(#neg) = [1] x1 + [1] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [2] p(#s) = [1] x1 + [0] p(#succ) = [1] x1 + [0] p(dd) = [1] x1 + [1] x2 + [0] p(dyade) = [4] x1 + [1] x2 + [0] p(dyade#1) = [4] x1 + [1] x2 + [0] p(mult) = [0] p(mult#1) = [1] p(nil) = [1] Following rules are strictly oriented: #pred(#0()) = [2] > [1] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [3] > [1] x + [1] = #neg(#s(#s(x))) Following rules are (at-least) weakly oriented: #add(#0(),y) = [1] y + [0] >= [1] y + [0] = y #add(#neg(#s(#0())),y) = [1] y + [4] >= [1] y + [2] = #pred(y) #add(#neg(#s(#s(x))),y) = [4] x + [1] y + [4] >= [4] x + [1] y + [2] = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = [1] y + [0] >= [1] y + [0] = #succ(y) #add(#pos(#s(#s(x))),y) = [4] x + [1] y + [0] >= [4] x + [1] y + [0] = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = [1] >= [0] = #0() #mult(#0(),#neg(y)) = [1] >= [0] = #0() #mult(#0(),#pos(y)) = [1] >= [0] = #0() #mult(#neg(x),#0()) = [1] >= [0] = #0() #mult(#neg(x),#neg(y)) = [1] >= [0] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [1] >= [1] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [1] >= [0] = #0() #mult(#pos(x),#neg(y)) = [1] >= [1] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [1] >= [0] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [0] >= [1] y + [0] = y #natadd(#s(x),y) = [1] y + [0] >= [1] y + [0] = #s(#natadd(x,y)) #natmult(#0(),y) = [0] >= [0] = #0() #natmult(#s(x),y) = [0] >= [0] = #natadd(y,#natmult(x,y)) #pred(#pos(#s(#0()))) = [2] >= [0] = #0() #pred(#pos(#s(#s(x)))) = [1] x + [2] >= [1] x + [0] = #pos(#s(x)) #succ(#0()) = [0] >= [0] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [1] >= [0] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [1] >= [1] x + [1] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [0] >= [1] x + [0] = #pos(#s(#s(x))) dyade(l1,l2) = [4] l1 + [1] l2 + [0] >= [4] l1 + [1] l2 + [0] = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = [1] l2 + [4] x + [4] xs + [0] >= [1] l2 + [4] xs + [0] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [1] l2 + [4] >= [1] = nil() mult(n,l) = [0] >= [1] = mult#1(l,n) mult(x,y) = [0] >= [1] = #mult(x,y) mult#1(dd(x,xs),n) = [1] >= [0] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [1] >= [1] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 5: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [0] p(#add) = [2] x2 + [0] p(#mult) = [0] p(#natadd) = [1] x2 + [4] p(#natmult) = [0] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [0] p(#s) = [1] x1 + [0] p(#succ) = [1] x1 + [0] p(dd) = [1] x1 + [1] x2 + [4] p(dyade) = [2] x1 + [4] p(dyade#1) = [2] x1 + [2] p(mult) = [1] p(mult#1) = [6] p(nil) = [0] Following rules are strictly oriented: mult(x,y) = [1] > [0] = #mult(x,y) Following rules are (at-least) weakly oriented: #add(#0(),y) = [2] y + [0] >= [1] y + [0] = y #add(#neg(#s(#0())),y) = [2] y + [0] >= [1] y + [0] = #pred(y) #add(#neg(#s(#s(x))),y) = [2] y + [0] >= [2] y + [0] = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = [2] y + [0] >= [1] y + [0] = #succ(y) #add(#pos(#s(#s(x))),y) = [2] y + [0] >= [2] y + [0] = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = [0] >= [0] = #0() #mult(#0(),#neg(y)) = [0] >= [0] = #0() #mult(#0(),#pos(y)) = [0] >= [0] = #0() #mult(#neg(x),#0()) = [0] >= [0] = #0() #mult(#neg(x),#neg(y)) = [0] >= [0] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [0] >= [0] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [0] >= [0] = #0() #mult(#pos(x),#neg(y)) = [0] >= [0] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [0] >= [0] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [4] >= [1] y + [0] = y #natadd(#s(x),y) = [1] y + [4] >= [1] y + [4] = #s(#natadd(x,y)) #natmult(#0(),y) = [0] >= [0] = #0() #natmult(#s(x),y) = [0] >= [4] = #natadd(y,#natmult(x,y)) #pred(#0()) = [0] >= [0] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [0] >= [1] x + [0] = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = [0] >= [0] = #0() #pred(#pos(#s(#s(x)))) = [1] x + [0] >= [1] x + [0] = #pos(#s(x)) #succ(#0()) = [0] >= [0] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [0] >= [0] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [0] >= [1] x + [0] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [0] >= [1] x + [0] = #pos(#s(#s(x))) dyade(l1,l2) = [2] l1 + [4] >= [2] l1 + [2] = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = [2] x + [2] xs + [10] >= [2] xs + [9] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [2] >= [0] = nil() mult(n,l) = [1] >= [6] = mult#1(l,n) mult#1(dd(x,xs),n) = [6] >= [6] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [6] >= [0] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 6: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) mult(n,l) -> mult#1(l,n) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [0] p(#add) = [4] x1 + [2] x2 + [1] p(#mult) = [1] p(#natadd) = [1] x2 + [0] p(#natmult) = [0] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [3] p(#s) = [1] x1 + [1] p(#succ) = [1] x1 + [1] p(dd) = [1] x1 + [1] x2 + [4] p(dyade) = [3] x1 + [3] p(dyade#1) = [3] x1 + [2] p(mult) = [1] p(mult#1) = [6] p(nil) = [0] Following rules are strictly oriented: #add(#pos(#s(#s(x))),y) = [4] x + [2] y + [9] > [4] x + [2] y + [6] = #succ(#add(#pos(#s(x)),y)) Following rules are (at-least) weakly oriented: #add(#0(),y) = [2] y + [1] >= [1] y + [0] = y #add(#neg(#s(#0())),y) = [2] y + [5] >= [1] y + [3] = #pred(y) #add(#neg(#s(#s(x))),y) = [4] x + [2] y + [9] >= [4] x + [2] y + [8] = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = [2] y + [5] >= [1] y + [1] = #succ(y) #mult(#0(),#0()) = [1] >= [0] = #0() #mult(#0(),#neg(y)) = [1] >= [0] = #0() #mult(#0(),#pos(y)) = [1] >= [0] = #0() #mult(#neg(x),#0()) = [1] >= [0] = #0() #mult(#neg(x),#neg(y)) = [1] >= [0] = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = [1] >= [0] = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = [1] >= [0] = #0() #mult(#pos(x),#neg(y)) = [1] >= [0] = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = [1] >= [0] = #pos(#natmult(x,y)) #natadd(#0(),y) = [1] y + [0] >= [1] y + [0] = y #natadd(#s(x),y) = [1] y + [0] >= [1] y + [1] = #s(#natadd(x,y)) #natmult(#0(),y) = [0] >= [0] = #0() #natmult(#s(x),y) = [0] >= [0] = #natadd(y,#natmult(x,y)) #pred(#0()) = [3] >= [1] = #neg(#s(#0())) #pred(#neg(#s(x))) = [1] x + [4] >= [1] x + [2] = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = [4] >= [0] = #0() #pred(#pos(#s(#s(x)))) = [1] x + [5] >= [1] x + [1] = #pos(#s(x)) #succ(#0()) = [1] >= [1] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [2] >= [0] = #0() #succ(#neg(#s(#s(x)))) = [1] x + [3] >= [1] x + [1] = #neg(#s(x)) #succ(#pos(#s(x))) = [1] x + [2] >= [1] x + [2] = #pos(#s(#s(x))) dyade(l1,l2) = [3] l1 + [3] >= [3] l1 + [2] = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = [3] x + [3] xs + [14] >= [3] xs + [8] = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = [2] >= [0] = nil() mult(n,l) = [1] >= [6] = mult#1(l,n) mult(x,y) = [1] >= [1] = #mult(x,y) mult#1(dd(x,xs),n) = [6] >= [6] = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = [6] >= [0] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 7: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) mult(n,l) -> mult#1(l,n) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: NaturalPI {shape = Mixed 2, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(mixed(2)): The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1,mult,mult#1} TcT has computed the following interpretation: p(#0) = 0 p(#add) = 2*x2 p(#mult) = 2*x1 + x2 p(#natadd) = 2*x2 p(#natmult) = 0 p(#neg) = x1 p(#pos) = x1 p(#pred) = x1 p(#s) = x1 p(#succ) = x1 p(dd) = 1 + x1 + x2 p(dyade) = 3*x1 + 3*x1*x2 + 2*x1^2 p(dyade#1) = 3*x1 + 3*x1*x2 + 2*x1^2 p(mult) = 1 + 2*x1 + 3*x1*x2 + 3*x2 p(mult#1) = 3*x1 + 3*x1*x2 + x2 p(nil) = 0 Following rules are strictly oriented: mult(n,l) = 1 + 3*l + 3*l*n + 2*n > 3*l + 3*l*n + n = mult#1(l,n) Following rules are (at-least) weakly oriented: #add(#0(),y) = 2*y >= y = y #add(#neg(#s(#0())),y) = 2*y >= y = #pred(y) #add(#neg(#s(#s(x))),y) = 2*y >= 2*y = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = 2*y >= y = #succ(y) #add(#pos(#s(#s(x))),y) = 2*y >= 2*y = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = 0 >= 0 = #0() #mult(#0(),#neg(y)) = y >= 0 = #0() #mult(#0(),#pos(y)) = y >= 0 = #0() #mult(#neg(x),#0()) = 2*x >= 0 = #0() #mult(#neg(x),#neg(y)) = 2*x + y >= 0 = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = 2*x + y >= 0 = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = 2*x >= 0 = #0() #mult(#pos(x),#neg(y)) = 2*x + y >= 0 = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = 2*x + y >= 0 = #pos(#natmult(x,y)) #natadd(#0(),y) = 2*y >= y = y #natadd(#s(x),y) = 2*y >= 2*y = #s(#natadd(x,y)) #natmult(#0(),y) = 0 >= 0 = #0() #natmult(#s(x),y) = 0 >= 0 = #natadd(y,#natmult(x,y)) #pred(#0()) = 0 >= 0 = #neg(#s(#0())) #pred(#neg(#s(x))) = x >= x = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = 0 >= 0 = #0() #pred(#pos(#s(#s(x)))) = x >= x = #pos(#s(x)) #succ(#0()) = 0 >= 0 = #pos(#s(#0())) #succ(#neg(#s(#0()))) = 0 >= 0 = #0() #succ(#neg(#s(#s(x)))) = x >= x = #neg(#s(x)) #succ(#pos(#s(x))) = x >= x = #pos(#s(#s(x))) dyade(l1,l2) = 3*l1 + 3*l1*l2 + 2*l1^2 >= 3*l1 + 3*l1*l2 + 2*l1^2 = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = 5 + 3*l2 + 3*l2*x + 3*l2*xs + 7*x + 4*x*xs + 2*x^2 + 7*xs + 2*xs^2 >= 2 + 3*l2 + 3*l2*x + 3*l2*xs + 2*x + 3*xs + 2*xs^2 = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = 0 >= 0 = nil() mult(x,y) = 1 + 2*x + 3*x*y + 3*y >= 2*x + y = #mult(x,y) mult#1(dd(x,xs),n) = 3 + 4*n + 3*n*x + 3*n*xs + 3*x + 3*xs >= 3 + 4*n + 3*n*x + 3*n*xs + 3*x + 3*xs = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = n >= 0 = nil() * Step 8: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: NaturalPI {shape = Mixed 2, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(mixed(2)): The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1,mult,mult#1} TcT has computed the following interpretation: p(#0) = 0 p(#add) = x1 + x2 p(#mult) = 2*x1 + x1*x2 p(#natadd) = x1 + x2 p(#natmult) = x1 + x1*x2 p(#neg) = x1 p(#pos) = x1 p(#pred) = 1 + x1 p(#s) = 1 + x1 p(#succ) = 1 + x1 p(dd) = 1 + x1 + x2 p(dyade) = 3 + 2*x1 + 3*x1*x2 + 3*x1^2 p(dyade#1) = x1 + 3*x1*x2 + 3*x1^2 p(mult) = 2*x1 + 2*x1*x2 + 2*x2 p(mult#1) = 2*x1 + 2*x1*x2 + 2*x2 p(nil) = 0 Following rules are strictly oriented: #natmult(#s(x),y) = 1 + x + x*y + y > x + x*y + y = #natadd(y,#natmult(x,y)) Following rules are (at-least) weakly oriented: #add(#0(),y) = y >= y = y #add(#neg(#s(#0())),y) = 1 + y >= 1 + y = #pred(y) #add(#neg(#s(#s(x))),y) = 2 + x + y >= 2 + x + y = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = 1 + y >= 1 + y = #succ(y) #add(#pos(#s(#s(x))),y) = 2 + x + y >= 2 + x + y = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = 0 >= 0 = #0() #mult(#0(),#neg(y)) = 0 >= 0 = #0() #mult(#0(),#pos(y)) = 0 >= 0 = #0() #mult(#neg(x),#0()) = 2*x >= 0 = #0() #mult(#neg(x),#neg(y)) = 2*x + x*y >= x + x*y = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = 2*x + x*y >= x + x*y = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = 2*x >= 0 = #0() #mult(#pos(x),#neg(y)) = 2*x + x*y >= x + x*y = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = 2*x + x*y >= x + x*y = #pos(#natmult(x,y)) #natadd(#0(),y) = y >= y = y #natadd(#s(x),y) = 1 + x + y >= 1 + x + y = #s(#natadd(x,y)) #natmult(#0(),y) = 0 >= 0 = #0() #pred(#0()) = 1 >= 1 = #neg(#s(#0())) #pred(#neg(#s(x))) = 2 + x >= 2 + x = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = 2 >= 0 = #0() #pred(#pos(#s(#s(x)))) = 3 + x >= 1 + x = #pos(#s(x)) #succ(#0()) = 1 >= 1 = #pos(#s(#0())) #succ(#neg(#s(#0()))) = 2 >= 0 = #0() #succ(#neg(#s(#s(x)))) = 3 + x >= 1 + x = #neg(#s(x)) #succ(#pos(#s(x))) = 2 + x >= 2 + x = #pos(#s(#s(x))) dyade(l1,l2) = 3 + 2*l1 + 3*l1*l2 + 3*l1^2 >= l1 + 3*l1*l2 + 3*l1^2 = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = 4 + 3*l2 + 3*l2*x + 3*l2*xs + 7*x + 6*x*xs + 3*x^2 + 7*xs + 3*xs^2 >= 4 + 2*l2 + 2*l2*x + 3*l2*xs + 2*x + 2*xs + 3*xs^2 = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = 0 >= 0 = nil() mult(n,l) = 2*l + 2*l*n + 2*n >= 2*l + 2*l*n + 2*n = mult#1(l,n) mult(x,y) = 2*x + 2*x*y + 2*y >= 2*x + x*y = #mult(x,y) mult#1(dd(x,xs),n) = 2 + 4*n + 2*n*x + 2*n*xs + 2*x + 2*xs >= 1 + 4*n + 2*n*x + 2*n*xs + 2*x + 2*xs = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = 2*n >= 0 = nil() * Step 9: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: #natadd(#s(x),y) -> #s(#natadd(x,y)) - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natmult(#0(),y) -> #0() #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: NaturalPI {shape = Mixed 2, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(mixed(2)): The following argument positions are considered usable: uargs(#natadd) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#s) = {1}, uargs(#succ) = {1}, uargs(dd) = {1,2} Following symbols are considered usable: {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1,mult,mult#1} TcT has computed the following interpretation: p(#0) = 0 p(#add) = 1 + x1 + x2 p(#mult) = 2*x1*x2 p(#natadd) = 2*x1 + x2 p(#natmult) = 2*x1*x2 p(#neg) = x1 p(#pos) = x1 p(#pred) = 1 + x1 p(#s) = 1 + x1 p(#succ) = 1 + x1 p(dd) = 2 + x1 + x2 p(dyade) = 2*x1 + 2*x1*x2 + 3*x2^2 p(dyade#1) = 2*x1 + 2*x1*x2 + 3*x2^2 p(mult) = 2*x1*x2 + 3*x2 p(mult#1) = 3*x1 + 2*x1*x2 p(nil) = 0 Following rules are strictly oriented: #natadd(#s(x),y) = 2 + 2*x + y > 1 + 2*x + y = #s(#natadd(x,y)) Following rules are (at-least) weakly oriented: #add(#0(),y) = 1 + y >= y = y #add(#neg(#s(#0())),y) = 2 + y >= 1 + y = #pred(y) #add(#neg(#s(#s(x))),y) = 3 + x + y >= 3 + x + y = #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) = 2 + y >= 1 + y = #succ(y) #add(#pos(#s(#s(x))),y) = 3 + x + y >= 3 + x + y = #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) = 0 >= 0 = #0() #mult(#0(),#neg(y)) = 0 >= 0 = #0() #mult(#0(),#pos(y)) = 0 >= 0 = #0() #mult(#neg(x),#0()) = 0 >= 0 = #0() #mult(#neg(x),#neg(y)) = 2*x*y >= 2*x*y = #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) = 2*x*y >= 2*x*y = #neg(#natmult(x,y)) #mult(#pos(x),#0()) = 0 >= 0 = #0() #mult(#pos(x),#neg(y)) = 2*x*y >= 2*x*y = #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) = 2*x*y >= 2*x*y = #pos(#natmult(x,y)) #natadd(#0(),y) = y >= y = y #natmult(#0(),y) = 0 >= 0 = #0() #natmult(#s(x),y) = 2*x*y + 2*y >= 2*x*y + 2*y = #natadd(y,#natmult(x,y)) #pred(#0()) = 1 >= 1 = #neg(#s(#0())) #pred(#neg(#s(x))) = 2 + x >= 2 + x = #neg(#s(#s(x))) #pred(#pos(#s(#0()))) = 2 >= 0 = #0() #pred(#pos(#s(#s(x)))) = 3 + x >= 1 + x = #pos(#s(x)) #succ(#0()) = 1 >= 1 = #pos(#s(#0())) #succ(#neg(#s(#0()))) = 2 >= 0 = #0() #succ(#neg(#s(#s(x)))) = 3 + x >= 1 + x = #neg(#s(x)) #succ(#pos(#s(x))) = 2 + x >= 2 + x = #pos(#s(#s(x))) dyade(l1,l2) = 2*l1 + 2*l1*l2 + 3*l2^2 >= 2*l1 + 2*l1*l2 + 3*l2^2 = dyade#1(l1,l2) dyade#1(dd(x,xs),l2) = 4 + 4*l2 + 2*l2*x + 2*l2*xs + 3*l2^2 + 2*x + 2*xs >= 2 + 3*l2 + 2*l2*x + 2*l2*xs + 3*l2^2 + 2*xs = dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) = 3*l2^2 >= 0 = nil() mult(n,l) = 3*l + 2*l*n >= 3*l + 2*l*n = mult#1(l,n) mult(x,y) = 2*x*y + 3*y >= 2*x*y = #mult(x,y) mult#1(dd(x,xs),n) = 6 + 4*n + 2*n*x + 2*n*xs + 3*x + 3*xs >= 2 + 2*n*x + 2*n*xs + 3*x + 3*xs = dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) = 0 >= 0 = nil() * Step 10: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: #add(#0(),y) -> y #add(#neg(#s(#0())),y) -> #pred(y) #add(#neg(#s(#s(x))),y) -> #pred(#add(#pos(#s(x)),y)) #add(#pos(#s(#0())),y) -> #succ(y) #add(#pos(#s(#s(x))),y) -> #succ(#add(#pos(#s(x)),y)) #mult(#0(),#0()) -> #0() #mult(#0(),#neg(y)) -> #0() #mult(#0(),#pos(y)) -> #0() #mult(#neg(x),#0()) -> #0() #mult(#neg(x),#neg(y)) -> #pos(#natmult(x,y)) #mult(#neg(x),#pos(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#0()) -> #0() #mult(#pos(x),#neg(y)) -> #neg(#natmult(x,y)) #mult(#pos(x),#pos(y)) -> #pos(#natmult(x,y)) #natadd(#0(),y) -> y #natadd(#s(x),y) -> #s(#natadd(x,y)) #natmult(#0(),y) -> #0() #natmult(#s(x),y) -> #natadd(y,#natmult(x,y)) #pred(#0()) -> #neg(#s(#0())) #pred(#neg(#s(x))) -> #neg(#s(#s(x))) #pred(#pos(#s(#0()))) -> #0() #pred(#pos(#s(#s(x)))) -> #pos(#s(x)) #succ(#0()) -> #pos(#s(#0())) #succ(#neg(#s(#0()))) -> #0() #succ(#neg(#s(#s(x)))) -> #neg(#s(x)) #succ(#pos(#s(x))) -> #pos(#s(#s(x))) dyade(l1,l2) -> dyade#1(l1,l2) dyade#1(dd(x,xs),l2) -> dd(mult(x,l2),dyade(xs,l2)) dyade#1(nil(),l2) -> nil() mult(n,l) -> mult#1(l,n) mult(x,y) -> #mult(x,y) mult#1(dd(x,xs),n) -> dd(mult(n,x),mult(n,xs)) mult#1(nil(),n) -> nil() - Signature: {#add/2,#mult/2,#natadd/2,#natmult/2,#pred/1,#succ/1,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1 ,#pos/1,#s/1,dd/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natadd,#natmult,#pred,#succ,dyade,dyade#1 ,mult,mult#1} and constructors {#0,#neg,#pos,#s,dd,nil} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))