1103.09/291.56 WORST_CASE(Omega(n^1), ?) 1103.15/291.56 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1103.15/291.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1103.15/291.56 1103.15/291.56 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 (0) CpxRelTRS 1103.15/291.56 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 357 ms] 1103.15/291.56 (2) CpxRelTRS 1103.15/291.56 (3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1103.15/291.56 (4) TRS for Loop Detection 1103.15/291.56 (5) DecreasingLoopProof [LOWER BOUND(ID), 123 ms] 1103.15/291.56 (6) BEST 1103.15/291.56 (7) proven lower bound 1103.15/291.56 (8) LowerBoundPropagationProof [FINISHED, 0 ms] 1103.15/291.56 (9) BOUNDS(n^1, INF) 1103.15/291.56 (10) TRS for Loop Detection 1103.15/291.56 1103.15/291.56 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (0) 1103.15/291.56 Obligation: 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 1103.15/291.56 The TRS R consists of the following rules: 1103.15/291.56 1103.15/291.56 *(@x, @y) -> #mult(@x, @y) 1103.15/291.56 +(@x, @y) -> #add(@x, @y) 1103.15/291.56 appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) 1103.15/291.56 appendreverse#1(nil, @sofar) -> @sofar 1103.15/291.56 bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) 1103.15/291.56 bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) 1103.15/291.56 bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) 1103.15/291.56 bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) 1103.15/291.56 bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) 1103.15/291.56 bftMult'#3(nil, @acc, @queue) -> @acc 1103.15/291.56 bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) 1103.15/291.56 bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) 1103.15/291.56 bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) 1103.15/291.56 computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) 1103.15/291.56 computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) 1103.15/291.56 computeLine#1(nil, @acc, @m) -> @acc 1103.15/291.56 computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) 1103.15/291.56 computeLine#2(nil, @acc, @x, @xs) -> nil 1103.15/291.56 dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) 1103.15/291.56 dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) 1103.15/291.56 dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) 1103.15/291.56 dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) 1103.15/291.56 dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) 1103.15/291.56 enqueue(@t, @queue) -> enqueue#1(@queue, @t) 1103.15/291.56 enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) 1103.15/291.56 lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) 1103.15/291.56 lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) 1103.15/291.56 lineMult#1(nil, @l2, @n) -> nil 1103.15/291.56 lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) 1103.15/291.56 lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) 1103.15/291.56 matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) 1103.15/291.56 matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) 1103.15/291.56 matrixMult#1(nil, @m2) -> nil 1103.15/291.56 reverse(@xs) -> appendreverse(@xs, nil) 1103.15/291.56 1103.15/291.56 The (relative) TRS S consists of the following rules: 1103.15/291.56 1103.15/291.56 #add(#0, @y) -> @y 1103.15/291.56 #add(#neg(#s(#0)), @y) -> #pred(@y) 1103.15/291.56 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #add(#pos(#s(#0)), @y) -> #succ(@y) 1103.15/291.56 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #mult(#0, #0) -> #0 1103.15/291.56 #mult(#0, #neg(@y)) -> #0 1103.15/291.56 #mult(#0, #pos(@y)) -> #0 1103.15/291.56 #mult(#neg(@x), #0) -> #0 1103.15/291.56 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #0) -> #0 1103.15/291.56 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #natmult(#0, @y) -> #0 1103.15/291.56 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1103.15/291.56 #pred(#0) -> #neg(#s(#0)) 1103.15/291.56 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1103.15/291.56 #pred(#pos(#s(#0))) -> #0 1103.15/291.56 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1103.15/291.56 #succ(#0) -> #pos(#s(#0)) 1103.15/291.56 #succ(#neg(#s(#0))) -> #0 1103.15/291.56 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1103.15/291.56 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1103.15/291.56 1103.15/291.56 Rewrite Strategy: INNERMOST 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 1103.15/291.56 proved termination of relative rules 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (2) 1103.15/291.56 Obligation: 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 1103.15/291.56 The TRS R consists of the following rules: 1103.15/291.56 1103.15/291.56 *(@x, @y) -> #mult(@x, @y) 1103.15/291.56 +(@x, @y) -> #add(@x, @y) 1103.15/291.56 appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) 1103.15/291.56 appendreverse#1(nil, @sofar) -> @sofar 1103.15/291.56 bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) 1103.15/291.56 bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) 1103.15/291.56 bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) 1103.15/291.56 bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) 1103.15/291.56 bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) 1103.15/291.56 bftMult'#3(nil, @acc, @queue) -> @acc 1103.15/291.56 bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) 1103.15/291.56 bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) 1103.15/291.56 bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) 1103.15/291.56 computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) 1103.15/291.56 computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) 1103.15/291.56 computeLine#1(nil, @acc, @m) -> @acc 1103.15/291.56 computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) 1103.15/291.56 computeLine#2(nil, @acc, @x, @xs) -> nil 1103.15/291.56 dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) 1103.15/291.56 dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) 1103.15/291.56 dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) 1103.15/291.56 dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) 1103.15/291.56 dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) 1103.15/291.56 enqueue(@t, @queue) -> enqueue#1(@queue, @t) 1103.15/291.56 enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) 1103.15/291.56 lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) 1103.15/291.56 lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) 1103.15/291.56 lineMult#1(nil, @l2, @n) -> nil 1103.15/291.56 lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) 1103.15/291.56 lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) 1103.15/291.56 matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) 1103.15/291.56 matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) 1103.15/291.56 matrixMult#1(nil, @m2) -> nil 1103.15/291.56 reverse(@xs) -> appendreverse(@xs, nil) 1103.15/291.56 1103.15/291.56 The (relative) TRS S consists of the following rules: 1103.15/291.56 1103.15/291.56 #add(#0, @y) -> @y 1103.15/291.56 #add(#neg(#s(#0)), @y) -> #pred(@y) 1103.15/291.56 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #add(#pos(#s(#0)), @y) -> #succ(@y) 1103.15/291.56 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #mult(#0, #0) -> #0 1103.15/291.56 #mult(#0, #neg(@y)) -> #0 1103.15/291.56 #mult(#0, #pos(@y)) -> #0 1103.15/291.56 #mult(#neg(@x), #0) -> #0 1103.15/291.56 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #0) -> #0 1103.15/291.56 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #natmult(#0, @y) -> #0 1103.15/291.56 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1103.15/291.56 #pred(#0) -> #neg(#s(#0)) 1103.15/291.56 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1103.15/291.56 #pred(#pos(#s(#0))) -> #0 1103.15/291.56 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1103.15/291.56 #succ(#0) -> #pos(#s(#0)) 1103.15/291.56 #succ(#neg(#s(#0))) -> #0 1103.15/291.56 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1103.15/291.56 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1103.15/291.56 1103.15/291.56 Rewrite Strategy: INNERMOST 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1103.15/291.56 Transformed a relative TRS into a decreasing-loop problem. 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (4) 1103.15/291.56 Obligation: 1103.15/291.56 Analyzing the following TRS for decreasing loops: 1103.15/291.56 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 1103.15/291.56 The TRS R consists of the following rules: 1103.15/291.56 1103.15/291.56 *(@x, @y) -> #mult(@x, @y) 1103.15/291.56 +(@x, @y) -> #add(@x, @y) 1103.15/291.56 appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) 1103.15/291.56 appendreverse#1(nil, @sofar) -> @sofar 1103.15/291.56 bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) 1103.15/291.56 bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) 1103.15/291.56 bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) 1103.15/291.56 bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) 1103.15/291.56 bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) 1103.15/291.56 bftMult'#3(nil, @acc, @queue) -> @acc 1103.15/291.56 bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) 1103.15/291.56 bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) 1103.15/291.56 bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) 1103.15/291.56 computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) 1103.15/291.56 computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) 1103.15/291.56 computeLine#1(nil, @acc, @m) -> @acc 1103.15/291.56 computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) 1103.15/291.56 computeLine#2(nil, @acc, @x, @xs) -> nil 1103.15/291.56 dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) 1103.15/291.56 dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) 1103.15/291.56 dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) 1103.15/291.56 dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) 1103.15/291.56 dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) 1103.15/291.56 enqueue(@t, @queue) -> enqueue#1(@queue, @t) 1103.15/291.56 enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) 1103.15/291.56 lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) 1103.15/291.56 lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) 1103.15/291.56 lineMult#1(nil, @l2, @n) -> nil 1103.15/291.56 lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) 1103.15/291.56 lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) 1103.15/291.56 matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) 1103.15/291.56 matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) 1103.15/291.56 matrixMult#1(nil, @m2) -> nil 1103.15/291.56 reverse(@xs) -> appendreverse(@xs, nil) 1103.15/291.56 1103.15/291.56 The (relative) TRS S consists of the following rules: 1103.15/291.56 1103.15/291.56 #add(#0, @y) -> @y 1103.15/291.56 #add(#neg(#s(#0)), @y) -> #pred(@y) 1103.15/291.56 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #add(#pos(#s(#0)), @y) -> #succ(@y) 1103.15/291.56 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #mult(#0, #0) -> #0 1103.15/291.56 #mult(#0, #neg(@y)) -> #0 1103.15/291.56 #mult(#0, #pos(@y)) -> #0 1103.15/291.56 #mult(#neg(@x), #0) -> #0 1103.15/291.56 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #0) -> #0 1103.15/291.56 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #natmult(#0, @y) -> #0 1103.15/291.56 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1103.15/291.56 #pred(#0) -> #neg(#s(#0)) 1103.15/291.56 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1103.15/291.56 #pred(#pos(#s(#0))) -> #0 1103.15/291.56 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1103.15/291.56 #succ(#0) -> #pos(#s(#0)) 1103.15/291.56 #succ(#neg(#s(#0))) -> #0 1103.15/291.56 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1103.15/291.56 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1103.15/291.56 1103.15/291.56 Rewrite Strategy: INNERMOST 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (5) DecreasingLoopProof (LOWER BOUND(ID)) 1103.15/291.56 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1103.15/291.56 1103.15/291.56 The rewrite sequence 1103.15/291.56 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) ->^+ appendreverse#1(@as, ::(@a, @sofar)) 1103.15/291.56 1103.15/291.56 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1103.15/291.56 1103.15/291.56 The pumping substitution is [@as / ::(@a, @as)]. 1103.15/291.56 1103.15/291.56 The result substitution is [@sofar / ::(@a, @sofar)]. 1103.15/291.56 1103.15/291.56 1103.15/291.56 1103.15/291.56 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (6) 1103.15/291.56 Complex Obligation (BEST) 1103.15/291.56 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (7) 1103.15/291.56 Obligation: 1103.15/291.56 Proved the lower bound n^1 for the following obligation: 1103.15/291.56 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 1103.15/291.56 The TRS R consists of the following rules: 1103.15/291.56 1103.15/291.56 *(@x, @y) -> #mult(@x, @y) 1103.15/291.56 +(@x, @y) -> #add(@x, @y) 1103.15/291.56 appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) 1103.15/291.56 appendreverse#1(nil, @sofar) -> @sofar 1103.15/291.56 bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) 1103.15/291.56 bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) 1103.15/291.56 bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) 1103.15/291.56 bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) 1103.15/291.56 bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) 1103.15/291.56 bftMult'#3(nil, @acc, @queue) -> @acc 1103.15/291.56 bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) 1103.15/291.56 bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) 1103.15/291.56 bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) 1103.15/291.56 computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) 1103.15/291.56 computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) 1103.15/291.56 computeLine#1(nil, @acc, @m) -> @acc 1103.15/291.56 computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) 1103.15/291.56 computeLine#2(nil, @acc, @x, @xs) -> nil 1103.15/291.56 dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) 1103.15/291.56 dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) 1103.15/291.56 dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) 1103.15/291.56 dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) 1103.15/291.56 dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) 1103.15/291.56 enqueue(@t, @queue) -> enqueue#1(@queue, @t) 1103.15/291.56 enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) 1103.15/291.56 lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) 1103.15/291.56 lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) 1103.15/291.56 lineMult#1(nil, @l2, @n) -> nil 1103.15/291.56 lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) 1103.15/291.56 lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) 1103.15/291.56 matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) 1103.15/291.56 matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) 1103.15/291.56 matrixMult#1(nil, @m2) -> nil 1103.15/291.56 reverse(@xs) -> appendreverse(@xs, nil) 1103.15/291.56 1103.15/291.56 The (relative) TRS S consists of the following rules: 1103.15/291.56 1103.15/291.56 #add(#0, @y) -> @y 1103.15/291.56 #add(#neg(#s(#0)), @y) -> #pred(@y) 1103.15/291.56 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #add(#pos(#s(#0)), @y) -> #succ(@y) 1103.15/291.56 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #mult(#0, #0) -> #0 1103.15/291.56 #mult(#0, #neg(@y)) -> #0 1103.15/291.56 #mult(#0, #pos(@y)) -> #0 1103.15/291.56 #mult(#neg(@x), #0) -> #0 1103.15/291.56 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #0) -> #0 1103.15/291.56 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #natmult(#0, @y) -> #0 1103.15/291.56 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1103.15/291.56 #pred(#0) -> #neg(#s(#0)) 1103.15/291.56 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1103.15/291.56 #pred(#pos(#s(#0))) -> #0 1103.15/291.56 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1103.15/291.56 #succ(#0) -> #pos(#s(#0)) 1103.15/291.56 #succ(#neg(#s(#0))) -> #0 1103.15/291.56 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1103.15/291.56 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1103.15/291.56 1103.15/291.56 Rewrite Strategy: INNERMOST 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (8) LowerBoundPropagationProof (FINISHED) 1103.15/291.56 Propagated lower bound. 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (9) 1103.15/291.56 BOUNDS(n^1, INF) 1103.15/291.56 1103.15/291.56 ---------------------------------------- 1103.15/291.56 1103.15/291.56 (10) 1103.15/291.56 Obligation: 1103.15/291.56 Analyzing the following TRS for decreasing loops: 1103.15/291.56 1103.15/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1103.15/291.56 1103.15/291.56 1103.15/291.56 The TRS R consists of the following rules: 1103.15/291.56 1103.15/291.56 *(@x, @y) -> #mult(@x, @y) 1103.15/291.56 +(@x, @y) -> #add(@x, @y) 1103.15/291.56 appendreverse(@toreverse, @sofar) -> appendreverse#1(@toreverse, @sofar) 1103.15/291.56 appendreverse#1(::(@a, @as), @sofar) -> appendreverse(@as, ::(@a, @sofar)) 1103.15/291.56 appendreverse#1(nil, @sofar) -> @sofar 1103.15/291.56 bftMult(@t, @acc) -> bftMult'(tuple#2(::(@t, nil), nil), @acc) 1103.15/291.56 bftMult'(@queue, @acc) -> bftMult'#1(bftMult'#2(@queue), @acc) 1103.15/291.56 bftMult'#1(tuple#2(@elem, @queue), @acc) -> bftMult'#3(@elem, @acc, @queue) 1103.15/291.56 bftMult'#2(tuple#2(@dequeue@1, @dequeue@2)) -> dequeue(@dequeue@1, @dequeue@2) 1103.15/291.56 bftMult'#3(::(@t, @_@3), @acc, @queue) -> bftMult'#4(@t, @acc, @queue) 1103.15/291.56 bftMult'#3(nil, @acc, @queue) -> @acc 1103.15/291.56 bftMult'#4(leaf, @acc, @queue) -> bftMult'(@queue, @acc) 1103.15/291.56 bftMult'#4(node(@y, @t1, @t2), @acc, @queue) -> bftMult'#5(enqueue(@t2, enqueue(@t1, @queue)), @acc, @y) 1103.15/291.56 bftMult'#5(@queue', @acc, @y) -> bftMult'(@queue', matrixMult(@acc, @y)) 1103.15/291.56 computeLine(@line, @m, @acc) -> computeLine#1(@line, @acc, @m) 1103.15/291.56 computeLine#1(::(@x, @xs), @acc, @m) -> computeLine#2(@m, @acc, @x, @xs) 1103.15/291.56 computeLine#1(nil, @acc, @m) -> @acc 1103.15/291.56 computeLine#2(::(@l, @ls), @acc, @x, @xs) -> computeLine(@xs, @ls, lineMult(@x, @l, @acc)) 1103.15/291.56 computeLine#2(nil, @acc, @x, @xs) -> nil 1103.15/291.56 dequeue(@outq, @inq) -> dequeue#1(@outq, @inq) 1103.15/291.56 dequeue#1(::(@t, @ts), @inq) -> tuple#2(::(@t, nil), tuple#2(@ts, @inq)) 1103.15/291.56 dequeue#1(nil, @inq) -> dequeue#2(reverse(@inq)) 1103.15/291.56 dequeue#2(::(@t, @ts)) -> tuple#2(::(@t, nil), tuple#2(@ts, nil)) 1103.15/291.56 dequeue#2(nil) -> tuple#2(nil, tuple#2(nil, nil)) 1103.15/291.56 enqueue(@t, @queue) -> enqueue#1(@queue, @t) 1103.15/291.56 enqueue#1(tuple#2(@outq, @inq), @t) -> tuple#2(@outq, ::(@t, @inq)) 1103.15/291.56 lineMult(@n, @l1, @l2) -> lineMult#1(@l1, @l2, @n) 1103.15/291.56 lineMult#1(::(@x, @xs), @l2, @n) -> lineMult#2(@l2, @n, @x, @xs) 1103.15/291.56 lineMult#1(nil, @l2, @n) -> nil 1103.15/291.56 lineMult#2(::(@y, @ys), @n, @x, @xs) -> ::(+(*(@x, @n), @y), lineMult(@n, @xs, @ys)) 1103.15/291.56 lineMult#2(nil, @n, @x, @xs) -> ::(*(@x, @n), lineMult(@n, @xs, nil)) 1103.15/291.56 matrixMult(@m1, @m2) -> matrixMult#1(@m1, @m2) 1103.15/291.56 matrixMult#1(::(@l, @ls), @m2) -> ::(computeLine(@l, @m2, nil), matrixMult(@ls, @m2)) 1103.15/291.56 matrixMult#1(nil, @m2) -> nil 1103.15/291.56 reverse(@xs) -> appendreverse(@xs, nil) 1103.15/291.56 1103.15/291.56 The (relative) TRS S consists of the following rules: 1103.15/291.56 1103.15/291.56 #add(#0, @y) -> @y 1103.15/291.56 #add(#neg(#s(#0)), @y) -> #pred(@y) 1103.15/291.56 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #add(#pos(#s(#0)), @y) -> #succ(@y) 1103.15/291.56 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1103.15/291.56 #mult(#0, #0) -> #0 1103.15/291.56 #mult(#0, #neg(@y)) -> #0 1103.15/291.56 #mult(#0, #pos(@y)) -> #0 1103.15/291.56 #mult(#neg(@x), #0) -> #0 1103.15/291.56 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #0) -> #0 1103.15/291.56 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1103.15/291.56 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1103.15/291.56 #natmult(#0, @y) -> #0 1103.15/291.56 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1103.15/291.56 #pred(#0) -> #neg(#s(#0)) 1103.15/291.56 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1103.15/291.56 #pred(#pos(#s(#0))) -> #0 1103.15/291.56 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1103.15/291.56 #succ(#0) -> #pos(#s(#0)) 1103.15/291.56 #succ(#neg(#s(#0))) -> #0 1103.15/291.56 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1103.15/291.56 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1103.15/291.56 1103.15/291.56 Rewrite Strategy: INNERMOST 1103.30/291.66 EOF