WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox/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), 275 ms] (4) CpxRelTRS (5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 4 ms] (8) typed CpxTrs (9) OrderProof [LOWER BOUND(ID), 0 ms] (10) typed CpxTrs (11) RewriteLemmaProof [LOWER BOUND(ID), 246 ms] (12) BEST (13) proven lower bound (14) LowerBoundPropagationProof [FINISHED, 0 ms] (15) BOUNDS(n^1, INF) (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 56 ms] (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 480 ms] (20) BOUNDS(1, INF) ---------------------------------------- (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: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0 minus(x, 0) -> x minus(0, x) -> 0 minus(s(x), s(y)) -> minus(x, y) isZero(0) -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) 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(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError ---------------------------------------- (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: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0 minus(x, 0) -> x minus(0, x) -> 0 minus(s(x), s(y)) -> minus(x, y) isZero(0) -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError 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: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0 minus(x, 0) -> x minus(0, x) -> 0 minus(s(x), s(y)) -> minus(x, y) isZero(0) -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Rewrite Strategy: INNERMOST ---------------------------------------- (5) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (6) 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: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Innermost TRS: Rules: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Types: le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod 0' :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encArg :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_0 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod hole_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod1_6 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6 :: Nat -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod ---------------------------------------- (9) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: le, minus, mod, if_mod, encArg They will be analysed ascendingly in the following order: le < mod le < encArg minus < mod minus < encArg mod = if_mod mod < encArg if_mod < encArg ---------------------------------------- (10) Obligation: Innermost TRS: Rules: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Types: le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod 0' :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encArg :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_0 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod hole_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod1_6 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6 :: Nat -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod Generator Equations: gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0) <=> 0' gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(x, 1)) <=> s(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(x)) The following defined symbols remain to be analysed: le, minus, mod, if_mod, encArg They will be analysed ascendingly in the following order: le < mod le < encArg minus < mod minus < encArg mod = if_mod mod < encArg if_mod < encArg ---------------------------------------- (11) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6)) -> true, rt in Omega(1 + n4_6) Induction Base: le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0)) ->_R^Omega(1) true Induction Step: le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(n4_6, 1)), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(n4_6, 1))) ->_R^Omega(1) le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6)) ->_IH true We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (12) Complex Obligation (BEST) ---------------------------------------- (13) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Types: le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod 0' :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encArg :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_0 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod hole_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod1_6 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6 :: Nat -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod Generator Equations: gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0) <=> 0' gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(x, 1)) <=> s(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(x)) The following defined symbols remain to be analysed: le, minus, mod, if_mod, encArg They will be analysed ascendingly in the following order: le < mod le < encArg minus < mod minus < encArg mod = if_mod mod < encArg if_mod < encArg ---------------------------------------- (14) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (15) BOUNDS(n^1, INF) ---------------------------------------- (16) Obligation: Innermost TRS: Rules: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Types: le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod 0' :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encArg :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_0 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod hole_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod1_6 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6 :: Nat -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod Lemmas: le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6)) -> true, rt in Omega(1 + n4_6) Generator Equations: gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0) <=> 0' gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(x, 1)) <=> s(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(x)) The following defined symbols remain to be analysed: minus, mod, if_mod, encArg They will be analysed ascendingly in the following order: minus < mod minus < encArg mod = if_mod mod < encArg if_mod < encArg ---------------------------------------- (17) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: minus(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6)) -> gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0), rt in Omega(1 + n587_6) Induction Base: minus(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0)) ->_R^Omega(1) 0' Induction Step: minus(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(n587_6, 1)), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(n587_6, 1))) ->_R^Omega(1) minus(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6)) ->_IH gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (18) Obligation: Innermost TRS: Rules: le(0', y) -> true le(s(x), 0') -> false le(s(x), s(y)) -> le(x, y) minus(x, x) -> 0' minus(x, 0') -> x minus(0', x) -> 0' minus(s(x), s(y)) -> minus(x, y) isZero(0') -> true isZero(s(x)) -> false mod(x, y) -> if_mod(isZero(y), le(y, x), x, y, minus(x, y)) if_mod(true, b, x, y, z) -> divByZeroError if_mod(false, false, x, y, z) -> x if_mod(false, true, x, y, z) -> mod(z, y) encArg(0') -> 0' encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(divByZeroError) -> divByZeroError encArg(cons_le(x_1, x_2)) -> le(encArg(x_1), encArg(x_2)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_isZero(x_1)) -> isZero(encArg(x_1)) encArg(cons_mod(x_1, x_2)) -> mod(encArg(x_1), encArg(x_2)) encArg(cons_if_mod(x_1, x_2, x_3, x_4, x_5)) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_le(x_1, x_2) -> le(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_true -> true encode_s(x_1) -> s(encArg(x_1)) encode_false -> false encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_isZero(x_1) -> isZero(encArg(x_1)) encode_mod(x_1, x_2) -> mod(encArg(x_1), encArg(x_2)) encode_if_mod(x_1, x_2, x_3, x_4, x_5) -> if_mod(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5)) encode_divByZeroError -> divByZeroError Types: le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod 0' :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encArg :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod cons_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_le :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_0 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_true :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_s :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_false :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_minus :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_isZero :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_if_mod :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod encode_divByZeroError :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod hole_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod1_6 :: 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6 :: Nat -> 0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod Lemmas: le(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n4_6)) -> true, rt in Omega(1 + n4_6) minus(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6), gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n587_6)) -> gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0), rt in Omega(1 + n587_6) Generator Equations: gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0) <=> 0' gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(x, 1)) <=> s(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(x)) The following defined symbols remain to be analysed: if_mod, mod, encArg They will be analysed ascendingly in the following order: mod = if_mod mod < encArg if_mod < encArg ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n2028_6)) -> gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n2028_6), rt in Omega(0) Induction Base: encArg(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(+(n2028_6, 1))) ->_R^Omega(0) s(encArg(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(n2028_6))) ->_IH s(gen_0':true:s:false:divByZeroError:cons_le:cons_minus:cons_isZero:cons_mod:cons_if_mod2_6(c2029_6)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (20) BOUNDS(1, INF)