/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 721 ms] (4) CpxRelTRS (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (6) TRS for Loop Detection (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (6) Obligation: Analyzing the following TRS for decreasing loops: 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: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (7) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence +(I(x), I(y)) ->^+ O(+(+(x, y), I(0))) gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0]. The pumping substitution is [x / I(x), y / I(y)]. The result substitution is [ ]. ---------------------------------------- (8) Complex Obligation (BEST) ---------------------------------------- (9) Obligation: Proved the lower bound n^1 for the following 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: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: Analyzing the following TRS for decreasing loops: 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: O(0) -> 0 +(0, x) -> x +(x, 0) -> x +(O(x), O(y)) -> O(+(x, y)) +(O(x), I(y)) -> I(+(x, y)) +(I(x), O(y)) -> I(+(x, y)) +(I(x), I(y)) -> O(+(+(x, y), I(0))) +(x, +(y, z)) -> +(+(x, y), z) -(x, 0) -> x -(0, x) -> 0 -(O(x), O(y)) -> O(-(x, y)) -(O(x), I(y)) -> I(-(-(x, y), I(1))) -(I(x), O(y)) -> I(-(x, y)) -(I(x), I(y)) -> O(-(x, y)) not(true) -> false not(false) -> true and(x, true) -> x and(x, false) -> false if(true, x, y) -> x if(false, x, y) -> y ge(O(x), O(y)) -> ge(x, y) ge(O(x), I(y)) -> not(ge(y, x)) ge(I(x), O(y)) -> ge(x, y) ge(I(x), I(y)) -> ge(x, y) ge(x, 0) -> true ge(0, O(x)) -> ge(0, x) ge(0, I(x)) -> false Log'(0) -> 0 Log'(I(x)) -> +(Log'(x), I(0)) Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) Log(x) -> -(Log'(x), I(0)) Val(L(x)) -> x Val(N(x, l, r)) -> x Min(L(x)) -> x Min(N(x, l, r)) -> Min(l) Max(L(x)) -> x Max(N(x, l, r)) -> Max(r) BS(L(x)) -> true BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) Size(L(x)) -> I(0) Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) WB(L(x)) -> true WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(I(x_1)) -> I(encArg(x_1)) encArg(1) -> 1 encArg(true) -> true encArg(false) -> false encArg(L(x_1)) -> L(encArg(x_1)) encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(l) -> l encArg(r) -> r encArg(cons_O(x_1)) -> O(encArg(x_1)) encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_not(x_1)) -> not(encArg(x_1)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_ge(x_1, x_2)) -> ge(encArg(x_1), encArg(x_2)) encArg(cons_Log'(x_1)) -> Log'(encArg(x_1)) encArg(cons_Log(x_1)) -> Log(encArg(x_1)) encArg(cons_Val(x_1)) -> Val(encArg(x_1)) encArg(cons_Min(x_1)) -> Min(encArg(x_1)) encArg(cons_Max(x_1)) -> Max(encArg(x_1)) encArg(cons_BS(x_1)) -> BS(encArg(x_1)) encArg(cons_Size(x_1)) -> Size(encArg(x_1)) encArg(cons_WB(x_1)) -> WB(encArg(x_1)) encode_O(x_1) -> O(encArg(x_1)) encode_0 -> 0 encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) encode_I(x_1) -> I(encArg(x_1)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_1 -> 1 encode_not(x_1) -> not(encArg(x_1)) encode_true -> true encode_false -> false encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_ge(x_1, x_2) -> ge(encArg(x_1), encArg(x_2)) encode_Log'(x_1) -> Log'(encArg(x_1)) encode_Log(x_1) -> Log(encArg(x_1)) encode_Val(x_1) -> Val(encArg(x_1)) encode_L(x_1) -> L(encArg(x_1)) encode_N(x_1, x_2, x_3) -> N(encArg(x_1), encArg(x_2), encArg(x_3)) encode_l -> l encode_r -> r encode_Min(x_1) -> Min(encArg(x_1)) encode_Max(x_1) -> Max(encArg(x_1)) encode_BS(x_1) -> BS(encArg(x_1)) encode_Size(x_1) -> Size(encArg(x_1)) encode_WB(x_1) -> WB(encArg(x_1)) Rewrite Strategy: INNERMOST