/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), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). (0) CpxRelTRS (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 356 ms] (2) CpxRelTRS (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxRelTRS (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (6) typed CpxTrs (7) OrderProof [LOWER BOUND(ID), 0 ms] (8) typed CpxTrs (9) RewriteLemmaProof [LOWER BOUND(ID), 17.3 s] (10) BEST (11) proven lower bound (12) LowerBoundPropagationProof [FINISHED, 0 ms] (13) BOUNDS(n^1, INF) (14) typed CpxTrs (15) RewriteLemmaProof [LOWER BOUND(ID), 16.3 s] (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 16.5 s] (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 2247 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 17 ms] (22) typed CpxTrs ---------------------------------------- (0) 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) +(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved termination of relative rules ---------------------------------------- (2) 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) +(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (4) 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) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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 ---------------------------------------- (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (6) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos ---------------------------------------- (7) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: #add, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, computeLine#1, lineMult, lineMult#1, matrixMult#1, #natmult They will be analysed ascendingly in the following order: #add < #natmult appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 lineMult < computeLine#1 lineMult = lineMult#1 ---------------------------------------- (8) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: #add, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, computeLine#1, lineMult, lineMult#1, matrixMult#1, #natmult They will be analysed ascendingly in the following order: #add < #natmult appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 lineMult < computeLine#1 lineMult = lineMult#1 ---------------------------------------- (9) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n112_6) Induction Base: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, 0)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) Induction Step: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, +(n112_6, 1))), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) ->_R^Omega(1) lineMult#2(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6))) ->_R^Omega(1) ::(*'(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), nil)) ->_R^Omega(1) ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), nil)) ->_R^Omega(1) ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c))) ->_IH ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), *3_6) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (10) Complex Obligation (BEST) ---------------------------------------- (11) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: lineMult#1, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, computeLine#1, lineMult, matrixMult#1 They will be analysed ascendingly in the following order: appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 lineMult < computeLine#1 lineMult = lineMult#1 ---------------------------------------- (12) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (13) BOUNDS(n^1, INF) ---------------------------------------- (14) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Lemmas: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n112_6) Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: lineMult, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, computeLine#1, matrixMult#1 They will be analysed ascendingly in the following order: appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 lineMult < computeLine#1 lineMult = lineMult#1 ---------------------------------------- (15) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) -> *3_6, rt in Omega(n4470374_6) Induction Base: lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) Induction Step: lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n4470374_6, 1)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) ->_R^Omega(1) lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n4470374_6, 1)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a)) ->_R^Omega(1) lineMult#2(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6)) ->_R^Omega(1) ::(*'(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), nil)) ->_R^Omega(1) ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), nil)) ->_IH ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a)), *3_6) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (16) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Lemmas: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n112_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n112_6) lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) -> *3_6, rt in Omega(n4470374_6) Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: lineMult#1, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, computeLine#1, matrixMult#1 They will be analysed ascendingly in the following order: appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 lineMult < computeLine#1 lineMult = lineMult#1 ---------------------------------------- (17) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n8946642_6) Induction Base: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, 0)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) Induction Step: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, +(n8946642_6, 1))), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) ->_R^Omega(1) lineMult#2(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6))) ->_R^Omega(1) ::(*'(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), nil)) ->_R^Omega(1) ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), nil)) ->_R^Omega(1) ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c))) ->_IH ::(#mult(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)), *3_6) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (18) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Lemmas: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n8946642_6) lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) -> *3_6, rt in Omega(n4470374_6) Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: computeLine#1, appendreverse, appendreverse#1, bftMult', bftMult'#1, matrixMult, computeLine, matrixMult#1 They will be analysed ascendingly in the following order: appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 computeLine = computeLine#1 computeLine < matrixMult#1 ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) -> gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), rt in Omega(1 + n13540387_6) Induction Base: matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) ->_R^Omega(1) nil Induction Step: matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n13540387_6, 1)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) ->_R^Omega(1) ::(computeLine(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b), nil), matrixMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_R^Omega(1) ::(computeLine#1(nil, nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)), matrixMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_R^Omega(1) ::(nil, matrixMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_R^Omega(1) ::(nil, matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_IH ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c13540388_6)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (20) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Lemmas: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n8946642_6) lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) -> *3_6, rt in Omega(n4470374_6) matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) -> gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), rt in Omega(1 + n13540387_6) Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: matrixMult, appendreverse, appendreverse#1, bftMult', bftMult'#1 They will be analysed ascendingly in the following order: appendreverse = appendreverse#1 bftMult' = bftMult'#1 matrixMult < bftMult'#1 matrixMult = matrixMult#1 ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: appendreverse#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13543083_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) -> gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n13543083_6, b)), rt in Omega(1 + n13543083_6) Induction Base: appendreverse#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) ->_R^Omega(1) gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b) Induction Step: appendreverse#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n13543083_6, 1)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) ->_R^Omega(1) appendreverse(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13543083_6), ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_R^Omega(1) appendreverse#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13543083_6), ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b))) ->_IH gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(+(b, 1), c13543084_6)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Obligation: Innermost TRS: Rules: *'(@x, @y) -> #mult(@x, @y) +'(@x, @y) -> #add(@x, @y) appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) appendreverse#1(nil, @sofar) -> @sofar bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) bftMult'#3(nil, @acc, @queue) -> @acc bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) computeLine#1(nil, @acc, @m) -> @acc computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) computeLine#2(nil, @acc, @x, @xs) -> nil dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) enqueue(@t, @queue) -> enqueue#1(@queue, @t) enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) lineMult#1(nil, @l2, @n) -> nil lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+'(*'(@x, @n), @y), lineMult(@n, @xs, @ys)) lineMult#2(nil, @n, @x, @xs) -> ::(*'(@x, @n), lineMult(@n, @xs, nil)) matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) matrixMult#1(nil, @m2) -> nil reverse(@xs) -> appendreverse(@xs, 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:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #mult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos +' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #add :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos appendreverse#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos :: :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos nil :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult' :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos tuple#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#3 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#4 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos leaf :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos node :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos bftMult'#5 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos computeLine#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos dequeue#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos reverse :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos enqueue#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos lineMult#2 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos matrixMult#1 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #0 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #neg :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #s :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pred :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #pos :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #succ :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos #natmult :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos hole_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos1_6 :: :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6 :: Nat -> :::nil:tuple#2:leaf:node:#0:#s:#neg:#pos Lemmas: lineMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(1, n8946642_6)), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(c)) -> *3_6, rt in Omega(n8946642_6) lineMult(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(a), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n4470374_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0)) -> *3_6, rt in Omega(n4470374_6) matrixMult#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) -> gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13540387_6), rt in Omega(1 + n13540387_6) appendreverse#1(gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(n13543083_6), gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(b)) -> gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(n13543083_6, b)), rt in Omega(1 + n13543083_6) Generator Equations: gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(0) <=> nil gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(+(x, 1)) <=> ::(nil, gen_:::nil:tuple#2:leaf:node:#0:#s:#neg:#pos2_6(x)) The following defined symbols remain to be analysed: appendreverse They will be analysed ascendingly in the following order: appendreverse = appendreverse#1