/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox/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, n^2).

(0) CpxRelTRS
(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 364 ms]
(2) CpxRelTRS
(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(4) CdtProblem
    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CdtProblem
    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 174 ms]
    (12) CdtProblem
    (13) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 471 ms]
    (16) CdtProblem
    (17) CdtKnowledgeProof [FINISHED, 0 ms]
    (18) BOUNDS(1, 1)
(19) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(20) CpxRelTRS
    (21) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (22) typed CpxTrs
    (23) OrderProof [LOWER BOUND(ID), 0 ms]
    (24) typed CpxTrs
    (25) RewriteLemmaProof [LOWER BOUND(ID), 20.0 s]
    (26) BEST
        (27) proven lower bound
            (28) LowerBoundPropagationProof [FINISHED, 0 ms]
            (29) BOUNDS(n^1, INF)
        (30) typed CpxTrs
            (31) RewriteLemmaProof [LOWER BOUND(ID), 17.4 s]
            (32) typed CpxTrs
            (33) RewriteLemmaProof [LOWER BOUND(ID), 18.9 s]
            (34) typed CpxTrs
            (35) RewriteLemmaProof [LOWER BOUND(ID), 1895 ms]
            (36) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   *(@x, @y) -> #mult(@x, @y)
   +(@x, @y) -> #add(@x, @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
   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

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, n^2).


The TRS R consists of the following rules:

   *(@x, @y) -> #mult(@x, @y)
   +(@x, @y) -> #add(@x, @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
   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

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) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   *(z0, z1) -> #mult(z0, z1)
   +(z0, z1) -> #add(z0, z1)
   computeLine(z0, z1, z2) -> computeLine#1(z0, z2, z1)
   computeLine#1(::(z0, z1), z2, z3) -> computeLine#2(z3, z2, z0, z1)
   computeLine#1(nil, z0, z1) -> z0
   computeLine#2(::(z0, z1), z2, z3, z4) -> computeLine(z4, z1, lineMult(z3, z0, z2))
   computeLine#2(nil, z0, z1, z2) -> nil
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   matrixMult(z0, z1) -> matrixMult#1(z0, z1)
   matrixMult#1(::(z0, z1), z2) -> ::(computeLine(z0, z2, nil), matrixMult(z1, z2))
   matrixMult#1(nil, z0) -> nil
Tuples:
   #ADD(#0, z0) -> c
   #ADD(#neg(#s(#0)), z0) -> c1(#PRED(z0))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#PRED(#add(#pos(#s(z0)), z1)), #ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#0)), z0) -> c3(#SUCC(z0))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#SUCC(#add(#pos(#s(z0)), z1)), #ADD(#pos(#s(z0)), z1))
   #MULT(#0, #0) -> c5
   #MULT(#0, #neg(z0)) -> c6
   #MULT(#0, #pos(z0)) -> c7
   #MULT(#neg(z0), #0) -> c8
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #0) -> c11
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#0, z0) -> c14
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   #PRED(#0) -> c16
   #PRED(#neg(#s(z0))) -> c17
   #PRED(#pos(#s(#0))) -> c18
   #PRED(#pos(#s(#s(z0)))) -> c19
   #SUCC(#0) -> c20
   #SUCC(#neg(#s(#0))) -> c21
   #SUCC(#neg(#s(#s(z0)))) -> c22
   #SUCC(#pos(#s(z0))) -> c23
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#1(nil, z0, z1) -> c28
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   COMPUTELINE#2(nil, z0, z1, z2) -> c30
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#1(nil, z0, z1) -> c33
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   MATRIXMULT#1(nil, z0) -> c38
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#1(nil, z0, z1) -> c28
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   COMPUTELINE#2(nil, z0, z1, z2) -> c30
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#1(nil, z0, z1) -> c33
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   MATRIXMULT#1(nil, z0) -> c38
K tuples:none
Defined Rule Symbols:   *_2, +_2, computeLine_3, computeLine#1_3, computeLine#2_4, lineMult_3, lineMult#1_3, lineMult#2_4, matrixMult_2, matrixMult#1_2, #add_2, #mult_2, #natmult_2, #pred_1, #succ_1

Defined Pair Symbols:   #ADD_2, #MULT_2, #NATMULT_2, #PRED_1, #SUCC_1, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2

Compound Symbols:   c, c1_1, c2_2, c3_1, c4_2, c5, c6, c7, c8, c9_1, c10_1, c11, c12_1, c13_1, c14, c15_2, c16, c17, c18, c19, c20, c21, c22, c23, c24_1, c25_1, c26_1, c27_1, c28, c29_2, c30, c31_1, c32_1, c33, c34_3, c35_2, c36_1, c37_2, c38


----------------------------------------

(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 21 trailing nodes:
   #PRED(#pos(#s(#0))) -> c18
   LINEMULT#1(nil, z0, z1) -> c33
   #MULT(#0, #neg(z0)) -> c6
   COMPUTELINE#1(nil, z0, z1) -> c28
   #MULT(#neg(z0), #0) -> c8
   #MULT(#0, #0) -> c5
   #ADD(#0, z0) -> c
   #SUCC(#pos(#s(z0))) -> c23
   #PRED(#pos(#s(#s(z0)))) -> c19
   MATRIXMULT#1(nil, z0) -> c38
   COMPUTELINE#2(nil, z0, z1, z2) -> c30
   #SUCC(#0) -> c20
   #SUCC(#neg(#s(#0))) -> c21
   #PRED(#neg(#s(z0))) -> c17
   #PRED(#0) -> c16
   #ADD(#pos(#s(#0)), z0) -> c3(#SUCC(z0))
   #ADD(#neg(#s(#0)), z0) -> c1(#PRED(z0))
   #MULT(#0, #pos(z0)) -> c7
   #MULT(#pos(z0), #0) -> c11
   #SUCC(#neg(#s(#s(z0)))) -> c22
   #NATMULT(#0, z0) -> c14

----------------------------------------

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   *(z0, z1) -> #mult(z0, z1)
   +(z0, z1) -> #add(z0, z1)
   computeLine(z0, z1, z2) -> computeLine#1(z0, z2, z1)
   computeLine#1(::(z0, z1), z2, z3) -> computeLine#2(z3, z2, z0, z1)
   computeLine#1(nil, z0, z1) -> z0
   computeLine#2(::(z0, z1), z2, z3, z4) -> computeLine(z4, z1, lineMult(z3, z0, z2))
   computeLine#2(nil, z0, z1, z2) -> nil
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   matrixMult(z0, z1) -> matrixMult#1(z0, z1)
   matrixMult#1(::(z0, z1), z2) -> ::(computeLine(z0, z2, nil), matrixMult(z1, z2))
   matrixMult#1(nil, z0) -> nil
Tuples:
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#PRED(#add(#pos(#s(z0)), z1)), #ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#SUCC(#add(#pos(#s(z0)), z1)), #ADD(#pos(#s(z0)), z1))
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
K tuples:none
Defined Rule Symbols:   *_2, +_2, computeLine_3, computeLine#1_3, computeLine#2_4, lineMult_3, lineMult#1_3, lineMult#2_4, matrixMult_2, matrixMult#1_2, #add_2, #mult_2, #natmult_2, #pred_1, #succ_1

Defined Pair Symbols:   #ADD_2, #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2

Compound Symbols:   c2_2, c4_2, c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2


----------------------------------------

(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 2 trailing tuple parts
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   *(z0, z1) -> #mult(z0, z1)
   +(z0, z1) -> #add(z0, z1)
   computeLine(z0, z1, z2) -> computeLine#1(z0, z2, z1)
   computeLine#1(::(z0, z1), z2, z3) -> computeLine#2(z3, z2, z0, z1)
   computeLine#1(nil, z0, z1) -> z0
   computeLine#2(::(z0, z1), z2, z3, z4) -> computeLine(z4, z1, lineMult(z3, z0, z2))
   computeLine#2(nil, z0, z1, z2) -> nil
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   matrixMult(z0, z1) -> matrixMult#1(z0, z1)
   matrixMult#1(::(z0, z1), z2) -> ::(computeLine(z0, z2, nil), matrixMult(z1, z2))
   matrixMult#1(nil, z0) -> nil
Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
K tuples:none
Defined Rule Symbols:   *_2, +_2, computeLine_3, computeLine#1_3, computeLine#2_4, lineMult_3, lineMult#1_3, lineMult#2_4, matrixMult_2, matrixMult#1_2, #add_2, #mult_2, #natmult_2, #pred_1, #succ_1

Defined Pair Symbols:   #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2, #ADD_2

Compound Symbols:   c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2, c2_1, c4_1


----------------------------------------

(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   computeLine(z0, z1, z2) -> computeLine#1(z0, z2, z1)
   computeLine#1(::(z0, z1), z2, z3) -> computeLine#2(z3, z2, z0, z1)
   computeLine#1(nil, z0, z1) -> z0
   computeLine#2(::(z0, z1), z2, z3, z4) -> computeLine(z4, z1, lineMult(z3, z0, z2))
   computeLine#2(nil, z0, z1, z2) -> nil
   matrixMult(z0, z1) -> matrixMult#1(z0, z1)
   matrixMult#1(::(z0, z1), z2) -> ::(computeLine(z0, z2, nil), matrixMult(z1, z2))
   matrixMult#1(nil, z0) -> nil

----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   +(z0, z1) -> #add(z0, z1)
   *(z0, z1) -> #mult(z0, z1)
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
K tuples:none
Defined Rule Symbols:   #natmult_2, #add_2, #succ_1, lineMult_3, lineMult#1_3, lineMult#2_4, +_2, *_2, #mult_2, #pred_1

Defined Pair Symbols:   #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2, #ADD_2

Compound Symbols:   c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2, c2_1, c4_1


----------------------------------------

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
We considered the (Usable) Rules:none
And the Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(#0) = 0
   POL(#ADD(x_1, x_2)) = 0
   POL(#MULT(x_1, x_2)) = 0
   POL(#NATMULT(x_1, x_2)) = 0
   POL(#add(x_1, x_2)) = 0
   POL(#mult(x_1, x_2)) = [1] + x_1 + x_2
   POL(#natmult(x_1, x_2)) = [1] + x_1 + x_2
   POL(#neg(x_1)) = 0
   POL(#pos(x_1)) = 0
   POL(#pred(x_1)) = [1] + x_1
   POL(#s(x_1)) = 0
   POL(#succ(x_1)) = [1] + x_1
   POL(*(x_1, x_2)) = x_1 + x_2
   POL(*'(x_1, x_2)) = 0
   POL(+(x_1, x_2)) = [1] + x_1 + x_2
   POL(+'(x_1, x_2)) = 0
   POL(::(x_1, x_2)) = [1] + x_1 + x_2
   POL(COMPUTELINE(x_1, x_2, x_3)) = x_1
   POL(COMPUTELINE#1(x_1, x_2, x_3)) = x_1
   POL(COMPUTELINE#2(x_1, x_2, x_3, x_4)) = [1] + x_3 + x_4
   POL(LINEMULT(x_1, x_2, x_3)) = x_1
   POL(LINEMULT#1(x_1, x_2, x_3)) = x_3
   POL(LINEMULT#2(x_1, x_2, x_3, x_4)) = x_2
   POL(MATRIXMULT(x_1, x_2)) = [1] + x_1 + x_2
   POL(MATRIXMULT#1(x_1, x_2)) = [1] + x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c15(x_1, x_2)) = x_1 + x_2
   POL(c2(x_1)) = x_1
   POL(c24(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c31(x_1)) = x_1
   POL(c32(x_1)) = x_1
   POL(c34(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c35(x_1, x_2)) = x_1 + x_2
   POL(c36(x_1)) = x_1
   POL(c37(x_1, x_2)) = x_1 + x_2
   POL(c4(x_1)) = x_1
   POL(c9(x_1)) = x_1
   POL(lineMult(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(lineMult#1(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(lineMult#2(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4
   POL(nil) = 0

----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   +(z0, z1) -> #add(z0, z1)
   *(z0, z1) -> #mult(z0, z1)
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
K tuples:
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
Defined Rule Symbols:   #natmult_2, #add_2, #succ_1, lineMult_3, lineMult#1_3, lineMult#2_4, +_2, *_2, #mult_2, #pred_1

Defined Pair Symbols:   #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2, #ADD_2

Compound Symbols:   c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2, c2_1, c4_1


----------------------------------------

(13) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))

----------------------------------------

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   +(z0, z1) -> #add(z0, z1)
   *(z0, z1) -> #mult(z0, z1)
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
K tuples:
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
Defined Rule Symbols:   #natmult_2, #add_2, #succ_1, lineMult_3, lineMult#1_3, lineMult#2_4, +_2, *_2, #mult_2, #pred_1

Defined Pair Symbols:   #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2, #ADD_2

Compound Symbols:   c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2, c2_1, c4_1


----------------------------------------

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
We considered the (Usable) Rules:none
And the Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(#0) = 0
   POL(#ADD(x_1, x_2)) = 0
   POL(#MULT(x_1, x_2)) = 0
   POL(#NATMULT(x_1, x_2)) = 0
   POL(#add(x_1, x_2)) = 0
   POL(#mult(x_1, x_2)) = [1]
   POL(#natmult(x_1, x_2)) = [2]x_2
   POL(#neg(x_1)) = 0
   POL(#pos(x_1)) = 0
   POL(#pred(x_1)) = [1]
   POL(#s(x_1)) = 0
   POL(#succ(x_1)) = [1]
   POL(*(x_1, x_2)) = 0
   POL(*'(x_1, x_2)) = 0
   POL(+(x_1, x_2)) = [2] + x_1 + x_2 + [2]x_2^2 + x_1*x_2 + [2]x_1^2
   POL(+'(x_1, x_2)) = 0
   POL(::(x_1, x_2)) = [1] + x_1 + x_2
   POL(COMPUTELINE(x_1, x_2, x_3)) = x_2
   POL(COMPUTELINE#1(x_1, x_2, x_3)) = x_3
   POL(COMPUTELINE#2(x_1, x_2, x_3, x_4)) = x_1
   POL(LINEMULT(x_1, x_2, x_3)) = x_2
   POL(LINEMULT#1(x_1, x_2, x_3)) = x_1
   POL(LINEMULT#2(x_1, x_2, x_3, x_4)) = x_4
   POL(MATRIXMULT(x_1, x_2)) = [2]x_2^2 + [2]x_1*x_2
   POL(MATRIXMULT#1(x_1, x_2)) = [2]x_2^2 + [2]x_1*x_2
   POL(c10(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c15(x_1, x_2)) = x_1 + x_2
   POL(c2(x_1)) = x_1
   POL(c24(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c31(x_1)) = x_1
   POL(c32(x_1)) = x_1
   POL(c34(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c35(x_1, x_2)) = x_1 + x_2
   POL(c36(x_1)) = x_1
   POL(c37(x_1, x_2)) = x_1 + x_2
   POL(c4(x_1)) = x_1
   POL(c9(x_1)) = x_1
   POL(lineMult(x_1, x_2, x_3)) = 0
   POL(lineMult#1(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2
   POL(lineMult#2(x_1, x_2, x_3, x_4)) = [1] + x_2 + x_3 + x_4 + x_4^2 + x_3*x_4 + x_2*x_4 + x_3^2 + x_2*x_3 + x_2^2
   POL(nil) = 0

----------------------------------------

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #natmult(#0, z0) -> #0
   #natmult(#s(z0), z1) -> #add(#pos(z1), #natmult(z0, z1))
   #add(#pos(#s(#0)), z0) -> #succ(z0)
   #add(#pos(#s(#s(z0))), z1) -> #succ(#add(#pos(#s(z0)), z1))
   #add(#0, z0) -> z0
   #add(#neg(#s(#0)), z0) -> #pred(z0)
   #add(#neg(#s(#s(z0))), z1) -> #pred(#add(#pos(#s(z0)), z1))
   #succ(#0) -> #pos(#s(#0))
   #succ(#neg(#s(#0))) -> #0
   #succ(#neg(#s(#s(z0)))) -> #neg(#s(z0))
   #succ(#pos(#s(z0))) -> #pos(#s(#s(z0)))
   lineMult(z0, z1, z2) -> lineMult#1(z1, z2, z0)
   lineMult#1(::(z0, z1), z2, z3) -> lineMult#2(z2, z3, z0, z1)
   lineMult#1(nil, z0, z1) -> nil
   lineMult#2(::(z0, z1), z2, z3, z4) -> ::(+(*(z3, z2), z0), lineMult(z2, z4, z1))
   lineMult#2(nil, z0, z1, z2) -> ::(*(z1, z0), lineMult(z0, z2, nil))
   +(z0, z1) -> #add(z0, z1)
   *(z0, z1) -> #mult(z0, z1)
   #mult(#0, #0) -> #0
   #mult(#0, #neg(z0)) -> #0
   #mult(#0, #pos(z0)) -> #0
   #mult(#neg(z0), #0) -> #0
   #mult(#neg(z0), #neg(z1)) -> #pos(#natmult(z0, z1))
   #mult(#neg(z0), #pos(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #0) -> #0
   #mult(#pos(z0), #neg(z1)) -> #neg(#natmult(z0, z1))
   #mult(#pos(z0), #pos(z1)) -> #pos(#natmult(z0, z1))
   #pred(#0) -> #neg(#s(#0))
   #pred(#neg(#s(z0))) -> #neg(#s(#s(z0)))
   #pred(#pos(#s(#0))) -> #0
   #pred(#pos(#s(#s(z0)))) -> #pos(#s(z0))
Tuples:
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   #NATMULT(#s(z0), z1) -> c15(#ADD(#pos(z1), #natmult(z0, z1)), #NATMULT(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #ADD(#pos(#s(#s(z0))), z1) -> c4(#ADD(#pos(#s(z0)), z1))
S tuples:
   *'(z0, z1) -> c24(#MULT(z0, z1))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
K tuples:
   COMPUTELINE#2(::(z0, z1), z2, z3, z4) -> c29(COMPUTELINE(z4, z1, lineMult(z3, z0, z2)), LINEMULT(z3, z0, z2))
   MATRIXMULT#1(::(z0, z1), z2) -> c37(COMPUTELINE(z0, z2, nil), MATRIXMULT(z1, z2))
   COMPUTELINE(z0, z1, z2) -> c26(COMPUTELINE#1(z0, z2, z1))
   COMPUTELINE#1(::(z0, z1), z2, z3) -> c27(COMPUTELINE#2(z3, z2, z0, z1))
   MATRIXMULT(z0, z1) -> c36(MATRIXMULT#1(z0, z1))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
Defined Rule Symbols:   #natmult_2, #add_2, #succ_1, lineMult_3, lineMult#1_3, lineMult#2_4, +_2, *_2, #mult_2, #pred_1

Defined Pair Symbols:   #MULT_2, #NATMULT_2, *'_2, +'_2, COMPUTELINE_3, COMPUTELINE#1_3, COMPUTELINE#2_4, LINEMULT_3, LINEMULT#1_3, LINEMULT#2_4, MATRIXMULT_2, MATRIXMULT#1_2, #ADD_2

Compound Symbols:   c9_1, c10_1, c12_1, c13_1, c15_2, c24_1, c25_1, c26_1, c27_1, c29_2, c31_1, c32_1, c34_3, c35_2, c36_1, c37_2, c2_1, c4_1


----------------------------------------

(17) CdtKnowledgeProof (FINISHED)
The following tuples could be moved from S to K by knowledge propagation:
   LINEMULT#2(::(z0, z1), z2, z3, z4) -> c34(+'(*(z3, z2), z0), *'(z3, z2), LINEMULT(z2, z4, z1))
   LINEMULT#2(nil, z0, z1, z2) -> c35(*'(z1, z0), LINEMULT(z0, z2, nil))
   +'(z0, z1) -> c25(#ADD(z0, z1))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   *'(z0, z1) -> c24(#MULT(z0, z1))
   LINEMULT(z0, z1, z2) -> c31(LINEMULT#1(z1, z2, z0))
   #ADD(#neg(#s(#s(z0))), z1) -> c2(#ADD(#pos(#s(z0)), z1))
   #MULT(#neg(z0), #neg(z1)) -> c9(#NATMULT(z0, z1))
   #MULT(#neg(z0), #pos(z1)) -> c10(#NATMULT(z0, z1))
   #MULT(#pos(z0), #neg(z1)) -> c12(#NATMULT(z0, z1))
   #MULT(#pos(z0), #pos(z1)) -> c13(#NATMULT(z0, z1))
   LINEMULT#1(::(z0, z1), z2, z3) -> c32(LINEMULT#2(z2, z3, z0, z1))
Now S is empty
----------------------------------------

(18)
BOUNDS(1, 1)

----------------------------------------

(19) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(20)
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)
   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
   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

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
----------------------------------------

(21) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(22)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos

----------------------------------------

(23) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
#add, computeLine, computeLine#1, lineMult, lineMult#1, matrixMult, matrixMult#1, #natmult

They will be analysed ascendingly in the following order:
#add < #natmult
computeLine = computeLine#1
computeLine < matrixMult#1
lineMult < computeLine#1
lineMult = lineMult#1
matrixMult = matrixMult#1

----------------------------------------

(24)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
#add, computeLine, computeLine#1, lineMult, lineMult#1, matrixMult, matrixMult#1, #natmult

They will be analysed ascendingly in the following order:
#add < #natmult
computeLine = computeLine#1
computeLine < matrixMult#1
lineMult < computeLine#1
lineMult = lineMult#1
matrixMult = matrixMult#1

----------------------------------------

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n112_3)

Induction Base:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, 0)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c))

Induction Step:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, +(n112_3, 1))), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) ->_R^Omega(1)
lineMult#2(gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c), nil, gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3))) ->_R^Omega(1)
::(*'(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(c), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), nil)) ->_R^Omega(1)
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(c), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), nil)) ->_R^Omega(1)
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), nil, gen_:::nil:#0:#s:#neg:#pos2_3(c))) ->_IH
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), *3_3)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(26)
Complex Obligation (BEST)

----------------------------------------

(27)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
lineMult#1, computeLine, computeLine#1, lineMult, matrixMult, matrixMult#1

They will be analysed ascendingly in the following order:
computeLine = computeLine#1
computeLine < matrixMult#1
lineMult < computeLine#1
lineMult = lineMult#1
matrixMult = matrixMult#1

----------------------------------------

(28) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(29)
BOUNDS(n^1, INF)

----------------------------------------

(30)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Lemmas:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n112_3)


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
lineMult, computeLine, computeLine#1, matrixMult, matrixMult#1

They will be analysed ascendingly in the following order:
computeLine = computeLine#1
computeLine < matrixMult#1
lineMult < computeLine#1
lineMult = lineMult#1
matrixMult = matrixMult#1

----------------------------------------

(31) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> *3_3, rt in Omega(n4468534_3)

Induction Base:
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(0))

Induction Step:
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(+(n4468534_3, 1)), gen_:::nil:#0:#s:#neg:#pos2_3(0)) ->_R^Omega(1)
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(n4468534_3, 1)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(a)) ->_R^Omega(1)
lineMult#2(gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(a), nil, gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3)) ->_R^Omega(1)
::(*'(nil, gen_:::nil:#0:#s:#neg:#pos2_3(a)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), nil)) ->_R^Omega(1)
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(a)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), nil)) ->_IH
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(a)), *3_3)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(32)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Lemmas:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n112_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n112_3)
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> *3_3, rt in Omega(n4468534_3)


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
lineMult#1, computeLine, computeLine#1, matrixMult, matrixMult#1

They will be analysed ascendingly in the following order:
computeLine = computeLine#1
computeLine < matrixMult#1
lineMult < computeLine#1
lineMult = lineMult#1
matrixMult = matrixMult#1

----------------------------------------

(33) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n8943742_3)

Induction Base:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, 0)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c))

Induction Step:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, +(n8943742_3, 1))), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) ->_R^Omega(1)
lineMult#2(gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c), nil, gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3))) ->_R^Omega(1)
::(*'(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(c), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), nil)) ->_R^Omega(1)
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(c), gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), nil)) ->_R^Omega(1)
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), nil, gen_:::nil:#0:#s:#neg:#pos2_3(c))) ->_IH
::(#mult(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c)), *3_3)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(34)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Lemmas:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n8943742_3)
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> *3_3, rt in Omega(n4468534_3)


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
computeLine#1, computeLine, matrixMult, matrixMult#1

They will be analysed ascendingly in the following order:
computeLine = computeLine#1
computeLine < matrixMult#1
matrixMult = matrixMult#1

----------------------------------------

(35) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
matrixMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), rt in Omega(1 + n13505007_3)

Induction Base:
matrixMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(b)) ->_R^Omega(1)
nil

Induction Step:
matrixMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(n13505007_3, 1)), gen_:::nil:#0:#s:#neg:#pos2_3(b)) ->_R^Omega(1)
::(computeLine(nil, gen_:::nil:#0:#s:#neg:#pos2_3(b), nil), matrixMult(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_R^Omega(1)
::(computeLine#1(nil, nil, gen_:::nil:#0:#s:#neg:#pos2_3(b)), matrixMult(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_R^Omega(1)
::(nil, matrixMult(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_R^Omega(1)
::(nil, matrixMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b))) ->_IH
::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(c13505008_3))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(36)
Obligation:
Innermost TRS:
Rules:
*'(@x, @y) -> #mult(@x, @y)
+'(@x, @y) -> #add(@x, @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
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
#add(#0, @y) -> @y
#add(#neg(#s(#0)), @y) -> #pred(@y)
#add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y))
#add(#pos(#s(#0)), @y) -> #succ(@y)
#add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y))
#mult(#0, #0) -> #0
#mult(#0, #neg(@y)) -> #0
#mult(#0, #pos(@y)) -> #0
#mult(#neg(@x), #0) -> #0
#mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y))
#mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #0) -> #0
#mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y))
#mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y))
#natmult(#0, @y) -> #0
#natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y))
#pred(#0) -> #neg(#s(#0))
#pred(#neg(#s(@x))) -> #neg(#s(#s(@x)))
#pred(#pos(#s(#0))) -> #0
#pred(#pos(#s(#s(@x)))) -> #pos(#s(@x))
#succ(#0) -> #pos(#s(#0))
#succ(#neg(#s(#0))) -> #0
#succ(#neg(#s(#s(@x)))) -> #neg(#s(@x))
#succ(#pos(#s(@x))) -> #pos(#s(#s(@x)))

Types:
*' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#mult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
+' :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#add :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
:: :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
computeLine#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
nil :: :::nil:#0:#s:#neg:#pos
lineMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
lineMult#2 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
matrixMult#1 :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#0 :: :::nil:#0:#s:#neg:#pos
#neg :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#s :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pred :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#pos :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#succ :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
#natmult :: :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos -> :::nil:#0:#s:#neg:#pos
hole_:::nil:#0:#s:#neg:#pos1_3 :: :::nil:#0:#s:#neg:#pos
gen_:::nil:#0:#s:#neg:#pos2_3 :: Nat -> :::nil:#0:#s:#neg:#pos


Lemmas:
lineMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(+(1, n8943742_3)), gen_:::nil:#0:#s:#neg:#pos2_3(0), gen_:::nil:#0:#s:#neg:#pos2_3(c)) -> *3_3, rt in Omega(n8943742_3)
lineMult(gen_:::nil:#0:#s:#neg:#pos2_3(a), gen_:::nil:#0:#s:#neg:#pos2_3(n4468534_3), gen_:::nil:#0:#s:#neg:#pos2_3(0)) -> *3_3, rt in Omega(n4468534_3)
matrixMult#1(gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), gen_:::nil:#0:#s:#neg:#pos2_3(b)) -> gen_:::nil:#0:#s:#neg:#pos2_3(n13505007_3), rt in Omega(1 + n13505007_3)


Generator Equations:
gen_:::nil:#0:#s:#neg:#pos2_3(0) <=> nil
gen_:::nil:#0:#s:#neg:#pos2_3(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#s:#neg:#pos2_3(x))


The following defined symbols remain to be analysed:
matrixMult

They will be analysed ascendingly in the following order:
matrixMult = matrixMult#1