/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). (0) CpxRelTRS (1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 348 ms] (2) CpxRelTRS (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxWeightedTrs (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 664 ms] (14) BOUNDS(1, n^2) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxRelTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 0 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 7647 ms] (22) BEST (23) proven lower bound (24) LowerBoundPropagationProof [FINISHED, 0 ms] (25) BOUNDS(n^1, INF) (26) typed CpxTrs (27) RewriteLemmaProof [LOWER BOUND(ID), 6489 ms] (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 6545 ms] (30) typed CpxTrs (31) RewriteLemmaProof [LOWER BOUND(ID), 575 ms] (32) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: *(@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 The (relative) TRS S consists of the following rules: #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))) Rewrite Strategy: INNERMOST ---------------------------------------- (1) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: *(@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 The (relative) TRS S consists of the following rules: #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))) Rewrite Strategy: INNERMOST ---------------------------------------- (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: *(@x, @y) -> #mult(@x, @y) [1] dyade(@l1, @l2) -> dyade#1(@l1, @l2) [1] dyade#1(::(@x, @xs), @l2) -> ::(mult(@x, @l2), dyade(@xs, @l2)) [1] dyade#1(nil, @l2) -> nil [1] mult(@n, @l) -> mult#1(@l, @n) [1] mult#1(::(@x, @xs), @n) -> ::(*(@n, @x), mult(@n, @xs)) [1] mult#1(nil, @n) -> nil [1] #add(#0, @y) -> @y [0] #add(#neg(#s(#0)), @y) -> #pred(@y) [0] #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) [0] #add(#pos(#s(#0)), @y) -> #succ(@y) [0] #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) [0] #mult(#0, #0) -> #0 [0] #mult(#0, #neg(@y)) -> #0 [0] #mult(#0, #pos(@y)) -> #0 [0] #mult(#neg(@x), #0) -> #0 [0] #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) [0] #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #0) -> #0 [0] #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) [0] #natmult(#0, @y) -> #0 [0] #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) [0] #pred(#0) -> #neg(#s(#0)) [0] #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) [0] #pred(#pos(#s(#0))) -> #0 [0] #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) [0] #succ(#0) -> #pos(#s(#0)) [0] #succ(#neg(#s(#0))) -> #0 [0] #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) [0] #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) Renamed defined symbols to avoid conflicts with arithmetic symbols: * => times ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: times(@x, @y) -> #mult(@x, @y) [1] dyade(@l1, @l2) -> dyade#1(@l1, @l2) [1] dyade#1(::(@x, @xs), @l2) -> ::(mult(@x, @l2), dyade(@xs, @l2)) [1] dyade#1(nil, @l2) -> nil [1] mult(@n, @l) -> mult#1(@l, @n) [1] mult#1(::(@x, @xs), @n) -> ::(times(@n, @x), mult(@n, @xs)) [1] mult#1(nil, @n) -> nil [1] #add(#0, @y) -> @y [0] #add(#neg(#s(#0)), @y) -> #pred(@y) [0] #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) [0] #add(#pos(#s(#0)), @y) -> #succ(@y) [0] #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) [0] #mult(#0, #0) -> #0 [0] #mult(#0, #neg(@y)) -> #0 [0] #mult(#0, #pos(@y)) -> #0 [0] #mult(#neg(@x), #0) -> #0 [0] #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) [0] #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #0) -> #0 [0] #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) [0] #natmult(#0, @y) -> #0 [0] #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) [0] #pred(#0) -> #neg(#s(#0)) [0] #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) [0] #pred(#pos(#s(#0))) -> #0 [0] #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) [0] #succ(#0) -> #pos(#s(#0)) [0] #succ(#neg(#s(#0))) -> #0 [0] #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) [0] #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: times(@x, @y) -> #mult(@x, @y) [1] dyade(@l1, @l2) -> dyade#1(@l1, @l2) [1] dyade#1(::(@x, @xs), @l2) -> ::(mult(@x, @l2), dyade(@xs, @l2)) [1] dyade#1(nil, @l2) -> nil [1] mult(@n, @l) -> mult#1(@l, @n) [1] mult#1(::(@x, @xs), @n) -> ::(times(@n, @x), mult(@n, @xs)) [1] mult#1(nil, @n) -> nil [1] #add(#0, @y) -> @y [0] #add(#neg(#s(#0)), @y) -> #pred(@y) [0] #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) [0] #add(#pos(#s(#0)), @y) -> #succ(@y) [0] #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) [0] #mult(#0, #0) -> #0 [0] #mult(#0, #neg(@y)) -> #0 [0] #mult(#0, #pos(@y)) -> #0 [0] #mult(#neg(@x), #0) -> #0 [0] #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) [0] #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #0) -> #0 [0] #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) [0] #natmult(#0, @y) -> #0 [0] #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) [0] #pred(#0) -> #neg(#s(#0)) [0] #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) [0] #pred(#pos(#s(#0))) -> #0 [0] #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) [0] #succ(#0) -> #pos(#s(#0)) [0] #succ(#neg(#s(#0))) -> #0 [0] #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) [0] #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) [0] The TRS has the following type information: times :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos Rewrite Strategy: INNERMOST ---------------------------------------- (9) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: #add(v0, v1) -> null_#add [0] #mult(v0, v1) -> null_#mult [0] #natmult(v0, v1) -> null_#natmult [0] #pred(v0) -> null_#pred [0] #succ(v0) -> null_#succ [0] dyade#1(v0, v1) -> null_dyade#1 [0] mult#1(v0, v1) -> null_mult#1 [0] And the following fresh constants: null_#add, null_#mult, null_#natmult, null_#pred, null_#succ, null_dyade#1, null_mult#1 ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: times(@x, @y) -> #mult(@x, @y) [1] dyade(@l1, @l2) -> dyade#1(@l1, @l2) [1] dyade#1(::(@x, @xs), @l2) -> ::(mult(@x, @l2), dyade(@xs, @l2)) [1] dyade#1(nil, @l2) -> nil [1] mult(@n, @l) -> mult#1(@l, @n) [1] mult#1(::(@x, @xs), @n) -> ::(times(@n, @x), mult(@n, @xs)) [1] mult#1(nil, @n) -> nil [1] #add(#0, @y) -> @y [0] #add(#neg(#s(#0)), @y) -> #pred(@y) [0] #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) [0] #add(#pos(#s(#0)), @y) -> #succ(@y) [0] #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) [0] #mult(#0, #0) -> #0 [0] #mult(#0, #neg(@y)) -> #0 [0] #mult(#0, #pos(@y)) -> #0 [0] #mult(#neg(@x), #0) -> #0 [0] #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) [0] #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #0) -> #0 [0] #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) [0] #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) [0] #natmult(#0, @y) -> #0 [0] #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) [0] #pred(#0) -> #neg(#s(#0)) [0] #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) [0] #pred(#pos(#s(#0))) -> #0 [0] #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) [0] #succ(#0) -> #pos(#s(#0)) [0] #succ(#neg(#s(#0))) -> #0 [0] #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) [0] #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) [0] #add(v0, v1) -> null_#add [0] #mult(v0, v1) -> null_#mult [0] #natmult(v0, v1) -> null_#natmult [0] #pred(v0) -> null_#pred [0] #succ(v0) -> null_#succ [0] dyade#1(v0, v1) -> null_dyade#1 [0] mult#1(v0, v1) -> null_mult#1 [0] The TRS has the following type information: times :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #mult :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 dyade :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 dyade#1 :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 :: :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 mult :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 nil :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 mult#1 :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #add :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #0 :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #neg :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #s :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #pred :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #pos :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #succ :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 #natmult :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 -> :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_#add :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_#mult :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_#natmult :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_#pred :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_#succ :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_dyade#1 :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 null_mult#1 :: :::nil:#0:#s:#neg:#pos:null_#add:null_#mult:null_#natmult:null_#pred:null_#succ:null_dyade#1:null_mult#1 Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: nil => 1 #0 => 0 null_#add => 0 null_#mult => 0 null_#natmult => 0 null_#pred => 0 null_#succ => 0 null_dyade#1 => 0 null_mult#1 => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: #add(z, z') -{ 0 }-> @y :|: z' = @y, z = 0, @y >= 0 #add(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #add(z, z') -{ 0 }-> #succ(@y) :|: z = 1 + (1 + 0), z' = @y, @y >= 0 #add(z, z') -{ 0 }-> #succ(#add(1 + (1 + @x), @y)) :|: @x >= 0, z' = @y, z = 1 + (1 + (1 + @x)), @y >= 0 #add(z, z') -{ 0 }-> #pred(@y) :|: z = 1 + (1 + 0), z' = @y, @y >= 0 #add(z, z') -{ 0 }-> #pred(#add(1 + (1 + @x), @y)) :|: @x >= 0, z' = @y, z = 1 + (1 + (1 + @x)), @y >= 0 #mult(z, z') -{ 0 }-> 0 :|: z = 0, z' = 0 #mult(z, z') -{ 0 }-> 0 :|: z = 0, z' = 1 + @y, @y >= 0 #mult(z, z') -{ 0 }-> 0 :|: @x >= 0, z = 1 + @x, z' = 0 #mult(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #mult(z, z') -{ 0 }-> 1 + #natmult(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #natmult(z, z') -{ 0 }-> 0 :|: z' = @y, z = 0, @y >= 0 #natmult(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #natmult(z, z') -{ 0 }-> #add(1 + @y, #natmult(@x, @y)) :|: @x >= 0, z = 1 + @x, z' = @y, @y >= 0 #pred(z) -{ 0 }-> 0 :|: z = 1 + (1 + 0) #pred(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 #pred(z) -{ 0 }-> 1 + (1 + @x) :|: @x >= 0, z = 1 + (1 + (1 + @x)) #pred(z) -{ 0 }-> 1 + (1 + 0) :|: z = 0 #pred(z) -{ 0 }-> 1 + (1 + (1 + @x)) :|: @x >= 0, z = 1 + (1 + @x) #succ(z) -{ 0 }-> 0 :|: z = 1 + (1 + 0) #succ(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 #succ(z) -{ 0 }-> 1 + (1 + @x) :|: @x >= 0, z = 1 + (1 + (1 + @x)) #succ(z) -{ 0 }-> 1 + (1 + 0) :|: z = 0 #succ(z) -{ 0 }-> 1 + (1 + (1 + @x)) :|: @x >= 0, z = 1 + (1 + @x) dyade(z, z') -{ 1 }-> dyade#1(@l1, @l2) :|: @l1 >= 0, z' = @l2, @l2 >= 0, z = @l1 dyade#1(z, z') -{ 1 }-> 1 :|: z' = @l2, z = 1, @l2 >= 0 dyade#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 dyade#1(z, z') -{ 1 }-> 1 + mult(@x, @l2) + dyade(@xs, @l2) :|: z' = @l2, @x >= 0, z = 1 + @x + @xs, @l2 >= 0, @xs >= 0 mult(z, z') -{ 1 }-> mult#1(@l, @n) :|: @l >= 0, @n >= 0, z' = @l, z = @n mult#1(z, z') -{ 1 }-> 1 :|: z' = @n, z = 1, @n >= 0 mult#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 mult#1(z, z') -{ 1 }-> 1 + times(@n, @x) + mult(@n, @xs) :|: z' = @n, @x >= 0, z = 1 + @x + @xs, @n >= 0, @xs >= 0 times(z, z') -{ 1 }-> #mult(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V),0,[times(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[dyade(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[mult(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun6(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun4(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun5(V1, Out)],[V1 >= 0]). eq(times(V1, V, Out),1,[fun(V2, V3, Ret)],[Out = Ret,V1 = V2,V2 >= 0,V = V3,V3 >= 0]). eq(dyade(V1, V, Out),1,[fun1(V5, V4, Ret1)],[Out = Ret1,V5 >= 0,V = V4,V4 >= 0,V1 = V5]). eq(fun1(V1, V, Out),1,[mult(V6, V7, Ret01),dyade(V8, V7, Ret11)],[Out = 1 + Ret01 + Ret11,V = V7,V6 >= 0,V1 = 1 + V6 + V8,V7 >= 0,V8 >= 0]). eq(fun1(V1, V, Out),1,[],[Out = 1,V = V9,V1 = 1,V9 >= 0]). eq(mult(V1, V, Out),1,[fun2(V11, V10, Ret2)],[Out = Ret2,V11 >= 0,V10 >= 0,V = V11,V1 = V10]). eq(fun2(V1, V, Out),1,[times(V13, V12, Ret011),mult(V13, V14, Ret12)],[Out = 1 + Ret011 + Ret12,V = V13,V12 >= 0,V1 = 1 + V12 + V14,V13 >= 0,V14 >= 0]). eq(fun2(V1, V, Out),1,[],[Out = 1,V = V15,V1 = 1,V15 >= 0]). eq(fun3(V1, V, Out),0,[],[Out = V16,V = V16,V1 = 0,V16 >= 0]). eq(fun3(V1, V, Out),0,[fun4(V17, Ret3)],[Out = Ret3,V1 = 2,V = V17,V17 >= 0]). eq(fun3(V1, V, Out),0,[fun3(1 + (1 + V18), V19, Ret0),fun4(Ret0, Ret4)],[Out = Ret4,V18 >= 0,V = V19,V1 = 3 + V18,V19 >= 0]). eq(fun3(V1, V, Out),0,[fun5(V20, Ret5)],[Out = Ret5,V1 = 2,V = V20,V20 >= 0]). eq(fun3(V1, V, Out),0,[fun3(1 + (1 + V21), V22, Ret02),fun5(Ret02, Ret6)],[Out = Ret6,V21 >= 0,V = V22,V1 = 3 + V21,V22 >= 0]). eq(fun(V1, V, Out),0,[],[Out = 0,V1 = 0,V = 0]). eq(fun(V1, V, Out),0,[],[Out = 0,V1 = 0,V = 1 + V23,V23 >= 0]). eq(fun(V1, V, Out),0,[],[Out = 0,V24 >= 0,V1 = 1 + V24,V = 0]). eq(fun(V1, V, Out),0,[fun6(V25, V26, Ret13)],[Out = 1 + Ret13,V25 >= 0,V1 = 1 + V25,V = 1 + V26,V26 >= 0]). eq(fun6(V1, V, Out),0,[],[Out = 0,V = V27,V1 = 0,V27 >= 0]). eq(fun6(V1, V, Out),0,[fun6(V28, V29, Ret14),fun3(1 + V29, Ret14, Ret7)],[Out = Ret7,V28 >= 0,V1 = 1 + V28,V = V29,V29 >= 0]). eq(fun4(V1, Out),0,[],[Out = 2,V1 = 0]). eq(fun4(V1, Out),0,[],[Out = 3 + V30,V30 >= 0,V1 = 2 + V30]). eq(fun4(V1, Out),0,[],[Out = 0,V1 = 2]). eq(fun4(V1, Out),0,[],[Out = 2 + V31,V31 >= 0,V1 = 3 + V31]). eq(fun5(V1, Out),0,[],[Out = 2,V1 = 0]). eq(fun5(V1, Out),0,[],[Out = 0,V1 = 2]). eq(fun5(V1, Out),0,[],[Out = 2 + V32,V32 >= 0,V1 = 3 + V32]). eq(fun5(V1, Out),0,[],[Out = 3 + V33,V33 >= 0,V1 = 2 + V33]). eq(fun3(V1, V, Out),0,[],[Out = 0,V35 >= 0,V34 >= 0,V1 = V35,V = V34]). eq(fun(V1, V, Out),0,[],[Out = 0,V37 >= 0,V36 >= 0,V1 = V37,V = V36]). eq(fun6(V1, V, Out),0,[],[Out = 0,V39 >= 0,V38 >= 0,V1 = V39,V = V38]). eq(fun4(V1, Out),0,[],[Out = 0,V40 >= 0,V1 = V40]). eq(fun5(V1, Out),0,[],[Out = 0,V41 >= 0,V1 = V41]). eq(fun1(V1, V, Out),0,[],[Out = 0,V42 >= 0,V43 >= 0,V1 = V42,V = V43]). eq(fun2(V1, V, Out),0,[],[Out = 0,V45 >= 0,V44 >= 0,V1 = V45,V = V44]). input_output_vars(times(V1,V,Out),[V1,V],[Out]). input_output_vars(dyade(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(V1,V,Out),[V1,V],[Out]). input_output_vars(mult(V1,V,Out),[V1,V],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun6(V1,V,Out),[V1,V],[Out]). input_output_vars(fun4(V1,Out),[V1],[Out]). input_output_vars(fun5(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [fun4/2] 1. non_recursive : [fun5/2] 2. recursive [non_tail] : [fun3/3] 3. recursive [non_tail] : [fun6/3] 4. non_recursive : [fun/3] 5. non_recursive : [times/3] 6. recursive : [fun2/3,mult/3] 7. recursive : [dyade/3,fun1/3] 8. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun4/2 1. SCC is partially evaluated into fun5/2 2. SCC is partially evaluated into fun3/3 3. SCC is partially evaluated into fun6/3 4. SCC is partially evaluated into fun/3 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into mult/3 7. SCC is partially evaluated into fun1/3 8. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun4/2 * CE 34 is refined into CE [39] * CE 32 is refined into CE [40] * CE 33 is refined into CE [41] * CE 31 is refined into CE [42] ### Cost equations --> "Loop" of fun4/2 * CEs [39] --> Loop 25 * CEs [40] --> Loop 26 * CEs [41] --> Loop 27 * CEs [42] --> Loop 28 ### Ranking functions of CR fun4(V1,Out) #### Partial ranking functions of CR fun4(V1,Out) ### Specialization of cost equations fun5/2 * CE 37 is refined into CE [43] * CE 38 is refined into CE [44] * CE 36 is refined into CE [45] * CE 35 is refined into CE [46] ### Cost equations --> "Loop" of fun5/2 * CEs [43] --> Loop 29 * CEs [44] --> Loop 30 * CEs [45] --> Loop 31 * CEs [46] --> Loop 32 ### Ranking functions of CR fun5(V1,Out) #### Partial ranking functions of CR fun5(V1,Out) ### Specialization of cost equations fun3/3 * CE 28 is refined into CE [47] * CE 24 is refined into CE [48,49,50,51] * CE 26 is refined into CE [52,53,54,55] * CE 23 is refined into CE [56] * CE 25 is refined into CE [57,58,59,60] * CE 27 is refined into CE [61,62,63,64] ### Cost equations --> "Loop" of fun3/3 * CEs [59,63] --> Loop 33 * CEs [60,64] --> Loop 34 * CEs [57,61] --> Loop 35 * CEs [58,62] --> Loop 36 * CEs [51,55] --> Loop 37 * CEs [50,54] --> Loop 38 * CEs [47,49,53] --> Loop 39 * CEs [48,52] --> Loop 40 * CEs [56] --> Loop 41 ### Ranking functions of CR fun3(V1,V,Out) * RF of phase [33,34,35,36]: [V1-2] #### Partial ranking functions of CR fun3(V1,V,Out) * Partial RF of phase [33,34,35,36]: - RF of loop [33:1,34:1,35:1,36:1]: V1-2 ### Specialization of cost equations fun6/3 * CE 29 is refined into CE [65] * CE 30 is refined into CE [66,67,68,69,70,71,72] ### Cost equations --> "Loop" of fun6/3 * CEs [72] --> Loop 42 * CEs [71] --> Loop 43 * CEs [69] --> Loop 44 * CEs [70] --> Loop 45 * CEs [67] --> Loop 46 * CEs [68] --> Loop 47 * CEs [66] --> Loop 48 * CEs [65] --> Loop 49 ### Ranking functions of CR fun6(V1,V,Out) * RF of phase [42,43,44,45,46,47,48]: [V1] #### Partial ranking functions of CR fun6(V1,V,Out) * Partial RF of phase [42,43,44,45,46,47,48]: - RF of loop [42:1,43:1,44:1,45:1,46:1,47:1,48:1]: V1 ### Specialization of cost equations fun/3 * CE 19 is refined into CE [73,74] * CE 18 is refined into CE [75] * CE 16 is refined into CE [76] * CE 17 is refined into CE [77] ### Cost equations --> "Loop" of fun/3 * CEs [74] --> Loop 50 * CEs [73] --> Loop 51 * CEs [75] --> Loop 52 * CEs [76,77] --> Loop 53 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations mult/3 * CE 22 is refined into CE [78,79,80] * CE 20 is refined into CE [81] * CE 21 is refined into CE [82] ### Cost equations --> "Loop" of mult/3 * CEs [81] --> Loop 54 * CEs [82] --> Loop 55 * CEs [80] --> Loop 56 * CEs [79] --> Loop 57 * CEs [78] --> Loop 58 ### Ranking functions of CR mult(V1,V,Out) * RF of phase [56,57,58]: [V] #### Partial ranking functions of CR mult(V1,V,Out) * Partial RF of phase [56,57,58]: - RF of loop [56:1]: V-1 - RF of loop [57:1]: V/2-1/2 - RF of loop [58:1]: V ### Specialization of cost equations fun1/3 * CE 15 is refined into CE [83] * CE 14 is refined into CE [84] * CE 13 is refined into CE [85,86] ### Cost equations --> "Loop" of fun1/3 * CEs [85] --> Loop 59 * CEs [86] --> Loop 60 * CEs [83] --> Loop 61 * CEs [84] --> Loop 62 ### Ranking functions of CR fun1(V1,V,Out) * RF of phase [59,60]: [V1] #### Partial ranking functions of CR fun1(V1,V,Out) * Partial RF of phase [59,60]: - RF of loop [59:1,60:1]: V1 ### Specialization of cost equations start/2 * CE 1 is refined into CE [87,88] * CE 2 is refined into CE [89] * CE 3 is refined into CE [90] * CE 4 is refined into CE [91,92,93,94,95,96] * CE 5 is refined into CE [97,98,99] * CE 6 is refined into CE [100,101] * CE 7 is refined into CE [102,103] * CE 8 is refined into CE [104,105,106,107,108,109,110,111] * CE 9 is refined into CE [112,113,114] * CE 10 is refined into CE [115,116] * CE 11 is refined into CE [117,118,119,120] * CE 12 is refined into CE [121,122,123,124] ### Cost equations --> "Loop" of start/2 * CEs [108] --> Loop 63 * CEs [106,107] --> Loop 64 * CEs [105] --> Loop 65 * CEs [90] --> Loop 66 * CEs [87,88,89,91,92,93,94,95,96,97,98,99,100,101,102,103,104,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124] --> Loop 67 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of fun4(V1,Out): * Chain [28]: 0 with precondition: [V1=0,Out=2] * Chain [27]: 0 with precondition: [Out=0,V1>=0] * Chain [26]: 0 with precondition: [V1+1=Out,V1>=2] * Chain [25]: 0 with precondition: [V1=Out+1,V1>=3] #### Cost of chains of fun5(V1,Out): * Chain [32]: 0 with precondition: [V1=0,Out=2] * Chain [31]: 0 with precondition: [Out=0,V1>=0] * Chain [30]: 0 with precondition: [V1+1=Out,V1>=2] * Chain [29]: 0 with precondition: [V1=Out+1,V1>=3] #### Cost of chains of fun3(V1,V,Out): * Chain [[33,34,35,36],40]: 0 with precondition: [V=0,V1>=3,Out>=0,V1>=Out] * Chain [[33,34,35,36],39]: 0 with precondition: [V1>=3,V>=0,Out>=0,V1>=Out+1] * Chain [[33,34,35,36],38]: 0 with precondition: [V1>=3,V>=2,Out>=0,V+V1>=Out+1] * Chain [[33,34,35,36],37]: 0 with precondition: [V1>=3,V>=3,Out>=0,V+V1>=Out+3] * Chain [41]: 0 with precondition: [V1=0,V=Out,V>=0] * Chain [40]: 0 with precondition: [V1=2,V=0,Out=2] * Chain [39]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [38]: 0 with precondition: [V1=2,V+1=Out,V>=2] * Chain [37]: 0 with precondition: [V1=2,V=Out+1,V>=3] #### Cost of chains of fun6(V1,V,Out): * Chain [[42,43,44,45,46,47,48],49]: 0 with precondition: [V1>=1,V>=0,Out>=0] * Chain [49]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of fun(V1,V,Out): * Chain [53]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [52]: 0 with precondition: [V=0,Out=0,V1>=1] * Chain [51]: 0 with precondition: [Out=1,V1>=1,V>=1] * Chain [50]: 0 with precondition: [V1>=2,V>=1,Out>=1] #### Cost of chains of mult(V1,V,Out): * Chain [[56,57,58],55]: 6*it(56)+3*it(57)+2 Such that:it(57) =< V/2 aux(7) =< V it(56) =< aux(7) it(57) =< aux(7) with precondition: [V1>=0,V>=2,Out>=2] * Chain [[56,57,58],54]: 6*it(56)+3*it(57)+1 Such that:it(57) =< V/2 aux(8) =< V it(56) =< aux(8) it(57) =< aux(8) with precondition: [V1>=0,V>=1,Out>=1] * Chain [55]: 2 with precondition: [V=1,Out=1,V1>=0] * Chain [54]: 1 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of fun1(V1,V,Out): * Chain [[59,60],62]: 7*it(59)+6*s(15)+12*s(16)+1 Such that:aux(11) =< V aux(15) =< V1 it(59) =< aux(15) aux(12) =< it(59)*aux(11) s(18) =< aux(12)*(1/2) s(15) =< s(18) s(16) =< aux(12) s(15) =< aux(12) with precondition: [V1>=2,V>=0,Out>=2] * Chain [[59,60],61]: 7*it(59)+6*s(15)+12*s(16)+0 Such that:aux(11) =< V aux(16) =< V1 it(59) =< aux(16) aux(12) =< it(59)*aux(11) s(18) =< aux(12)*(1/2) s(15) =< s(18) s(16) =< aux(12) s(15) =< aux(12) with precondition: [V1>=1,V>=0,Out>=1] * Chain [62]: 1 with precondition: [V1=1,Out=1,V>=0] * Chain [61]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of start(V1,V): * Chain [67]: 64*s(35)+24*s(38)+48*s(39)+18*s(42)+6*s(61)+12*s(62)+4 Such that:s(60) =< V/2 aux(19) =< V1 aux(20) =< V1/2 aux(21) =< V s(35) =< aux(19) s(36) =< s(35)*aux(21) s(37) =< s(36)*(1/2) s(38) =< s(37) s(39) =< s(36) s(38) =< s(36) s(42) =< aux(20) s(42) =< aux(19) s(61) =< s(60) s(62) =< aux(21) s(61) =< aux(21) with precondition: [V1>=0] * Chain [66]: 1 with precondition: [V1=1,V>=0] * Chain [65]: 0 with precondition: [V1=2,V=0] * Chain [64]: 0 with precondition: [V1=2,V>=2] * Chain [63]: 0 with precondition: [V=0,V1>=3] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [67] with precondition: [V1>=0] - Upper bound: 64*V1+4+60*V1*nat(V)+nat(V)*12+9*V1+nat(V/2)*6 - Complexity: n^2 * Chain [66] with precondition: [V1=1,V>=0] - Upper bound: 1 - Complexity: constant * Chain [65] with precondition: [V1=2,V=0] - Upper bound: 0 - Complexity: constant * Chain [64] with precondition: [V1=2,V>=2] - Upper bound: 0 - Complexity: constant * Chain [63] with precondition: [V=0,V1>=3] - Upper bound: 0 - Complexity: constant ### Maximum cost of start(V1,V): max([1,64*V1+4+60*V1*nat(V)+nat(V)*12+9*V1+nat(V/2)*6]) Asymptotic class: n^2 * Total analysis performed in 565 ms. ---------------------------------------- (14) BOUNDS(1, n^2) ---------------------------------------- (15) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (16) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: *'(@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 The (relative) TRS S consists of the following rules: #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))) Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: dyade, dyade#1, mult, mult#1, #add, #natmult They will be analysed ascendingly in the following order: dyade = dyade#1 mult < dyade#1 mult = mult#1 #add < #natmult ---------------------------------------- (20) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: #add, dyade, dyade#1, mult, mult#1, #natmult They will be analysed ascendingly in the following order: dyade = dyade#1 mult < dyade#1 mult = mult#1 #add < #natmult ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n112_3) Induction Base: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, 0)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) Induction Step: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, +(n112_3, 1))), gen_:::nil:#0:#s:#neg:#pos2_3(b)) ->_R^Omega(1) ::(*'(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)))) ->_R^Omega(1) ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)))) ->_R^Omega(1) ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_IH ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), *3_3) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Complex Obligation (BEST) ---------------------------------------- (23) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: mult#1, dyade, dyade#1, mult They will be analysed ascendingly in the following order: dyade = dyade#1 mult < dyade#1 mult = mult#1 ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Lemmas: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n112_3) Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: mult, dyade, dyade#1 They will be analysed ascendingly in the following order: dyade = dyade#1 mult < dyade#1 mult = mult#1 ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3)) -> *3_3, rt in Omega(n1780965_3) Induction Base: mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(0)) Induction Step: mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(+(n1780965_3, 1))) ->_R^Omega(1) mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(n1780965_3, 1)), gen_:::nil:#0:#s:#neg:#pos2_3(a)) ->_R^Omega(1) ::(*'(gen_:::nil:#0:#s:#neg:#pos2_3(a), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3))) ->_R^Omega(1) ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3))) ->_IH ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), nil), *3_3) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (28) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Lemmas: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n112_3) mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3)) -> *3_3, rt in Omega(n1780965_3) Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: mult#1, dyade, dyade#1 They will be analysed ascendingly in the following order: dyade = dyade#1 mult < dyade#1 mult = mult#1 ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n3508152_3) Induction Base: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, 0)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) Induction Step: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, +(n3508152_3, 1))), gen_:::nil:#0:#s:#neg:#pos2_3(b)) ->_R^Omega(1) ::(*'(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)))) ->_R^Omega(1) ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)))) ->_R^Omega(1) ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_IH ::(#mult(gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), *3_3) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (30) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Lemmas: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n3508152_3) mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3)) -> *3_3, rt in Omega(n1780965_3) Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: dyade#1, dyade They will be analysed ascendingly in the following order: dyade = dyade#1 ---------------------------------------- (31) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: dyade#1(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), rt in Omega(1 + n5297365_3) Induction Base: dyade#1(gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(0)) ->_R^Omega(1) nil Induction Step: dyade#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(n5297365_3, 1)), gen_:::nil:#0:#s:#neg:#pos2_3(0)) ->_R^Omega(1) ::(mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(0)), dyade(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0))) ->_R^Omega(1) ::(mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(0), nil), dyade(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0))) ->_R^Omega(1) ::(nil, dyade(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0))) ->_R^Omega(1) ::(nil, dyade#1(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0))) ->_IH ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c5297366_3)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (32) Obligation: Innermost TRS: Rules: *'(@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 #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))) Types: *' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos dyade#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos :: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos nil :: :::nil:#0:#s:#neg:#pos mult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #0 :: :::nil:#0:#s:#neg:#pos #neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos #natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos Lemmas: mult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n3508152_3)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> *3_3, rt in Omega(n3508152_3) mult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n1780965_3)) -> *3_3, rt in Omega(n1780965_3) dyade#1(gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> gen_:::nil:#0:#s:#neg:#pos2_3(n5297365_3), rt in Omega(1 + n5297365_3) Generator Equations: gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x)) The following defined symbols remain to be analysed: dyade They will be analysed ascendingly in the following order: dyade = dyade#1