WORST_CASE(?,O(n^2)) * Step 1: NaturalMI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: *(@x,@y) -> #mult(@x,@y) dyade(@l1,@l2) -> dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) -> nil() mult(@n,@l) -> mult#1(@l,@n) mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - 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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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))) - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,nil} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(#add) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#succ) = {1}, uargs(::) = {1,2} Following symbols are considered usable: {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult,mult#1} TcT has computed the following interpretation: p(#0) = [0] p(#add) = [1] x2 + [0] p(#mult) = [0] p(#natmult) = [0] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [0] p(#s) = [0] p(#succ) = [1] x1 + [0] p(*) = [0] p(::) = [1] x1 + [1] x2 + [0] p(dyade) = [1] p(dyade#1) = [1] p(mult) = [0] p(mult#1) = [0] p(nil) = [0] Following rules are strictly oriented: dyade#1(nil(),@l2) = [1] > [0] = nil() Following rules are (at-least) weakly oriented: #add(#0(),@y) = [1] @y + [0] >= [1] @y + [0] = @y #add(#neg(#s(#0())),@y) = [1] @y + [0] >= [1] @y + [0] = #pred(@y) #add(#neg(#s(#s(@x))),@y) = [1] @y + [0] >= [1] @y + [0] = #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) = [1] @y + [0] >= [1] @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)) #natmult(#0(),@y) = [0] >= [0] = #0() #natmult(#s(@x),@y) = [0] >= [0] = #add(#pos(@y),#natmult(@x,@y)) #pred(#0()) = [0] >= [0] = #neg(#s(#0())) #pred(#neg(#s(@x))) = [0] >= [0] = #neg(#s(#s(@x))) #pred(#pos(#s(#0()))) = [0] >= [0] = #0() #pred(#pos(#s(#s(@x)))) = [0] >= [0] = #pos(#s(@x)) #succ(#0()) = [0] >= [0] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [0] >= [0] = #0() #succ(#neg(#s(#s(@x)))) = [0] >= [0] = #neg(#s(@x)) #succ(#pos(#s(@x))) = [0] >= [0] = #pos(#s(#s(@x))) *(@x,@y) = [0] >= [0] = #mult(@x,@y) dyade(@l1,@l2) = [1] >= [1] = dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) = [1] >= [1] = ::(mult(@x,@l2),dyade(@xs,@l2)) mult(@n,@l) = [0] >= [0] = mult#1(@l,@n) mult#1(::(@x,@xs),@n) = [0] >= [0] = ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) = [0] >= [0] = nil() * Step 2: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: *(@x,@y) -> #mult(@x,@y) dyade(@l1,@l2) -> dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) mult(@n,@l) -> mult#1(@l,@n) mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - 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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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#1(nil(),@l2) -> nil() - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,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(#add) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#succ) = {1}, uargs(::) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [5] p(#add) = [1] x2 + [0] p(#mult) = [5] p(#natmult) = [5] 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(*) = [0] p(::) = [1] x1 + [1] x2 + [0] p(dyade) = [0] p(dyade#1) = [0] p(mult) = [0] p(mult#1) = [3] p(nil) = [0] Following rules are strictly oriented: mult#1(::(@x,@xs),@n) = [3] > [0] = ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) = [3] > [0] = nil() Following rules are (at-least) weakly oriented: #add(#0(),@y) = [1] @y + [0] >= [1] @y + [0] = @y #add(#neg(#s(#0())),@y) = [1] @y + [0] >= [1] @y + [0] = #pred(@y) #add(#neg(#s(#s(@x))),@y) = [1] @y + [0] >= [1] @y + [0] = #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) = [1] @y + [0] >= [1] @y + [0] = #succ(#add(#pos(#s(@x)),@y)) #mult(#0(),#0()) = [5] >= [5] = #0() #mult(#0(),#neg(@y)) = [5] >= [5] = #0() #mult(#0(),#pos(@y)) = [5] >= [5] = #0() #mult(#neg(@x),#0()) = [5] >= [5] = #0() #mult(#neg(@x),#neg(@y)) = [5] >= [5] = #pos(#natmult(@x,@y)) #mult(#neg(@x),#pos(@y)) = [5] >= [5] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#0()) = [5] >= [5] = #0() #mult(#pos(@x),#neg(@y)) = [5] >= [5] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#pos(@y)) = [5] >= [5] = #pos(#natmult(@x,@y)) #natmult(#0(),@y) = [5] >= [5] = #0() #natmult(#s(@x),@y) = [5] >= [5] = #add(#pos(@y),#natmult(@x,@y)) #pred(#0()) = [5] >= [5] = #neg(#s(#0())) #pred(#neg(#s(@x))) = [1] @x + [0] >= [1] @x + [0] = #neg(#s(#s(@x))) #pred(#pos(#s(#0()))) = [5] >= [5] = #0() #pred(#pos(#s(#s(@x)))) = [1] @x + [0] >= [1] @x + [0] = #pos(#s(@x)) #succ(#0()) = [5] >= [5] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [5] >= [5] = #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))) *(@x,@y) = [0] >= [5] = #mult(@x,@y) dyade(@l1,@l2) = [0] >= [0] = dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) = [0] >= [0] = ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) = [0] >= [0] = nil() mult(@n,@l) = [0] >= [3] = mult#1(@l,@n) 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: *(@x,@y) -> #mult(@x,@y) dyade(@l1,@l2) -> dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) 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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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#1(nil(),@l2) -> nil() mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,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(#add) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#succ) = {1}, uargs(::) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [4] p(#add) = [1] x2 + [0] p(#mult) = [4] p(#natmult) = [4] p(#neg) = [1] x1 + [0] p(#pos) = [1] x1 + [0] p(#pred) = [1] x1 + [0] p(#s) = [4] p(#succ) = [1] x1 + [0] p(*) = [1] p(::) = [1] x1 + [1] x2 + [1] p(dyade) = [7] x1 + [5] p(dyade#1) = [7] x1 + [0] p(mult) = [0] p(mult#1) = [2] p(nil) = [2] Following rules are strictly oriented: dyade(@l1,@l2) = [7] @l1 + [5] > [7] @l1 + [0] = dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) = [7] @x + [7] @xs + [7] > [7] @xs + [6] = ::(mult(@x,@l2),dyade(@xs,@l2)) Following rules are (at-least) weakly oriented: #add(#0(),@y) = [1] @y + [0] >= [1] @y + [0] = @y #add(#neg(#s(#0())),@y) = [1] @y + [0] >= [1] @y + [0] = #pred(@y) #add(#neg(#s(#s(@x))),@y) = [1] @y + [0] >= [1] @y + [0] = #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) = [1] @y + [0] >= [1] @y + [0] = #succ(#add(#pos(#s(@x)),@y)) #mult(#0(),#0()) = [4] >= [4] = #0() #mult(#0(),#neg(@y)) = [4] >= [4] = #0() #mult(#0(),#pos(@y)) = [4] >= [4] = #0() #mult(#neg(@x),#0()) = [4] >= [4] = #0() #mult(#neg(@x),#neg(@y)) = [4] >= [4] = #pos(#natmult(@x,@y)) #mult(#neg(@x),#pos(@y)) = [4] >= [4] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#0()) = [4] >= [4] = #0() #mult(#pos(@x),#neg(@y)) = [4] >= [4] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#pos(@y)) = [4] >= [4] = #pos(#natmult(@x,@y)) #natmult(#0(),@y) = [4] >= [4] = #0() #natmult(#s(@x),@y) = [4] >= [4] = #add(#pos(@y),#natmult(@x,@y)) #pred(#0()) = [4] >= [4] = #neg(#s(#0())) #pred(#neg(#s(@x))) = [4] >= [4] = #neg(#s(#s(@x))) #pred(#pos(#s(#0()))) = [4] >= [4] = #0() #pred(#pos(#s(#s(@x)))) = [4] >= [4] = #pos(#s(@x)) #succ(#0()) = [4] >= [4] = #pos(#s(#0())) #succ(#neg(#s(#0()))) = [4] >= [4] = #0() #succ(#neg(#s(#s(@x)))) = [4] >= [4] = #neg(#s(@x)) #succ(#pos(#s(@x))) = [4] >= [4] = #pos(#s(#s(@x))) *(@x,@y) = [1] >= [4] = #mult(@x,@y) dyade#1(nil(),@l2) = [14] >= [2] = nil() mult(@n,@l) = [0] >= [2] = mult#1(@l,@n) mult#1(::(@x,@xs),@n) = [2] >= [2] = ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) = [2] >= [2] = 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: *(@x,@y) -> #mult(@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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) -> nil() mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,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(#add) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#succ) = {1}, uargs(::) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(#0) = [1] p(#add) = [1] x2 + [0] p(#mult) = [1] p(#natmult) = [1] 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(*) = [4] p(::) = [1] x1 + [1] x2 + [0] p(dyade) = [1] x1 + [4] p(dyade#1) = [1] x1 + [4] p(mult) = [0] p(mult#1) = [4] p(nil) = [4] Following rules are strictly oriented: *(@x,@y) = [4] > [1] = #mult(@x,@y) Following rules are (at-least) weakly oriented: #add(#0(),@y) = [1] @y + [0] >= [1] @y + [0] = @y #add(#neg(#s(#0())),@y) = [1] @y + [0] >= [1] @y + [0] = #pred(@y) #add(#neg(#s(#s(@x))),@y) = [1] @y + [0] >= [1] @y + [0] = #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) = [1] @y + [0] >= [1] @y + [0] = #succ(#add(#pos(#s(@x)),@y)) #mult(#0(),#0()) = [1] >= [1] = #0() #mult(#0(),#neg(@y)) = [1] >= [1] = #0() #mult(#0(),#pos(@y)) = [1] >= [1] = #0() #mult(#neg(@x),#0()) = [1] >= [1] = #0() #mult(#neg(@x),#neg(@y)) = [1] >= [1] = #pos(#natmult(@x,@y)) #mult(#neg(@x),#pos(@y)) = [1] >= [1] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#0()) = [1] >= [1] = #0() #mult(#pos(@x),#neg(@y)) = [1] >= [1] = #neg(#natmult(@x,@y)) #mult(#pos(@x),#pos(@y)) = [1] >= [1] = #pos(#natmult(@x,@y)) #natmult(#0(),@y) = [1] >= [1] = #0() #natmult(#s(@x),@y) = [1] >= [1] = #add(#pos(@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(#0()))) = [1] >= [1] = #0() #pred(#pos(#s(#s(@x)))) = [1] @x + [0] >= [1] @x + [0] = #pos(#s(@x)) #succ(#0()) = [1] >= [1] = #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 + [0] >= [1] @x + [0] = #pos(#s(#s(@x))) dyade(@l1,@l2) = [1] @l1 + [4] >= [1] @l1 + [4] = dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) = [1] @x + [1] @xs + [4] >= [1] @xs + [4] = ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) = [8] >= [4] = nil() mult(@n,@l) = [0] >= [4] = mult#1(@l,@n) mult#1(::(@x,@xs),@n) = [4] >= [4] = ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) = [4] >= [4] = nil() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 5: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: 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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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))) *(@x,@y) -> #mult(@x,@y) dyade(@l1,@l2) -> dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) -> nil() mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,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(#add) = {2}, uargs(#neg) = {1}, uargs(#pos) = {1}, uargs(#pred) = {1}, uargs(#succ) = {1}, uargs(::) = {1,2} Following symbols are considered usable: {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult,mult#1} TcT has computed the following interpretation: p(#0) = 0 p(#add) = x2 p(#mult) = 2*x1*x2 p(#natmult) = 2*x1*x2 p(#neg) = x1 p(#pos) = x1 p(#pred) = x1 p(#s) = x1 p(#succ) = x1 p(*) = 2*x1*x2 p(::) = 2 + x1 + x2 p(dyade) = 2 + 2*x1 + 2*x1*x2 + x1^2 p(dyade#1) = x1 + 2*x1*x2 + x1^2 p(mult) = 2 + 2*x1 + 2*x1*x2 + 2*x2 p(mult#1) = 2*x1 + 2*x1*x2 + x2 p(nil) = 0 Following rules are strictly oriented: mult(@n,@l) = 2 + 2*@l + 2*@l*@n + 2*@n > 2*@l + 2*@l*@n + @n = mult#1(@l,@n) Following rules are (at-least) weakly oriented: #add(#0(),@y) = @y >= @y = @y #add(#neg(#s(#0())),@y) = @y >= @y = #pred(@y) #add(#neg(#s(#s(@x))),@y) = @y >= @y = #pred(#add(#pos(#s(@x)),@y)) #add(#pos(#s(#0())),@y) = @y >= @y = #succ(@y) #add(#pos(#s(#s(@x))),@y) = @y >= @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)) #natmult(#0(),@y) = 0 >= 0 = #0() #natmult(#s(@x),@y) = 2*@x*@y >= 2*@x*@y = #add(#pos(@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))) *(@x,@y) = 2*@x*@y >= 2*@x*@y = #mult(@x,@y) dyade(@l1,@l2) = 2 + 2*@l1 + 2*@l1*@l2 + @l1^2 >= @l1 + 2*@l1*@l2 + @l1^2 = dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) = 6 + 4*@l2 + 2*@l2*@x + 2*@l2*@xs + 5*@x + 2*@x*@xs + @x^2 + 5*@xs + @xs^2 >= 6 + 2*@l2 + 2*@l2*@x + 2*@l2*@xs + 2*@x + 2*@xs + @xs^2 = ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) = 0 >= 0 = nil() mult#1(::(@x,@xs),@n) = 4 + 5*@n + 2*@n*@x + 2*@n*@xs + 2*@x + 2*@xs >= 4 + 2*@n + 2*@n*@x + 2*@n*@xs + 2*@xs = ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) = @n >= 0 = nil() * Step 6: 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)) #natmult(#0(),@y) -> #0() #natmult(#s(@x),@y) -> #add(#pos(@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))) *(@x,@y) -> #mult(@x,@y) dyade(@l1,@l2) -> dyade#1(@l1,@l2) dyade#1(::(@x,@xs),@l2) -> ::(mult(@x,@l2),dyade(@xs,@l2)) dyade#1(nil(),@l2) -> nil() mult(@n,@l) -> mult#1(@l,@n) mult#1(::(@x,@xs),@n) -> ::(*(@n,@x),mult(@n,@xs)) mult#1(nil(),@n) -> nil() - Signature: {#add/2,#mult/2,#natmult/2,#pred/1,#succ/1,*/2,dyade/2,dyade#1/2,mult/2,mult#1/2} / {#0/0,#neg/1,#pos/1,#s/1 ,::/2,nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {#add,#mult,#natmult,#pred,#succ,*,dyade,dyade#1,mult ,mult#1} and constructors {#0,#neg,#pos,#s,::,nil} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))