1121.56/291.65 WORST_CASE(Omega(n^1), ?) 1136.01/295.20 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1136.01/295.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1136.01/295.20 1136.01/295.20 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 (0) CpxRelTRS 1136.01/295.20 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 361 ms] 1136.01/295.20 (2) CpxRelTRS 1136.01/295.20 (3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1136.01/295.20 (4) TRS for Loop Detection 1136.01/295.20 (5) DecreasingLoopProof [LOWER BOUND(ID), 244 ms] 1136.01/295.20 (6) BEST 1136.01/295.20 (7) proven lower bound 1136.01/295.20 (8) LowerBoundPropagationProof [FINISHED, 0 ms] 1136.01/295.20 (9) BOUNDS(n^1, INF) 1136.01/295.20 (10) TRS for Loop Detection 1136.01/295.20 1136.01/295.20 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (0) 1136.01/295.20 Obligation: 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 1136.01/295.20 The TRS R consists of the following rules: 1136.01/295.20 1136.01/295.20 #abs(#0) -> #0 1136.01/295.20 #abs(#neg(@x)) -> #pos(@x) 1136.01/295.20 #abs(#pos(@x)) -> #pos(@x) 1136.01/295.20 #abs(#s(@x)) -> #pos(#s(@x)) 1136.01/295.20 *(@x, @y) -> #mult(@x, @y) 1136.01/295.20 +(@x, @y) -> #add(@x, @y) 1136.01/295.20 attach(@line, @m) -> attach#1(@line, @m) 1136.01/295.20 attach#1(::(@x, @xs), @m) -> attach#2(@m, @x, @xs) 1136.01/295.20 attach#1(nil, @m) -> nil 1136.01/295.20 attach#2(::(@l, @ls), @x, @xs) -> ::(::(@x, @l), attach(@xs, @ls)) 1136.01/295.20 attach#2(nil, @x, @xs) -> nil 1136.01/295.20 lineMult(@l, @m2) -> lineMult#1(@m2, @l) 1136.01/295.20 lineMult#1(::(@x, @xs), @l) -> ::(mult(@l, @x), lineMult(@l, @xs)) 1136.01/295.20 lineMult#1(nil, @l) -> nil 1136.01/295.20 m1(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil))), nil)) 1136.01/295.20 m2(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), nil)), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)), nil))) 1136.01/295.20 m3(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), nil)) 1136.01/295.20 m4(@x) -> ::(::(#abs(#pos(#s(#0))), nil), ::(::(#abs(#pos(#s(#s(#0)))), nil), ::(::(#abs(#pos(#s(#s(#s(#0))))), nil), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil), nil)))) 1136.01/295.20 makeBase(@m) -> makeBase#1(@m) 1136.01/295.20 makeBase#1(::(@l, @m')) -> mkBase(@l) 1136.01/295.20 makeBase#1(nil) -> nil 1136.01/295.20 matrixMult(@m1, @m2) -> matrixMult'(@m1, transAcc(@m2, makeBase(@m2))) 1136.01/295.20 matrixMult'(@m1, @m2) -> matrixMult'#1(@m1, @m2) 1136.01/295.20 matrixMult'#1(::(@l, @ls), @m2) -> ::(lineMult(@l, @m2), matrixMult'(@ls, @m2)) 1136.01/295.20 matrixMult'#1(nil, @m2) -> nil 1136.01/295.20 matrixMult3(@m1, @m2, @m3) -> matrixMult(matrixMult(@m1, @m2), @m3) 1136.01/295.20 matrixMultList(@acc, @mm) -> matrixMultList#1(@mm, @acc) 1136.01/295.20 matrixMultList#1(::(@m, @ms), @acc) -> matrixMultList(matrixMult(@acc, @m), @ms) 1136.01/295.20 matrixMultList#1(nil, @acc) -> @acc 1136.01/295.20 matrixMultOld(@m1, @m2) -> matrixMult'(@m1, transpose(@m2)) 1136.01/295.20 mkBase(@m) -> mkBase#1(@m) 1136.01/295.20 mkBase#1(::(@l, @m')) -> ::(nil, mkBase(@m')) 1136.01/295.20 mkBase#1(nil) -> nil 1136.01/295.20 mult(@l1, @l2) -> mult#1(@l1, @l2) 1136.01/295.20 mult#1(::(@x, @xs), @l2) -> mult#2(@l2, @x, @xs) 1136.01/295.20 mult#1(nil, @l2) -> #abs(#0) 1136.01/295.20 mult#2(::(@y, @ys), @x, @xs) -> +(*(@x, @y), mult(@xs, @ys)) 1136.01/295.20 mult#2(nil, @x, @xs) -> #abs(#0) 1136.01/295.20 split(@m) -> split#1(@m) 1136.01/295.20 split#1(::(@l, @ls)) -> split#2(@l, @ls) 1136.01/295.20 split#1(nil) -> tuple#2(nil, nil) 1136.01/295.20 split#2(::(@x, @xs), @ls) -> split#3(split(@ls), @x, @xs) 1136.01/295.20 split#2(nil, @ls) -> tuple#2(nil, nil) 1136.01/295.20 split#3(tuple#2(@ys, @m'), @x, @xs) -> tuple#2(::(@x, @ys), ::(@xs, @m')) 1136.01/295.20 transAcc(@m, @base) -> transAcc#1(@m, @base) 1136.01/295.20 transAcc#1(::(@l, @m'), @base) -> attach(@l, transAcc(@m', @base)) 1136.01/295.20 transAcc#1(nil, @base) -> @base 1136.01/295.20 transpose(@m) -> transpose#1(@m, @m) 1136.01/295.20 transpose#1(::(@xs, @xss), @m) -> transpose#2(split(@m)) 1136.01/295.20 transpose#1(nil, @m) -> nil 1136.01/295.20 transpose#2(tuple#2(@l, @m')) -> transpose#3(@m', @l) 1136.01/295.20 transpose#3(::(@y, @ys), @l) -> ::(@l, transpose(::(@y, @ys))) 1136.01/295.20 transpose#3(nil, @l) -> nil 1136.01/295.20 transpose'(@m) -> transAcc(@m, makeBase(@m)) 1136.01/295.20 1136.01/295.20 The (relative) TRS S consists of the following rules: 1136.01/295.20 1136.01/295.20 #add(#0, @y) -> @y 1136.01/295.20 #add(#neg(#s(#0)), @y) -> #pred(@y) 1136.01/295.20 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #add(#pos(#s(#0)), @y) -> #succ(@y) 1136.01/295.20 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #mult(#0, #0) -> #0 1136.01/295.20 #mult(#0, #neg(@y)) -> #0 1136.01/295.20 #mult(#0, #pos(@y)) -> #0 1136.01/295.20 #mult(#neg(@x), #0) -> #0 1136.01/295.20 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #0) -> #0 1136.01/295.20 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #natmult(#0, @y) -> #0 1136.01/295.20 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1136.01/295.20 #pred(#0) -> #neg(#s(#0)) 1136.01/295.20 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1136.01/295.20 #pred(#pos(#s(#0))) -> #0 1136.01/295.20 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1136.01/295.20 #succ(#0) -> #pos(#s(#0)) 1136.01/295.20 #succ(#neg(#s(#0))) -> #0 1136.01/295.20 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1136.01/295.20 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1136.01/295.20 1136.01/295.20 Rewrite Strategy: INNERMOST 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 1136.01/295.20 proved termination of relative rules 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (2) 1136.01/295.20 Obligation: 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 1136.01/295.20 The TRS R consists of the following rules: 1136.01/295.20 1136.01/295.20 #abs(#0) -> #0 1136.01/295.20 #abs(#neg(@x)) -> #pos(@x) 1136.01/295.20 #abs(#pos(@x)) -> #pos(@x) 1136.01/295.20 #abs(#s(@x)) -> #pos(#s(@x)) 1136.01/295.20 *(@x, @y) -> #mult(@x, @y) 1136.01/295.20 +(@x, @y) -> #add(@x, @y) 1136.01/295.20 attach(@line, @m) -> attach#1(@line, @m) 1136.01/295.20 attach#1(::(@x, @xs), @m) -> attach#2(@m, @x, @xs) 1136.01/295.20 attach#1(nil, @m) -> nil 1136.01/295.20 attach#2(::(@l, @ls), @x, @xs) -> ::(::(@x, @l), attach(@xs, @ls)) 1136.01/295.20 attach#2(nil, @x, @xs) -> nil 1136.01/295.20 lineMult(@l, @m2) -> lineMult#1(@m2, @l) 1136.01/295.20 lineMult#1(::(@x, @xs), @l) -> ::(mult(@l, @x), lineMult(@l, @xs)) 1136.01/295.20 lineMult#1(nil, @l) -> nil 1136.01/295.20 m1(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil))), nil)) 1136.01/295.20 m2(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), nil)), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)), nil))) 1136.01/295.20 m3(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), nil)) 1136.01/295.20 m4(@x) -> ::(::(#abs(#pos(#s(#0))), nil), ::(::(#abs(#pos(#s(#s(#0)))), nil), ::(::(#abs(#pos(#s(#s(#s(#0))))), nil), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil), nil)))) 1136.01/295.20 makeBase(@m) -> makeBase#1(@m) 1136.01/295.20 makeBase#1(::(@l, @m')) -> mkBase(@l) 1136.01/295.20 makeBase#1(nil) -> nil 1136.01/295.20 matrixMult(@m1, @m2) -> matrixMult'(@m1, transAcc(@m2, makeBase(@m2))) 1136.01/295.20 matrixMult'(@m1, @m2) -> matrixMult'#1(@m1, @m2) 1136.01/295.20 matrixMult'#1(::(@l, @ls), @m2) -> ::(lineMult(@l, @m2), matrixMult'(@ls, @m2)) 1136.01/295.20 matrixMult'#1(nil, @m2) -> nil 1136.01/295.20 matrixMult3(@m1, @m2, @m3) -> matrixMult(matrixMult(@m1, @m2), @m3) 1136.01/295.20 matrixMultList(@acc, @mm) -> matrixMultList#1(@mm, @acc) 1136.01/295.20 matrixMultList#1(::(@m, @ms), @acc) -> matrixMultList(matrixMult(@acc, @m), @ms) 1136.01/295.20 matrixMultList#1(nil, @acc) -> @acc 1136.01/295.20 matrixMultOld(@m1, @m2) -> matrixMult'(@m1, transpose(@m2)) 1136.01/295.20 mkBase(@m) -> mkBase#1(@m) 1136.01/295.20 mkBase#1(::(@l, @m')) -> ::(nil, mkBase(@m')) 1136.01/295.20 mkBase#1(nil) -> nil 1136.01/295.20 mult(@l1, @l2) -> mult#1(@l1, @l2) 1136.01/295.20 mult#1(::(@x, @xs), @l2) -> mult#2(@l2, @x, @xs) 1136.01/295.20 mult#1(nil, @l2) -> #abs(#0) 1136.01/295.20 mult#2(::(@y, @ys), @x, @xs) -> +(*(@x, @y), mult(@xs, @ys)) 1136.01/295.20 mult#2(nil, @x, @xs) -> #abs(#0) 1136.01/295.20 split(@m) -> split#1(@m) 1136.01/295.20 split#1(::(@l, @ls)) -> split#2(@l, @ls) 1136.01/295.20 split#1(nil) -> tuple#2(nil, nil) 1136.01/295.20 split#2(::(@x, @xs), @ls) -> split#3(split(@ls), @x, @xs) 1136.01/295.20 split#2(nil, @ls) -> tuple#2(nil, nil) 1136.01/295.20 split#3(tuple#2(@ys, @m'), @x, @xs) -> tuple#2(::(@x, @ys), ::(@xs, @m')) 1136.01/295.20 transAcc(@m, @base) -> transAcc#1(@m, @base) 1136.01/295.20 transAcc#1(::(@l, @m'), @base) -> attach(@l, transAcc(@m', @base)) 1136.01/295.20 transAcc#1(nil, @base) -> @base 1136.01/295.20 transpose(@m) -> transpose#1(@m, @m) 1136.01/295.20 transpose#1(::(@xs, @xss), @m) -> transpose#2(split(@m)) 1136.01/295.20 transpose#1(nil, @m) -> nil 1136.01/295.20 transpose#2(tuple#2(@l, @m')) -> transpose#3(@m', @l) 1136.01/295.20 transpose#3(::(@y, @ys), @l) -> ::(@l, transpose(::(@y, @ys))) 1136.01/295.20 transpose#3(nil, @l) -> nil 1136.01/295.20 transpose'(@m) -> transAcc(@m, makeBase(@m)) 1136.01/295.20 1136.01/295.20 The (relative) TRS S consists of the following rules: 1136.01/295.20 1136.01/295.20 #add(#0, @y) -> @y 1136.01/295.20 #add(#neg(#s(#0)), @y) -> #pred(@y) 1136.01/295.20 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #add(#pos(#s(#0)), @y) -> #succ(@y) 1136.01/295.20 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #mult(#0, #0) -> #0 1136.01/295.20 #mult(#0, #neg(@y)) -> #0 1136.01/295.20 #mult(#0, #pos(@y)) -> #0 1136.01/295.20 #mult(#neg(@x), #0) -> #0 1136.01/295.20 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #0) -> #0 1136.01/295.20 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #natmult(#0, @y) -> #0 1136.01/295.20 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1136.01/295.20 #pred(#0) -> #neg(#s(#0)) 1136.01/295.20 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1136.01/295.20 #pred(#pos(#s(#0))) -> #0 1136.01/295.20 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1136.01/295.20 #succ(#0) -> #pos(#s(#0)) 1136.01/295.20 #succ(#neg(#s(#0))) -> #0 1136.01/295.20 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1136.01/295.20 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1136.01/295.20 1136.01/295.20 Rewrite Strategy: INNERMOST 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1136.01/295.20 Transformed a relative TRS into a decreasing-loop problem. 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (4) 1136.01/295.20 Obligation: 1136.01/295.20 Analyzing the following TRS for decreasing loops: 1136.01/295.20 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 1136.01/295.20 The TRS R consists of the following rules: 1136.01/295.20 1136.01/295.20 #abs(#0) -> #0 1136.01/295.20 #abs(#neg(@x)) -> #pos(@x) 1136.01/295.20 #abs(#pos(@x)) -> #pos(@x) 1136.01/295.20 #abs(#s(@x)) -> #pos(#s(@x)) 1136.01/295.20 *(@x, @y) -> #mult(@x, @y) 1136.01/295.20 +(@x, @y) -> #add(@x, @y) 1136.01/295.20 attach(@line, @m) -> attach#1(@line, @m) 1136.01/295.20 attach#1(::(@x, @xs), @m) -> attach#2(@m, @x, @xs) 1136.01/295.20 attach#1(nil, @m) -> nil 1136.01/295.20 attach#2(::(@l, @ls), @x, @xs) -> ::(::(@x, @l), attach(@xs, @ls)) 1136.01/295.20 attach#2(nil, @x, @xs) -> nil 1136.01/295.20 lineMult(@l, @m2) -> lineMult#1(@m2, @l) 1136.01/295.20 lineMult#1(::(@x, @xs), @l) -> ::(mult(@l, @x), lineMult(@l, @xs)) 1136.01/295.20 lineMult#1(nil, @l) -> nil 1136.01/295.20 m1(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil))), nil)) 1136.01/295.20 m2(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), nil)), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)), nil))) 1136.01/295.20 m3(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), nil)) 1136.01/295.20 m4(@x) -> ::(::(#abs(#pos(#s(#0))), nil), ::(::(#abs(#pos(#s(#s(#0)))), nil), ::(::(#abs(#pos(#s(#s(#s(#0))))), nil), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil), nil)))) 1136.01/295.20 makeBase(@m) -> makeBase#1(@m) 1136.01/295.20 makeBase#1(::(@l, @m')) -> mkBase(@l) 1136.01/295.20 makeBase#1(nil) -> nil 1136.01/295.20 matrixMult(@m1, @m2) -> matrixMult'(@m1, transAcc(@m2, makeBase(@m2))) 1136.01/295.20 matrixMult'(@m1, @m2) -> matrixMult'#1(@m1, @m2) 1136.01/295.20 matrixMult'#1(::(@l, @ls), @m2) -> ::(lineMult(@l, @m2), matrixMult'(@ls, @m2)) 1136.01/295.20 matrixMult'#1(nil, @m2) -> nil 1136.01/295.20 matrixMult3(@m1, @m2, @m3) -> matrixMult(matrixMult(@m1, @m2), @m3) 1136.01/295.20 matrixMultList(@acc, @mm) -> matrixMultList#1(@mm, @acc) 1136.01/295.20 matrixMultList#1(::(@m, @ms), @acc) -> matrixMultList(matrixMult(@acc, @m), @ms) 1136.01/295.20 matrixMultList#1(nil, @acc) -> @acc 1136.01/295.20 matrixMultOld(@m1, @m2) -> matrixMult'(@m1, transpose(@m2)) 1136.01/295.20 mkBase(@m) -> mkBase#1(@m) 1136.01/295.20 mkBase#1(::(@l, @m')) -> ::(nil, mkBase(@m')) 1136.01/295.20 mkBase#1(nil) -> nil 1136.01/295.20 mult(@l1, @l2) -> mult#1(@l1, @l2) 1136.01/295.20 mult#1(::(@x, @xs), @l2) -> mult#2(@l2, @x, @xs) 1136.01/295.20 mult#1(nil, @l2) -> #abs(#0) 1136.01/295.20 mult#2(::(@y, @ys), @x, @xs) -> +(*(@x, @y), mult(@xs, @ys)) 1136.01/295.20 mult#2(nil, @x, @xs) -> #abs(#0) 1136.01/295.20 split(@m) -> split#1(@m) 1136.01/295.20 split#1(::(@l, @ls)) -> split#2(@l, @ls) 1136.01/295.20 split#1(nil) -> tuple#2(nil, nil) 1136.01/295.20 split#2(::(@x, @xs), @ls) -> split#3(split(@ls), @x, @xs) 1136.01/295.20 split#2(nil, @ls) -> tuple#2(nil, nil) 1136.01/295.20 split#3(tuple#2(@ys, @m'), @x, @xs) -> tuple#2(::(@x, @ys), ::(@xs, @m')) 1136.01/295.20 transAcc(@m, @base) -> transAcc#1(@m, @base) 1136.01/295.20 transAcc#1(::(@l, @m'), @base) -> attach(@l, transAcc(@m', @base)) 1136.01/295.20 transAcc#1(nil, @base) -> @base 1136.01/295.20 transpose(@m) -> transpose#1(@m, @m) 1136.01/295.20 transpose#1(::(@xs, @xss), @m) -> transpose#2(split(@m)) 1136.01/295.20 transpose#1(nil, @m) -> nil 1136.01/295.20 transpose#2(tuple#2(@l, @m')) -> transpose#3(@m', @l) 1136.01/295.20 transpose#3(::(@y, @ys), @l) -> ::(@l, transpose(::(@y, @ys))) 1136.01/295.20 transpose#3(nil, @l) -> nil 1136.01/295.20 transpose'(@m) -> transAcc(@m, makeBase(@m)) 1136.01/295.20 1136.01/295.20 The (relative) TRS S consists of the following rules: 1136.01/295.20 1136.01/295.20 #add(#0, @y) -> @y 1136.01/295.20 #add(#neg(#s(#0)), @y) -> #pred(@y) 1136.01/295.20 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #add(#pos(#s(#0)), @y) -> #succ(@y) 1136.01/295.20 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #mult(#0, #0) -> #0 1136.01/295.20 #mult(#0, #neg(@y)) -> #0 1136.01/295.20 #mult(#0, #pos(@y)) -> #0 1136.01/295.20 #mult(#neg(@x), #0) -> #0 1136.01/295.20 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #0) -> #0 1136.01/295.20 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #natmult(#0, @y) -> #0 1136.01/295.20 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1136.01/295.20 #pred(#0) -> #neg(#s(#0)) 1136.01/295.20 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1136.01/295.20 #pred(#pos(#s(#0))) -> #0 1136.01/295.20 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1136.01/295.20 #succ(#0) -> #pos(#s(#0)) 1136.01/295.20 #succ(#neg(#s(#0))) -> #0 1136.01/295.20 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1136.01/295.20 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1136.01/295.20 1136.01/295.20 Rewrite Strategy: INNERMOST 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (5) DecreasingLoopProof (LOWER BOUND(ID)) 1136.01/295.20 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1136.01/295.20 1136.01/295.20 The rewrite sequence 1136.01/295.20 1136.01/295.20 lineMult#1(::(@x, @xs), @l) ->^+ ::(mult(@l, @x), lineMult#1(@xs, @l)) 1136.01/295.20 1136.01/295.20 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 1136.01/295.20 1136.01/295.20 The pumping substitution is [@xs / ::(@x, @xs)]. 1136.01/295.20 1136.01/295.20 The result substitution is [ ]. 1136.01/295.20 1136.01/295.20 1136.01/295.20 1136.01/295.20 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (6) 1136.01/295.20 Complex Obligation (BEST) 1136.01/295.20 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (7) 1136.01/295.20 Obligation: 1136.01/295.20 Proved the lower bound n^1 for the following obligation: 1136.01/295.20 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 1136.01/295.20 The TRS R consists of the following rules: 1136.01/295.20 1136.01/295.20 #abs(#0) -> #0 1136.01/295.20 #abs(#neg(@x)) -> #pos(@x) 1136.01/295.20 #abs(#pos(@x)) -> #pos(@x) 1136.01/295.20 #abs(#s(@x)) -> #pos(#s(@x)) 1136.01/295.20 *(@x, @y) -> #mult(@x, @y) 1136.01/295.20 +(@x, @y) -> #add(@x, @y) 1136.01/295.20 attach(@line, @m) -> attach#1(@line, @m) 1136.01/295.20 attach#1(::(@x, @xs), @m) -> attach#2(@m, @x, @xs) 1136.01/295.20 attach#1(nil, @m) -> nil 1136.01/295.20 attach#2(::(@l, @ls), @x, @xs) -> ::(::(@x, @l), attach(@xs, @ls)) 1136.01/295.20 attach#2(nil, @x, @xs) -> nil 1136.01/295.20 lineMult(@l, @m2) -> lineMult#1(@m2, @l) 1136.01/295.20 lineMult#1(::(@x, @xs), @l) -> ::(mult(@l, @x), lineMult(@l, @xs)) 1136.01/295.20 lineMult#1(nil, @l) -> nil 1136.01/295.20 m1(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil))), nil)) 1136.01/295.20 m2(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), nil)), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)), nil))) 1136.01/295.20 m3(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), nil)) 1136.01/295.20 m4(@x) -> ::(::(#abs(#pos(#s(#0))), nil), ::(::(#abs(#pos(#s(#s(#0)))), nil), ::(::(#abs(#pos(#s(#s(#s(#0))))), nil), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil), nil)))) 1136.01/295.20 makeBase(@m) -> makeBase#1(@m) 1136.01/295.20 makeBase#1(::(@l, @m')) -> mkBase(@l) 1136.01/295.20 makeBase#1(nil) -> nil 1136.01/295.20 matrixMult(@m1, @m2) -> matrixMult'(@m1, transAcc(@m2, makeBase(@m2))) 1136.01/295.20 matrixMult'(@m1, @m2) -> matrixMult'#1(@m1, @m2) 1136.01/295.20 matrixMult'#1(::(@l, @ls), @m2) -> ::(lineMult(@l, @m2), matrixMult'(@ls, @m2)) 1136.01/295.20 matrixMult'#1(nil, @m2) -> nil 1136.01/295.20 matrixMult3(@m1, @m2, @m3) -> matrixMult(matrixMult(@m1, @m2), @m3) 1136.01/295.20 matrixMultList(@acc, @mm) -> matrixMultList#1(@mm, @acc) 1136.01/295.20 matrixMultList#1(::(@m, @ms), @acc) -> matrixMultList(matrixMult(@acc, @m), @ms) 1136.01/295.20 matrixMultList#1(nil, @acc) -> @acc 1136.01/295.20 matrixMultOld(@m1, @m2) -> matrixMult'(@m1, transpose(@m2)) 1136.01/295.20 mkBase(@m) -> mkBase#1(@m) 1136.01/295.20 mkBase#1(::(@l, @m')) -> ::(nil, mkBase(@m')) 1136.01/295.20 mkBase#1(nil) -> nil 1136.01/295.20 mult(@l1, @l2) -> mult#1(@l1, @l2) 1136.01/295.20 mult#1(::(@x, @xs), @l2) -> mult#2(@l2, @x, @xs) 1136.01/295.20 mult#1(nil, @l2) -> #abs(#0) 1136.01/295.20 mult#2(::(@y, @ys), @x, @xs) -> +(*(@x, @y), mult(@xs, @ys)) 1136.01/295.20 mult#2(nil, @x, @xs) -> #abs(#0) 1136.01/295.20 split(@m) -> split#1(@m) 1136.01/295.20 split#1(::(@l, @ls)) -> split#2(@l, @ls) 1136.01/295.20 split#1(nil) -> tuple#2(nil, nil) 1136.01/295.20 split#2(::(@x, @xs), @ls) -> split#3(split(@ls), @x, @xs) 1136.01/295.20 split#2(nil, @ls) -> tuple#2(nil, nil) 1136.01/295.20 split#3(tuple#2(@ys, @m'), @x, @xs) -> tuple#2(::(@x, @ys), ::(@xs, @m')) 1136.01/295.20 transAcc(@m, @base) -> transAcc#1(@m, @base) 1136.01/295.20 transAcc#1(::(@l, @m'), @base) -> attach(@l, transAcc(@m', @base)) 1136.01/295.20 transAcc#1(nil, @base) -> @base 1136.01/295.20 transpose(@m) -> transpose#1(@m, @m) 1136.01/295.20 transpose#1(::(@xs, @xss), @m) -> transpose#2(split(@m)) 1136.01/295.20 transpose#1(nil, @m) -> nil 1136.01/295.20 transpose#2(tuple#2(@l, @m')) -> transpose#3(@m', @l) 1136.01/295.20 transpose#3(::(@y, @ys), @l) -> ::(@l, transpose(::(@y, @ys))) 1136.01/295.20 transpose#3(nil, @l) -> nil 1136.01/295.20 transpose'(@m) -> transAcc(@m, makeBase(@m)) 1136.01/295.20 1136.01/295.20 The (relative) TRS S consists of the following rules: 1136.01/295.20 1136.01/295.20 #add(#0, @y) -> @y 1136.01/295.20 #add(#neg(#s(#0)), @y) -> #pred(@y) 1136.01/295.20 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #add(#pos(#s(#0)), @y) -> #succ(@y) 1136.01/295.20 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1136.01/295.20 #mult(#0, #0) -> #0 1136.01/295.20 #mult(#0, #neg(@y)) -> #0 1136.01/295.20 #mult(#0, #pos(@y)) -> #0 1136.01/295.20 #mult(#neg(@x), #0) -> #0 1136.01/295.20 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #0) -> #0 1136.01/295.20 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.20 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.20 #natmult(#0, @y) -> #0 1136.01/295.20 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1136.01/295.20 #pred(#0) -> #neg(#s(#0)) 1136.01/295.20 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1136.01/295.20 #pred(#pos(#s(#0))) -> #0 1136.01/295.20 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1136.01/295.20 #succ(#0) -> #pos(#s(#0)) 1136.01/295.20 #succ(#neg(#s(#0))) -> #0 1136.01/295.20 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1136.01/295.20 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1136.01/295.20 1136.01/295.20 Rewrite Strategy: INNERMOST 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (8) LowerBoundPropagationProof (FINISHED) 1136.01/295.20 Propagated lower bound. 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (9) 1136.01/295.20 BOUNDS(n^1, INF) 1136.01/295.20 1136.01/295.20 ---------------------------------------- 1136.01/295.20 1136.01/295.20 (10) 1136.01/295.20 Obligation: 1136.01/295.20 Analyzing the following TRS for decreasing loops: 1136.01/295.20 1136.01/295.20 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1136.01/295.20 1136.01/295.20 1136.01/295.20 The TRS R consists of the following rules: 1136.01/295.20 1136.01/295.20 #abs(#0) -> #0 1136.01/295.20 #abs(#neg(@x)) -> #pos(@x) 1136.01/295.20 #abs(#pos(@x)) -> #pos(@x) 1136.01/295.20 #abs(#s(@x)) -> #pos(#s(@x)) 1136.01/295.20 *(@x, @y) -> #mult(@x, @y) 1136.01/295.20 +(@x, @y) -> #add(@x, @y) 1136.01/295.20 attach(@line, @m) -> attach#1(@line, @m) 1136.01/295.20 attach#1(::(@x, @xs), @m) -> attach#2(@m, @x, @xs) 1136.01/295.20 attach#1(nil, @m) -> nil 1136.01/295.20 attach#2(::(@l, @ls), @x, @xs) -> ::(::(@x, @l), attach(@xs, @ls)) 1136.01/295.20 attach#2(nil, @x, @xs) -> nil 1136.01/295.20 lineMult(@l, @m2) -> lineMult#1(@m2, @l) 1136.01/295.20 lineMult#1(::(@x, @xs), @l) -> ::(mult(@l, @x), lineMult(@l, @xs)) 1136.01/295.20 lineMult#1(nil, @l) -> nil 1136.01/295.20 m1(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil))), nil)) 1136.01/295.20 m2(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), nil)), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)), nil))) 1136.01/295.20 m3(@x) -> ::(::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), ::(::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#0))))), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), nil)))), nil)) 1136.01/295.20 m4(@x) -> ::(::(#abs(#pos(#s(#0))), nil), ::(::(#abs(#pos(#s(#s(#0)))), nil), ::(::(#abs(#pos(#s(#s(#s(#0))))), nil), ::(::(#abs(#pos(#s(#s(#s(#s(#0)))))), nil), nil)))) 1136.01/295.20 makeBase(@m) -> makeBase#1(@m) 1136.01/295.20 makeBase#1(::(@l, @m')) -> mkBase(@l) 1136.01/295.20 makeBase#1(nil) -> nil 1136.01/295.20 matrixMult(@m1, @m2) -> matrixMult'(@m1, transAcc(@m2, makeBase(@m2))) 1136.01/295.20 matrixMult'(@m1, @m2) -> matrixMult'#1(@m1, @m2) 1136.01/295.20 matrixMult'#1(::(@l, @ls), @m2) -> ::(lineMult(@l, @m2), matrixMult'(@ls, @m2)) 1136.01/295.20 matrixMult'#1(nil, @m2) -> nil 1136.01/295.20 matrixMult3(@m1, @m2, @m3) -> matrixMult(matrixMult(@m1, @m2), @m3) 1136.01/295.20 matrixMultList(@acc, @mm) -> matrixMultList#1(@mm, @acc) 1136.01/295.20 matrixMultList#1(::(@m, @ms), @acc) -> matrixMultList(matrixMult(@acc, @m), @ms) 1136.01/295.20 matrixMultList#1(nil, @acc) -> @acc 1136.01/295.20 matrixMultOld(@m1, @m2) -> matrixMult'(@m1, transpose(@m2)) 1136.01/295.20 mkBase(@m) -> mkBase#1(@m) 1136.01/295.20 mkBase#1(::(@l, @m')) -> ::(nil, mkBase(@m')) 1136.01/295.20 mkBase#1(nil) -> nil 1136.01/295.20 mult(@l1, @l2) -> mult#1(@l1, @l2) 1136.01/295.20 mult#1(::(@x, @xs), @l2) -> mult#2(@l2, @x, @xs) 1136.01/295.20 mult#1(nil, @l2) -> #abs(#0) 1136.01/295.20 mult#2(::(@y, @ys), @x, @xs) -> +(*(@x, @y), mult(@xs, @ys)) 1136.01/295.20 mult#2(nil, @x, @xs) -> #abs(#0) 1136.01/295.20 split(@m) -> split#1(@m) 1136.01/295.20 split#1(::(@l, @ls)) -> split#2(@l, @ls) 1136.01/295.20 split#1(nil) -> tuple#2(nil, nil) 1136.01/295.20 split#2(::(@x, @xs), @ls) -> split#3(split(@ls), @x, @xs) 1136.01/295.20 split#2(nil, @ls) -> tuple#2(nil, nil) 1136.01/295.20 split#3(tuple#2(@ys, @m'), @x, @xs) -> tuple#2(::(@x, @ys), ::(@xs, @m')) 1136.01/295.21 transAcc(@m, @base) -> transAcc#1(@m, @base) 1136.01/295.21 transAcc#1(::(@l, @m'), @base) -> attach(@l, transAcc(@m', @base)) 1136.01/295.21 transAcc#1(nil, @base) -> @base 1136.01/295.21 transpose(@m) -> transpose#1(@m, @m) 1136.01/295.21 transpose#1(::(@xs, @xss), @m) -> transpose#2(split(@m)) 1136.01/295.21 transpose#1(nil, @m) -> nil 1136.01/295.21 transpose#2(tuple#2(@l, @m')) -> transpose#3(@m', @l) 1136.01/295.21 transpose#3(::(@y, @ys), @l) -> ::(@l, transpose(::(@y, @ys))) 1136.01/295.21 transpose#3(nil, @l) -> nil 1136.01/295.21 transpose'(@m) -> transAcc(@m, makeBase(@m)) 1136.01/295.21 1136.01/295.21 The (relative) TRS S consists of the following rules: 1136.01/295.21 1136.01/295.21 #add(#0, @y) -> @y 1136.01/295.21 #add(#neg(#s(#0)), @y) -> #pred(@y) 1136.01/295.21 #add(#neg(#s(#s(@x))), @y) -> #pred(#add(#pos(#s(@x)), @y)) 1136.01/295.21 #add(#pos(#s(#0)), @y) -> #succ(@y) 1136.01/295.21 #add(#pos(#s(#s(@x))), @y) -> #succ(#add(#pos(#s(@x)), @y)) 1136.01/295.21 #mult(#0, #0) -> #0 1136.01/295.21 #mult(#0, #neg(@y)) -> #0 1136.01/295.21 #mult(#0, #pos(@y)) -> #0 1136.01/295.21 #mult(#neg(@x), #0) -> #0 1136.01/295.21 #mult(#neg(@x), #neg(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.21 #mult(#neg(@x), #pos(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.21 #mult(#pos(@x), #0) -> #0 1136.01/295.21 #mult(#pos(@x), #neg(@y)) -> #neg(#natmult(@x, @y)) 1136.01/295.21 #mult(#pos(@x), #pos(@y)) -> #pos(#natmult(@x, @y)) 1136.01/295.21 #natmult(#0, @y) -> #0 1136.01/295.21 #natmult(#s(@x), @y) -> #add(#pos(@y), #natmult(@x, @y)) 1136.01/295.21 #pred(#0) -> #neg(#s(#0)) 1136.01/295.21 #pred(#neg(#s(@x))) -> #neg(#s(#s(@x))) 1136.01/295.21 #pred(#pos(#s(#0))) -> #0 1136.01/295.21 #pred(#pos(#s(#s(@x)))) -> #pos(#s(@x)) 1136.01/295.21 #succ(#0) -> #pos(#s(#0)) 1136.01/295.21 #succ(#neg(#s(#0))) -> #0 1136.01/295.21 #succ(#neg(#s(#s(@x)))) -> #neg(#s(@x)) 1136.01/295.21 #succ(#pos(#s(@x))) -> #pos(#s(#s(@x))) 1136.01/295.21 1136.01/295.21 Rewrite Strategy: INNERMOST 1136.10/295.28 EOF