1077.11/291.60 WORST_CASE(Omega(n^1), ?) 1077.11/291.62 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1077.11/291.62 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1077.11/291.62 1077.11/291.62 1077.11/291.62 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1077.11/291.62 1077.11/291.62 (0) CpxTRS 1077.11/291.62 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1077.11/291.62 (2) TRS for Loop Detection 1077.11/291.62 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1077.11/291.62 (4) BEST 1077.11/291.62 (5) proven lower bound 1077.11/291.62 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1077.11/291.62 (7) BOUNDS(n^1, INF) 1077.11/291.62 (8) TRS for Loop Detection 1077.11/291.62 1077.11/291.62 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (0) 1077.11/291.62 Obligation: 1077.11/291.62 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1077.11/291.62 1077.11/291.62 1077.11/291.62 The TRS R consists of the following rules: 1077.11/291.62 1077.11/291.62 0(#) -> # 1077.11/291.62 +(x, #) -> x 1077.11/291.62 +(#, x) -> x 1077.11/291.62 +(0(x), 0(y)) -> 0(+(x, y)) 1077.11/291.62 +(0(x), 1(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 0(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 1(y)) -> 0(+(+(x, y), 1(#))) 1077.11/291.62 +(x, +(y, z)) -> +(+(x, y), z) 1077.11/291.62 -(x, #) -> x 1077.11/291.62 -(#, x) -> # 1077.11/291.62 -(0(x), 0(y)) -> 0(-(x, y)) 1077.11/291.62 -(0(x), 1(y)) -> 1(-(-(x, y), 1(#))) 1077.11/291.62 -(1(x), 0(y)) -> 1(-(x, y)) 1077.11/291.62 -(1(x), 1(y)) -> 0(-(x, y)) 1077.11/291.62 not(false) -> true 1077.11/291.62 not(true) -> false 1077.11/291.62 and(x, true) -> x 1077.11/291.62 and(x, false) -> false 1077.11/291.62 if(true, x, y) -> x 1077.11/291.62 if(false, x, y) -> y 1077.11/291.62 ge(0(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(0(x), 1(y)) -> not(ge(y, x)) 1077.11/291.62 ge(1(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(1(x), 1(y)) -> ge(x, y) 1077.11/291.62 ge(x, #) -> true 1077.11/291.62 ge(#, 1(x)) -> false 1077.11/291.62 ge(#, 0(x)) -> ge(#, x) 1077.11/291.62 val(l(x)) -> x 1077.11/291.62 val(n(x, y, z)) -> x 1077.11/291.62 min(l(x)) -> x 1077.11/291.62 min(n(x, y, z)) -> min(y) 1077.11/291.62 max(l(x)) -> x 1077.11/291.62 max(n(x, y, z)) -> max(z) 1077.11/291.62 bs(l(x)) -> true 1077.11/291.62 bs(n(x, y, z)) -> and(and(ge(x, max(y)), ge(min(z), x)), and(bs(y), bs(z))) 1077.11/291.62 size(l(x)) -> 1(#) 1077.11/291.62 size(n(x, y, z)) -> +(+(size(x), size(y)), 1(#)) 1077.11/291.62 wb(l(x)) -> true 1077.11/291.62 wb(n(x, y, z)) -> and(if(ge(size(y), size(z)), ge(1(#), -(size(y), size(z))), ge(1(#), -(size(z), size(y)))), and(wb(y), wb(z))) 1077.11/291.62 1077.11/291.62 S is empty. 1077.11/291.62 Rewrite Strategy: FULL 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1077.11/291.62 Transformed a relative TRS into a decreasing-loop problem. 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (2) 1077.11/291.62 Obligation: 1077.11/291.62 Analyzing the following TRS for decreasing loops: 1077.11/291.62 1077.11/291.62 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1077.11/291.62 1077.11/291.62 1077.11/291.62 The TRS R consists of the following rules: 1077.11/291.62 1077.11/291.62 0(#) -> # 1077.11/291.62 +(x, #) -> x 1077.11/291.62 +(#, x) -> x 1077.11/291.62 +(0(x), 0(y)) -> 0(+(x, y)) 1077.11/291.62 +(0(x), 1(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 0(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 1(y)) -> 0(+(+(x, y), 1(#))) 1077.11/291.62 +(x, +(y, z)) -> +(+(x, y), z) 1077.11/291.62 -(x, #) -> x 1077.11/291.62 -(#, x) -> # 1077.11/291.62 -(0(x), 0(y)) -> 0(-(x, y)) 1077.11/291.62 -(0(x), 1(y)) -> 1(-(-(x, y), 1(#))) 1077.11/291.62 -(1(x), 0(y)) -> 1(-(x, y)) 1077.11/291.62 -(1(x), 1(y)) -> 0(-(x, y)) 1077.11/291.62 not(false) -> true 1077.11/291.62 not(true) -> false 1077.11/291.62 and(x, true) -> x 1077.11/291.62 and(x, false) -> false 1077.11/291.62 if(true, x, y) -> x 1077.11/291.62 if(false, x, y) -> y 1077.11/291.62 ge(0(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(0(x), 1(y)) -> not(ge(y, x)) 1077.11/291.62 ge(1(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(1(x), 1(y)) -> ge(x, y) 1077.11/291.62 ge(x, #) -> true 1077.11/291.62 ge(#, 1(x)) -> false 1077.11/291.62 ge(#, 0(x)) -> ge(#, x) 1077.11/291.62 val(l(x)) -> x 1077.11/291.62 val(n(x, y, z)) -> x 1077.11/291.62 min(l(x)) -> x 1077.11/291.62 min(n(x, y, z)) -> min(y) 1077.11/291.62 max(l(x)) -> x 1077.11/291.62 max(n(x, y, z)) -> max(z) 1077.11/291.62 bs(l(x)) -> true 1077.11/291.62 bs(n(x, y, z)) -> and(and(ge(x, max(y)), ge(min(z), x)), and(bs(y), bs(z))) 1077.11/291.62 size(l(x)) -> 1(#) 1077.11/291.62 size(n(x, y, z)) -> +(+(size(x), size(y)), 1(#)) 1077.11/291.62 wb(l(x)) -> true 1077.11/291.62 wb(n(x, y, z)) -> and(if(ge(size(y), size(z)), ge(1(#), -(size(y), size(z))), ge(1(#), -(size(z), size(y)))), and(wb(y), wb(z))) 1077.11/291.62 1077.11/291.62 S is empty. 1077.11/291.62 Rewrite Strategy: FULL 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1077.11/291.62 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1077.11/291.62 1077.11/291.62 The rewrite sequence 1077.11/291.62 1077.11/291.62 max(n(x, y, z)) ->^+ max(z) 1077.11/291.62 1077.11/291.62 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1077.11/291.62 1077.11/291.62 The pumping substitution is [z / n(x, y, z)]. 1077.11/291.62 1077.11/291.62 The result substitution is [ ]. 1077.11/291.62 1077.11/291.62 1077.11/291.62 1077.11/291.62 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (4) 1077.11/291.62 Complex Obligation (BEST) 1077.11/291.62 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (5) 1077.11/291.62 Obligation: 1077.11/291.62 Proved the lower bound n^1 for the following obligation: 1077.11/291.62 1077.11/291.62 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1077.11/291.62 1077.11/291.62 1077.11/291.62 The TRS R consists of the following rules: 1077.11/291.62 1077.11/291.62 0(#) -> # 1077.11/291.62 +(x, #) -> x 1077.11/291.62 +(#, x) -> x 1077.11/291.62 +(0(x), 0(y)) -> 0(+(x, y)) 1077.11/291.62 +(0(x), 1(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 0(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 1(y)) -> 0(+(+(x, y), 1(#))) 1077.11/291.62 +(x, +(y, z)) -> +(+(x, y), z) 1077.11/291.62 -(x, #) -> x 1077.11/291.62 -(#, x) -> # 1077.11/291.62 -(0(x), 0(y)) -> 0(-(x, y)) 1077.11/291.62 -(0(x), 1(y)) -> 1(-(-(x, y), 1(#))) 1077.11/291.62 -(1(x), 0(y)) -> 1(-(x, y)) 1077.11/291.62 -(1(x), 1(y)) -> 0(-(x, y)) 1077.11/291.62 not(false) -> true 1077.11/291.62 not(true) -> false 1077.11/291.62 and(x, true) -> x 1077.11/291.62 and(x, false) -> false 1077.11/291.62 if(true, x, y) -> x 1077.11/291.62 if(false, x, y) -> y 1077.11/291.62 ge(0(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(0(x), 1(y)) -> not(ge(y, x)) 1077.11/291.62 ge(1(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(1(x), 1(y)) -> ge(x, y) 1077.11/291.62 ge(x, #) -> true 1077.11/291.62 ge(#, 1(x)) -> false 1077.11/291.62 ge(#, 0(x)) -> ge(#, x) 1077.11/291.62 val(l(x)) -> x 1077.11/291.62 val(n(x, y, z)) -> x 1077.11/291.62 min(l(x)) -> x 1077.11/291.62 min(n(x, y, z)) -> min(y) 1077.11/291.62 max(l(x)) -> x 1077.11/291.62 max(n(x, y, z)) -> max(z) 1077.11/291.62 bs(l(x)) -> true 1077.11/291.62 bs(n(x, y, z)) -> and(and(ge(x, max(y)), ge(min(z), x)), and(bs(y), bs(z))) 1077.11/291.62 size(l(x)) -> 1(#) 1077.11/291.62 size(n(x, y, z)) -> +(+(size(x), size(y)), 1(#)) 1077.11/291.62 wb(l(x)) -> true 1077.11/291.62 wb(n(x, y, z)) -> and(if(ge(size(y), size(z)), ge(1(#), -(size(y), size(z))), ge(1(#), -(size(z), size(y)))), and(wb(y), wb(z))) 1077.11/291.62 1077.11/291.62 S is empty. 1077.11/291.62 Rewrite Strategy: FULL 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (6) LowerBoundPropagationProof (FINISHED) 1077.11/291.62 Propagated lower bound. 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (7) 1077.11/291.62 BOUNDS(n^1, INF) 1077.11/291.62 1077.11/291.62 ---------------------------------------- 1077.11/291.62 1077.11/291.62 (8) 1077.11/291.62 Obligation: 1077.11/291.62 Analyzing the following TRS for decreasing loops: 1077.11/291.62 1077.11/291.62 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1077.11/291.62 1077.11/291.62 1077.11/291.62 The TRS R consists of the following rules: 1077.11/291.62 1077.11/291.62 0(#) -> # 1077.11/291.62 +(x, #) -> x 1077.11/291.62 +(#, x) -> x 1077.11/291.62 +(0(x), 0(y)) -> 0(+(x, y)) 1077.11/291.62 +(0(x), 1(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 0(y)) -> 1(+(x, y)) 1077.11/291.62 +(1(x), 1(y)) -> 0(+(+(x, y), 1(#))) 1077.11/291.62 +(x, +(y, z)) -> +(+(x, y), z) 1077.11/291.62 -(x, #) -> x 1077.11/291.62 -(#, x) -> # 1077.11/291.62 -(0(x), 0(y)) -> 0(-(x, y)) 1077.11/291.62 -(0(x), 1(y)) -> 1(-(-(x, y), 1(#))) 1077.11/291.62 -(1(x), 0(y)) -> 1(-(x, y)) 1077.11/291.62 -(1(x), 1(y)) -> 0(-(x, y)) 1077.11/291.62 not(false) -> true 1077.11/291.62 not(true) -> false 1077.11/291.62 and(x, true) -> x 1077.11/291.62 and(x, false) -> false 1077.11/291.62 if(true, x, y) -> x 1077.11/291.62 if(false, x, y) -> y 1077.11/291.62 ge(0(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(0(x), 1(y)) -> not(ge(y, x)) 1077.11/291.62 ge(1(x), 0(y)) -> ge(x, y) 1077.11/291.62 ge(1(x), 1(y)) -> ge(x, y) 1077.11/291.62 ge(x, #) -> true 1077.11/291.62 ge(#, 1(x)) -> false 1077.11/291.62 ge(#, 0(x)) -> ge(#, x) 1077.11/291.62 val(l(x)) -> x 1077.11/291.62 val(n(x, y, z)) -> x 1077.11/291.62 min(l(x)) -> x 1077.11/291.62 min(n(x, y, z)) -> min(y) 1077.11/291.62 max(l(x)) -> x 1077.11/291.62 max(n(x, y, z)) -> max(z) 1077.11/291.62 bs(l(x)) -> true 1077.11/291.62 bs(n(x, y, z)) -> and(and(ge(x, max(y)), ge(min(z), x)), and(bs(y), bs(z))) 1077.11/291.62 size(l(x)) -> 1(#) 1077.11/291.62 size(n(x, y, z)) -> +(+(size(x), size(y)), 1(#)) 1077.11/291.62 wb(l(x)) -> true 1077.11/291.62 wb(n(x, y, z)) -> and(if(ge(size(y), size(z)), ge(1(#), -(size(y), size(z))), ge(1(#), -(size(z), size(y)))), and(wb(y), wb(z))) 1077.11/291.62 1077.11/291.62 S is empty. 1077.11/291.62 Rewrite Strategy: FULL 1077.51/291.81 EOF