/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxRelTRS (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 45 ms] (2) CpxRelTRS (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxWeightedTrs (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 4 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 3305 ms] (14) BOUNDS(1, n^1) (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (16) TRS for Loop Detection (17) DecreasingLoopProof [LOWER BOUND(ID), 400 ms] (18) BEST (19) proven lower bound (20) LowerBoundPropagationProof [FINISHED, 0 ms] (21) BOUNDS(n^1, INF) (22) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False m2(S(S(x)), b, res, True) -> True m2(0, b, res, True) -> False m3(S(0), b, res, t) -> False m3(S(S(x)), b, res, t) -> True m3(0, b, res, t) -> False l8(res, y, res', True, mtmp, t) -> res l5(x, y, res, tmp, mtmp, True) -> 0 help1(S(0)) -> False help1(S(S(x))) -> True e4(a, b, res, False) -> False e4(a, b, res, True) -> True e2(a, b, res, False) -> False l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) m2(a, b, res, False) -> m4(a, b, res, False) l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, True) -> res l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) help1(0) -> False e2(a, b, res, True) -> e3(a, b, res, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(a, x, res, t) -> m2(a, x, res, False) l9(res, y, res', tmp, mtmp, t) -> res l6(x, y, res, tmp, mtmp, t) -> 0 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) e7(a, b, res, t) -> False e6(a, b, res, t) -> False e5(a, b, res, t) -> True monus(a, b) -> m1(a, b, False, False) m5(a, b, res, t) -> res l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) l16(x, y, res, tmp, mtmp, t) -> res l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) gcd(x, y) -> l1(x, y, 0, False, False, False) equal0(a, b) -> e1(a, b, False, False) e8(a, b, res, t) -> res e3(a, b, res, t) -> e4(a, b, res, <(b, a)) e1(a, b, res, t) -> e2(a, b, res, <(a, b)) The (relative) TRS S consists of the following rules: <(S(x), S(y)) -> <(x, y) <(0, S(y)) -> True <(x, 0) -> False Rewrite Strategy: INNERMOST ---------------------------------------- (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved termination of relative rules ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False m2(S(S(x)), b, res, True) -> True m2(0, b, res, True) -> False m3(S(0), b, res, t) -> False m3(S(S(x)), b, res, t) -> True m3(0, b, res, t) -> False l8(res, y, res', True, mtmp, t) -> res l5(x, y, res, tmp, mtmp, True) -> 0 help1(S(0)) -> False help1(S(S(x))) -> True e4(a, b, res, False) -> False e4(a, b, res, True) -> True e2(a, b, res, False) -> False l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) m2(a, b, res, False) -> m4(a, b, res, False) l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, True) -> res l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) help1(0) -> False e2(a, b, res, True) -> e3(a, b, res, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(a, x, res, t) -> m2(a, x, res, False) l9(res, y, res', tmp, mtmp, t) -> res l6(x, y, res, tmp, mtmp, t) -> 0 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) e7(a, b, res, t) -> False e6(a, b, res, t) -> False e5(a, b, res, t) -> True monus(a, b) -> m1(a, b, False, False) m5(a, b, res, t) -> res l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) l16(x, y, res, tmp, mtmp, t) -> res l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) gcd(x, y) -> l1(x, y, 0, False, False, False) equal0(a, b) -> e1(a, b, False, False) e8(a, b, res, t) -> res e3(a, b, res, t) -> e4(a, b, res, <(b, a)) e1(a, b, res, t) -> e2(a, b, res, <(a, b)) The (relative) TRS S consists of the following rules: <(S(x), S(y)) -> <(x, y) <(0, S(y)) -> True <(x, 0) -> False Rewrite Strategy: INNERMOST ---------------------------------------- (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False [1] m2(S(S(x)), b, res, True) -> True [1] m2(0, b, res, True) -> False [1] m3(S(0), b, res, t) -> False [1] m3(S(S(x)), b, res, t) -> True [1] m3(0, b, res, t) -> False [1] l8(res, y, res', True, mtmp, t) -> res [1] l5(x, y, res, tmp, mtmp, True) -> 0 [1] help1(S(0)) -> False [1] help1(S(S(x))) -> True [1] e4(a, b, res, False) -> False [1] e4(a, b, res, True) -> True [1] e2(a, b, res, False) -> False [1] l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) [1] l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) [1] l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) [1] l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) [1] m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) [1] m2(a, b, res, False) -> m4(a, b, res, False) [1] l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) [1] l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, True) -> res [1] l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) [1] l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) [1] help1(0) -> False [1] e2(a, b, res, True) -> e3(a, b, res, True) [1] bool2Nat(False) -> 0 [1] bool2Nat(True) -> S(0) [1] m1(a, x, res, t) -> m2(a, x, res, False) [1] l9(res, y, res', tmp, mtmp, t) -> res [1] l6(x, y, res, tmp, mtmp, t) -> 0 [1] l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) [1] l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) [1] e7(a, b, res, t) -> False [1] e6(a, b, res, t) -> False [1] e5(a, b, res, t) -> True [1] monus(a, b) -> m1(a, b, False, False) [1] m5(a, b, res, t) -> res [1] l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) [1] l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) [1] l16(x, y, res, tmp, mtmp, t) -> res [1] l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) [1] l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) [1] l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) [1] gcd(x, y) -> l1(x, y, 0, False, False, False) [1] equal0(a, b) -> e1(a, b, False, False) [1] e8(a, b, res, t) -> res [1] e3(a, b, res, t) -> e4(a, b, res, <(b, a)) [1] e1(a, b, res, t) -> e2(a, b, res, <(a, b)) [1] <(S(x), S(y)) -> <(x, y) [0] <(0, S(y)) -> True [0] <(x, 0) -> False [0] Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) Renamed defined symbols to avoid conflicts with arithmetic symbols: < => lt ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False [1] m2(S(S(x)), b, res, True) -> True [1] m2(0, b, res, True) -> False [1] m3(S(0), b, res, t) -> False [1] m3(S(S(x)), b, res, t) -> True [1] m3(0, b, res, t) -> False [1] l8(res, y, res', True, mtmp, t) -> res [1] l5(x, y, res, tmp, mtmp, True) -> 0 [1] help1(S(0)) -> False [1] help1(S(S(x))) -> True [1] e4(a, b, res, False) -> False [1] e4(a, b, res, True) -> True [1] e2(a, b, res, False) -> False [1] l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) [1] l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) [1] l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) [1] l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) [1] m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) [1] m2(a, b, res, False) -> m4(a, b, res, False) [1] l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) [1] l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, True) -> res [1] l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) [1] l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) [1] help1(0) -> False [1] e2(a, b, res, True) -> e3(a, b, res, True) [1] bool2Nat(False) -> 0 [1] bool2Nat(True) -> S(0) [1] m1(a, x, res, t) -> m2(a, x, res, False) [1] l9(res, y, res', tmp, mtmp, t) -> res [1] l6(x, y, res, tmp, mtmp, t) -> 0 [1] l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) [1] l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) [1] e7(a, b, res, t) -> False [1] e6(a, b, res, t) -> False [1] e5(a, b, res, t) -> True [1] monus(a, b) -> m1(a, b, False, False) [1] m5(a, b, res, t) -> res [1] l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) [1] l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) [1] l16(x, y, res, tmp, mtmp, t) -> res [1] l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) [1] l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) [1] l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, lt(x, y)) [1] gcd(x, y) -> l1(x, y, 0, False, False, False) [1] equal0(a, b) -> e1(a, b, False, False) [1] e8(a, b, res, t) -> res [1] e3(a, b, res, t) -> e4(a, b, res, lt(b, a)) [1] e1(a, b, res, t) -> e2(a, b, res, lt(a, b)) [1] lt(S(x), S(y)) -> lt(x, y) [0] lt(0, S(y)) -> True [0] lt(x, 0) -> False [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: m2(S(0), b, res, True) -> False [1] m2(S(S(x)), b, res, True) -> True [1] m2(0, b, res, True) -> False [1] m3(S(0), b, res, t) -> False [1] m3(S(S(x)), b, res, t) -> True [1] m3(0, b, res, t) -> False [1] l8(res, y, res', True, mtmp, t) -> res [1] l5(x, y, res, tmp, mtmp, True) -> 0 [1] help1(S(0)) -> False [1] help1(S(S(x))) -> True [1] e4(a, b, res, False) -> False [1] e4(a, b, res, True) -> True [1] e2(a, b, res, False) -> False [1] l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) [1] l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) [1] l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) [1] l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) [1] m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) [1] m2(a, b, res, False) -> m4(a, b, res, False) [1] l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) [1] l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, True) -> res [1] l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) [1] l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) [1] help1(0) -> False [1] e2(a, b, res, True) -> e3(a, b, res, True) [1] bool2Nat(False) -> 0 [1] bool2Nat(True) -> S(0) [1] m1(a, x, res, t) -> m2(a, x, res, False) [1] l9(res, y, res', tmp, mtmp, t) -> res [1] l6(x, y, res, tmp, mtmp, t) -> 0 [1] l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) [1] l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) [1] e7(a, b, res, t) -> False [1] e6(a, b, res, t) -> False [1] e5(a, b, res, t) -> True [1] monus(a, b) -> m1(a, b, False, False) [1] m5(a, b, res, t) -> res [1] l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) [1] l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) [1] l16(x, y, res, tmp, mtmp, t) -> res [1] l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) [1] l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) [1] l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, lt(x, y)) [1] gcd(x, y) -> l1(x, y, 0, False, False, False) [1] equal0(a, b) -> e1(a, b, False, False) [1] e8(a, b, res, t) -> res [1] e3(a, b, res, t) -> e4(a, b, res, lt(b, a)) [1] e1(a, b, res, t) -> e2(a, b, res, lt(a, b)) [1] lt(S(x), S(y)) -> lt(x, y) [0] lt(0, S(y)) -> True [0] lt(x, 0) -> False [0] The TRS has the following type information: m2 :: 0:S -> 0:S -> True:False -> True:False -> True:False S :: 0:S -> 0:S 0 :: 0:S True :: True:False False :: True:False m3 :: 0:S -> a -> b -> c -> True:False l8 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l5 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S help1 :: 0:S -> True:False e4 :: 0:S -> 0:S -> True:False -> True:False -> True:False e2 :: 0:S -> 0:S -> True:False -> True:False -> True:False l15 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l16 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S gcd :: 0:S -> 0:S -> 0:S l13 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S m4 :: 0:S -> 0:S -> True:False -> True:False -> True:False m5 :: 0:S -> 0:S -> True:False -> True:False -> True:False monus :: 0:S -> 0:S -> True:False l10 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l7 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l2 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l3 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l11 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l14 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l12 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S e3 :: 0:S -> 0:S -> True:False -> True:False -> True:False bool2Nat :: True:False -> 0:S m1 :: 0:S -> 0:S -> True:False -> True:False -> True:False l9 :: l9 -> d -> e -> f -> g -> h -> l9 l6 :: i -> j -> k -> l -> m -> n -> 0:S l4 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S l1 :: 0:S -> 0:S -> 0:S -> True:False -> True:False -> True:False -> 0:S e7 :: o -> p -> q -> r -> True:False e6 :: s -> t -> u -> v -> True:False e5 :: w -> x -> y -> z -> True:False equal0 :: 0:S -> 0:S -> True:False lt :: 0:S -> 0:S -> True:False e1 :: 0:S -> 0:S -> True:False -> True:False -> True:False e8 :: za -> zaa -> e8 -> zaaa -> e8 Rewrite Strategy: INNERMOST ---------------------------------------- (9) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: lt(v0, v1) -> null_lt [0] m2(v0, v1, v2, v3) -> null_m2 [0] l8(v0, v1, v2, v3, v4, v5) -> null_l8 [0] l5(v0, v1, v2, v3, v4, v5) -> null_l5 [0] e4(v0, v1, v2, v3) -> null_e4 [0] e2(v0, v1, v2, v3) -> null_e2 [0] l15(v0, v1, v2, v3, v4, v5) -> null_l15 [0] l13(v0, v1, v2, v3, v4, v5) -> null_l13 [0] m4(v0, v1, v2, v3) -> null_m4 [0] l2(v0, v1, v2, v3, v4, v5) -> null_l2 [0] l11(v0, v1, v2, v3, v4, v5) -> null_l11 [0] bool2Nat(v0) -> null_bool2Nat [0] m3(v0, v1, v2, v3) -> null_m3 [0] help1(v0) -> null_help1 [0] And the following fresh constants: null_lt, null_m2, null_l8, null_l5, null_e4, null_e2, null_l15, null_l13, null_m4, null_l2, null_l11, null_bool2Nat, null_m3, null_help1, const, const1, const2, const3, const4, const5, const6, const7, const8, const9, const10, const11, const12, const13, const14, const15, const16, const17, const18, const19, const20, const21, const22, const23, const24, const25, const26, const27, const28, const29, const30 ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: m2(S(0), b, res, True) -> False [1] m2(S(S(x)), b, res, True) -> True [1] m2(0, b, res, True) -> False [1] m3(S(0), b, res, t) -> False [1] m3(S(S(x)), b, res, t) -> True [1] m3(0, b, res, t) -> False [1] l8(res, y, res', True, mtmp, t) -> res [1] l5(x, y, res, tmp, mtmp, True) -> 0 [1] help1(S(0)) -> False [1] help1(S(S(x))) -> True [1] e4(a, b, res, False) -> False [1] e4(a, b, res, True) -> True [1] e2(a, b, res, False) -> False [1] l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) [1] l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) [1] l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) [1] l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) [1] m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) [1] m2(a, b, res, False) -> m4(a, b, res, False) [1] l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) [1] l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) [1] l2(x, y, res, tmp, mtmp, True) -> res [1] l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) [1] l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) [1] help1(0) -> False [1] e2(a, b, res, True) -> e3(a, b, res, True) [1] bool2Nat(False) -> 0 [1] bool2Nat(True) -> S(0) [1] m1(a, x, res, t) -> m2(a, x, res, False) [1] l9(res, y, res', tmp, mtmp, t) -> res [1] l6(x, y, res, tmp, mtmp, t) -> 0 [1] l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) [1] l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) [1] e7(a, b, res, t) -> False [1] e6(a, b, res, t) -> False [1] e5(a, b, res, t) -> True [1] monus(a, b) -> m1(a, b, False, False) [1] m5(a, b, res, t) -> res [1] l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) [1] l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) [1] l16(x, y, res, tmp, mtmp, t) -> res [1] l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) [1] l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) [1] l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, lt(x, y)) [1] gcd(x, y) -> l1(x, y, 0, False, False, False) [1] equal0(a, b) -> e1(a, b, False, False) [1] e8(a, b, res, t) -> res [1] e3(a, b, res, t) -> e4(a, b, res, lt(b, a)) [1] e1(a, b, res, t) -> e2(a, b, res, lt(a, b)) [1] lt(S(x), S(y)) -> lt(x, y) [0] lt(0, S(y)) -> True [0] lt(x, 0) -> False [0] lt(v0, v1) -> null_lt [0] m2(v0, v1, v2, v3) -> null_m2 [0] l8(v0, v1, v2, v3, v4, v5) -> null_l8 [0] l5(v0, v1, v2, v3, v4, v5) -> null_l5 [0] e4(v0, v1, v2, v3) -> null_e4 [0] e2(v0, v1, v2, v3) -> null_e2 [0] l15(v0, v1, v2, v3, v4, v5) -> null_l15 [0] l13(v0, v1, v2, v3, v4, v5) -> null_l13 [0] m4(v0, v1, v2, v3) -> null_m4 [0] l2(v0, v1, v2, v3, v4, v5) -> null_l2 [0] l11(v0, v1, v2, v3, v4, v5) -> null_l11 [0] bool2Nat(v0) -> null_bool2Nat [0] m3(v0, v1, v2, v3) -> null_m3 [0] help1(v0) -> null_help1 [0] The TRS has the following type information: m2 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 S :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat 0 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat True :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 False :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 m3 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> a -> b -> c -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 l8 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l5 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat help1 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e4 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e2 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 l15 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l16 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat gcd :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l13 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat m4 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 m5 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 monus :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 l10 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l7 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l2 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l3 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l11 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l14 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l12 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat e3 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 bool2Nat :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat m1 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 l9 :: l9 -> d -> e -> f -> g -> h -> l9 l6 :: i -> j -> k -> l -> m -> n -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l4 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat l1 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat e7 :: o -> p -> q -> r -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e6 :: s -> t -> u -> v -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e5 :: w -> x -> y -> z -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 equal0 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 lt :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e1 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 -> True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 e8 :: za -> zaa -> e8 -> zaaa -> e8 null_lt :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_m2 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_l8 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_l5 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_e4 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_e2 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_l15 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_l13 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_m4 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_l2 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_l11 :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_bool2Nat :: 0:S:null_l8:null_l5:null_l15:null_l13:null_l2:null_l11:null_bool2Nat null_m3 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 null_help1 :: True:False:null_lt:null_m2:null_e4:null_e2:null_m4:null_m3:null_help1 const :: a const1 :: b const2 :: c const3 :: l9 const4 :: d const5 :: e const6 :: f const7 :: g const8 :: h const9 :: i const10 :: j const11 :: k const12 :: l const13 :: m const14 :: n const15 :: o const16 :: p const17 :: q const18 :: r const19 :: s const20 :: t const21 :: u const22 :: v const23 :: w const24 :: x const25 :: y const26 :: z const27 :: e8 const28 :: za const29 :: zaa const30 :: zaaa Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 True => 2 False => 1 null_lt => 0 null_m2 => 0 null_l8 => 0 null_l5 => 0 null_e4 => 0 null_e2 => 0 null_l15 => 0 null_l13 => 0 null_m4 => 0 null_l2 => 0 null_l11 => 0 null_bool2Nat => 0 null_m3 => 0 null_help1 => 0 const => 0 const1 => 0 const2 => 0 const3 => 0 const4 => 0 const5 => 0 const6 => 0 const7 => 0 const8 => 0 const9 => 0 const10 => 0 const11 => 0 const12 => 0 const13 => 0 const14 => 0 const15 => 0 const16 => 0 const17 => 0 const18 => 0 const19 => 0 const20 => 0 const21 => 0 const22 => 0 const23 => 0 const24 => 0 const25 => 0 const26 => 0 const27 => 0 const28 => 0 const29 => 0 const30 => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: bool2Nat(z) -{ 1 }-> 0 :|: z = 1 bool2Nat(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 bool2Nat(z) -{ 1 }-> 1 + 0 :|: z = 2 e1(z, z', z'', z1) -{ 1 }-> e2(a, b, res, lt(a, b)) :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 e2(z, z', z'', z1) -{ 1 }-> e3(a, b, res, 2) :|: z = a, b >= 0, z1 = 2, a >= 0, z'' = res, z' = b, res >= 0 e2(z, z', z'', z1) -{ 1 }-> 1 :|: z = a, b >= 0, a >= 0, z'' = res, z1 = 1, z' = b, res >= 0 e2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 e3(z, z', z'', z1) -{ 1 }-> e4(a, b, res, lt(b, a)) :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 e4(z, z', z'', z1) -{ 1 }-> 2 :|: z = a, b >= 0, z1 = 2, a >= 0, z'' = res, z' = b, res >= 0 e4(z, z', z'', z1) -{ 1 }-> 1 :|: z = a, b >= 0, a >= 0, z'' = res, z1 = 1, z' = b, res >= 0 e4(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 e5(z, z', z'', z1) -{ 1 }-> 2 :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 e6(z, z', z'', z1) -{ 1 }-> 1 :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 e7(z, z', z'', z1) -{ 1 }-> 1 :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 e8(z, z', z'', z1) -{ 1 }-> res :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 equal0(z, z') -{ 1 }-> e1(a, b, 1, 1) :|: z = a, b >= 0, a >= 0, z' = b gcd(z, z') -{ 1 }-> l1(x, y, 0, 1, 1, 1) :|: x >= 0, y >= 0, z = x, z' = y help1(z) -{ 1 }-> 2 :|: x >= 0, z = 1 + (1 + x) help1(z) -{ 1 }-> 1 :|: z = 1 + 0 help1(z) -{ 1 }-> 1 :|: z = 0 help1(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 l1(z, z', z'', z1, z2, z3) -{ 1 }-> l2(x, y, res, tmp, mtmp, 1) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l10(z, z', z'', z1, z2, z3) -{ 1 }-> l11(x, y, res, tmp, mtmp, lt(x, y)) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l11(z, z', z'', z1, z2, z3) -{ 1 }-> l14(x, y, res, tmp, mtmp, 1) :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, z3 = 1, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l11(z, z', z'', z1, z2, z3) -{ 1 }-> l12(x, y, res, tmp, mtmp, 2) :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp, z3 = 2 l11(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l12(z, z', z'', z1, z2, z3) -{ 1 }-> l13(x, y, res, tmp, monus(x, y), t) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l13(z, z', z'', z1, z2, z3) -{ 1 }-> l16(x, y, gcd(0, y), tmp, 1, t) :|: z3 = t, z2 = 1, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l13(z, z', z'', z1, z2, z3) -{ 1 }-> l16(x, y, gcd(1 + 0, y), tmp, 2, t) :|: z2 = 2, z3 = t, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l13(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l14(z, z', z'', z1, z2, z3) -{ 1 }-> l15(x, y, res, tmp, monus(x, y), t) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l15(z, z', z'', z1, z2, z3) -{ 1 }-> l16(x, y, gcd(y, 0), tmp, 1, t) :|: z3 = t, z2 = 1, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l15(z, z', z'', z1, z2, z3) -{ 1 }-> l16(x, y, gcd(y, 1 + 0), tmp, 2, t) :|: z2 = 2, z3 = t, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l15(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l16(z, z', z'', z1, z2, z3) -{ 1 }-> res :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l2(z, z', z'', z1, z2, z3) -{ 1 }-> res :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp, z3 = 2 l2(z, z', z'', z1, z2, z3) -{ 1 }-> l3(x, y, res, tmp, mtmp, 1) :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, z3 = 1, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l2(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l3(z, z', z'', z1, z2, z3) -{ 1 }-> l4(x, y, 0, tmp, mtmp, t) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l4(z, z', z'', z1, z2, z3) -{ 1 }-> l5(x', x, res, tmp, mtmp, 1) :|: mtmp >= 0, z3 = t, z' = x, z2 = mtmp, z'' = res, x' >= 0, x >= 0, t >= 0, res >= 0, tmp >= 0, z1 = tmp, z = x' l5(z, z', z'', z1, z2, z3) -{ 1 }-> l7(x, y, res, tmp, mtmp, 1) :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, z3 = 1, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l5(z, z', z'', z1, z2, z3) -{ 1 }-> 0 :|: mtmp >= 0, z2 = mtmp, z'' = res, x >= 0, y >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp, z3 = 2 l5(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l6(z, z', z'', z1, z2, z3) -{ 1 }-> 0 :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l7(z, z', z'', z1, z2, z3) -{ 1 }-> l8(x, y, res, equal0(x, y), mtmp, t) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, t >= 0, res >= 0, tmp >= 0, z = x, z' = y, z1 = tmp l8(z, z', z'', z1, z2, z3) -{ 1 }-> res :|: mtmp >= 0, z3 = t, z'' = res', z1 = 2, z2 = mtmp, y >= 0, t >= 0, z = res, res >= 0, z' = y, res' >= 0 l8(z, z', z'', z1, z2, z3) -{ 1 }-> l10(x, y, res, 1, mtmp, t) :|: mtmp >= 0, z3 = t, z2 = mtmp, z'' = res, x >= 0, y >= 0, z1 = 1, t >= 0, res >= 0, z = x, z' = y l8(z, z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z1 = v3, z3 = v5, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, v5 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 l9(z, z', z'', z1, z2, z3) -{ 1 }-> res :|: mtmp >= 0, z3 = t, z'' = res', z2 = mtmp, y >= 0, t >= 0, z = res, res >= 0, tmp >= 0, z' = y, z1 = tmp, res' >= 0 lt(z, z') -{ 0 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x lt(z, z') -{ 0 }-> 2 :|: z' = 1 + y, y >= 0, z = 0 lt(z, z') -{ 0 }-> 1 :|: x >= 0, z = x, z' = 0 lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 m1(z, z', z'', z1) -{ 1 }-> m2(a, x, res, 1) :|: z = a, z' = x, a >= 0, z'' = res, x >= 0, z1 = t, t >= 0, res >= 0 m2(z, z', z'', z1) -{ 1 }-> m4(a, b, res, 1) :|: z = a, b >= 0, a >= 0, z'' = res, z1 = 1, z' = b, res >= 0 m2(z, z', z'', z1) -{ 1 }-> 2 :|: b >= 0, z1 = 2, z'' = res, x >= 0, z' = b, res >= 0, z = 1 + (1 + x) m2(z, z', z'', z1) -{ 1 }-> 1 :|: b >= 0, z1 = 2, z = 1 + 0, z'' = res, z' = b, res >= 0 m2(z, z', z'', z1) -{ 1 }-> 1 :|: b >= 0, z1 = 2, z'' = res, z' = b, res >= 0, z = 0 m2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 m3(z, z', z'', z1) -{ 1 }-> 2 :|: b >= 0, z'' = res, x >= 0, z1 = t, z' = b, t >= 0, res >= 0, z = 1 + (1 + x) m3(z, z', z'', z1) -{ 1 }-> 1 :|: b >= 0, z = 1 + 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 m3(z, z', z'', z1) -{ 1 }-> 1 :|: b >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0, z = 0 m3(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 m4(z, z', z'', z1) -{ 1 }-> m5(1 + x', 1 + x, monus(x', x), t) :|: z = 1 + x', z' = 1 + x, z'' = res, x' >= 0, x >= 0, z1 = t, t >= 0, res >= 0 m4(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 m5(z, z', z'', z1) -{ 1 }-> res :|: z = a, b >= 0, a >= 0, z'' = res, z1 = t, z' = b, t >= 0, res >= 0 monus(z, z') -{ 1 }-> m1(a, b, 1, 1) :|: z = a, b >= 0, a >= 0, z' = b Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V2, V1, V3, V5, V25, V27),0,[m2(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[m3(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l8(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l5(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[help1(V2, Out)],[V2 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e4(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e2(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l15(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l13(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[m4(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l2(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l11(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[bool2Nat(V2, Out)],[V2 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[m1(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l9(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l6(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l4(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l1(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e7(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e6(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e5(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[monus(V2, V1, Out)],[V2 >= 0,V1 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[m5(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l7(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l3(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l16(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l14(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l12(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[l10(V2, V1, V3, V5, V25, V27, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0,V25 >= 0,V27 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[gcd(V2, V1, Out)],[V2 >= 0,V1 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[equal0(V2, V1, Out)],[V2 >= 0,V1 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e8(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e3(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[e1(V2, V1, V3, V5, Out)],[V2 >= 0,V1 >= 0,V3 >= 0,V5 >= 0]). eq(start(V2, V1, V3, V5, V25, V27),0,[lt(V2, V1, Out)],[V2 >= 0,V1 >= 0]). eq(m2(V2, V1, V3, V5, Out),1,[],[Out = 1,V4 >= 0,V5 = 2,V2 = 1,V3 = V,V1 = V4,V >= 0]). eq(m2(V2, V1, V3, V5, Out),1,[],[Out = 2,V6 >= 0,V5 = 2,V3 = V8,V7 >= 0,V1 = V6,V8 >= 0,V2 = 2 + V7]). eq(m2(V2, V1, V3, V5, Out),1,[],[Out = 1,V9 >= 0,V5 = 2,V3 = V10,V1 = V9,V10 >= 0,V2 = 0]). eq(m3(V2, V1, V3, V5, Out),1,[],[Out = 1,V12 >= 0,V2 = 1,V3 = V13,V5 = V11,V1 = V12,V11 >= 0,V13 >= 0]). eq(m3(V2, V1, V3, V5, Out),1,[],[Out = 2,V16 >= 0,V3 = V17,V14 >= 0,V5 = V15,V1 = V16,V15 >= 0,V17 >= 0,V2 = 2 + V14]). eq(m3(V2, V1, V3, V5, Out),1,[],[Out = 1,V19 >= 0,V3 = V20,V5 = V18,V1 = V19,V18 >= 0,V20 >= 0,V2 = 0]). eq(l8(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = V24,V22 >= 0,V27 = V21,V3 = V23,V5 = 2,V25 = V22,V26 >= 0,V21 >= 0,V2 = V24,V24 >= 0,V1 = V26,V23 >= 0]). eq(l5(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = 0,V29 >= 0,V25 = V29,V3 = V31,V28 >= 0,V32 >= 0,V31 >= 0,V30 >= 0,V2 = V28,V1 = V32,V5 = V30,V27 = 2]). eq(help1(V2, Out),1,[],[Out = 1,V2 = 1]). eq(help1(V2, Out),1,[],[Out = 2,V33 >= 0,V2 = 2 + V33]). eq(e4(V2, V1, V3, V5, Out),1,[],[Out = 1,V2 = V34,V36 >= 0,V34 >= 0,V3 = V35,V5 = 1,V1 = V36,V35 >= 0]). eq(e4(V2, V1, V3, V5, Out),1,[],[Out = 2,V2 = V37,V39 >= 0,V5 = 2,V37 >= 0,V3 = V38,V1 = V39,V38 >= 0]). eq(e2(V2, V1, V3, V5, Out),1,[],[Out = 1,V2 = V40,V42 >= 0,V40 >= 0,V3 = V41,V5 = 1,V1 = V42,V41 >= 0]). eq(l15(V2, V1, V3, V5, V25, V27, Out),1,[gcd(V44, 0, Ret2),l16(V43, V44, Ret2, V46, 1, V45, Ret)],[Out = Ret,V27 = V45,V25 = 1,V3 = V47,V43 >= 0,V44 >= 0,V45 >= 0,V47 >= 0,V46 >= 0,V2 = V43,V1 = V44,V5 = V46]). eq(l15(V2, V1, V3, V5, V25, V27, Out),1,[gcd(V49, 1 + 0, Ret21),l16(V50, V49, Ret21, V51, 2, V52, Ret1)],[Out = Ret1,V25 = 2,V27 = V52,V3 = V48,V50 >= 0,V49 >= 0,V52 >= 0,V48 >= 0,V51 >= 0,V2 = V50,V1 = V49,V5 = V51]). eq(l13(V2, V1, V3, V5, V25, V27, Out),1,[gcd(0, V53, Ret22),l16(V55, V53, Ret22, V56, 1, V57, Ret3)],[Out = Ret3,V27 = V57,V25 = 1,V3 = V54,V55 >= 0,V53 >= 0,V57 >= 0,V54 >= 0,V56 >= 0,V2 = V55,V1 = V53,V5 = V56]). eq(l13(V2, V1, V3, V5, V25, V27, Out),1,[gcd(1 + 0, V58, Ret23),l16(V60, V58, Ret23, V62, 2, V61, Ret4)],[Out = Ret4,V25 = 2,V27 = V61,V3 = V59,V60 >= 0,V58 >= 0,V61 >= 0,V59 >= 0,V62 >= 0,V2 = V60,V1 = V58,V5 = V62]). eq(m4(V2, V1, V3, V5, Out),1,[monus(V66, V64, Ret24),m5(1 + V66, 1 + V64, Ret24, V65, Ret5)],[Out = Ret5,V2 = 1 + V66,V1 = 1 + V64,V3 = V63,V66 >= 0,V64 >= 0,V5 = V65,V65 >= 0,V63 >= 0]). eq(m2(V2, V1, V3, V5, Out),1,[m4(V69, V67, V68, 1, Ret6)],[Out = Ret6,V2 = V69,V67 >= 0,V69 >= 0,V3 = V68,V5 = 1,V1 = V67,V68 >= 0]). eq(l8(V2, V1, V3, V5, V25, V27, Out),1,[l10(V73, V71, V70, 1, V72, V74, Ret7)],[Out = Ret7,V72 >= 0,V27 = V74,V25 = V72,V3 = V70,V73 >= 0,V71 >= 0,V5 = 1,V74 >= 0,V70 >= 0,V2 = V73,V1 = V71]). eq(l5(V2, V1, V3, V5, V25, V27, Out),1,[l7(V78, V76, V75, V79, V77, 1, Ret8)],[Out = Ret8,V77 >= 0,V25 = V77,V3 = V75,V78 >= 0,V76 >= 0,V27 = 1,V75 >= 0,V79 >= 0,V2 = V78,V1 = V76,V5 = V79]). eq(l2(V2, V1, V3, V5, V25, V27, Out),1,[l3(V82, V80, V83, V84, V81, 1, Ret9)],[Out = Ret9,V81 >= 0,V25 = V81,V3 = V83,V82 >= 0,V80 >= 0,V27 = 1,V83 >= 0,V84 >= 0,V2 = V82,V1 = V80,V5 = V84]). eq(l2(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = V88,V86 >= 0,V25 = V86,V3 = V88,V85 >= 0,V87 >= 0,V88 >= 0,V89 >= 0,V2 = V85,V1 = V87,V5 = V89,V27 = 2]). eq(l11(V2, V1, V3, V5, V25, V27, Out),1,[l14(V91, V92, V94, V90, V93, 1, Ret10)],[Out = Ret10,V93 >= 0,V25 = V93,V3 = V94,V91 >= 0,V92 >= 0,V27 = 1,V94 >= 0,V90 >= 0,V2 = V91,V1 = V92,V5 = V90]). eq(l11(V2, V1, V3, V5, V25, V27, Out),1,[l12(V97, V95, V99, V96, V98, 2, Ret11)],[Out = Ret11,V98 >= 0,V25 = V98,V3 = V99,V97 >= 0,V95 >= 0,V99 >= 0,V96 >= 0,V2 = V97,V1 = V95,V5 = V96,V27 = 2]). eq(help1(V2, Out),1,[],[Out = 1,V2 = 0]). eq(e2(V2, V1, V3, V5, Out),1,[e3(V101, V102, V100, 2, Ret12)],[Out = Ret12,V2 = V101,V102 >= 0,V5 = 2,V101 >= 0,V3 = V100,V1 = V102,V100 >= 0]). eq(bool2Nat(V2, Out),1,[],[Out = 0,V2 = 1]). eq(bool2Nat(V2, Out),1,[],[Out = 1,V2 = 2]). eq(m1(V2, V1, V3, V5, Out),1,[m2(V105, V104, V103, 1, Ret13)],[Out = Ret13,V2 = V105,V1 = V104,V105 >= 0,V3 = V103,V104 >= 0,V5 = V106,V106 >= 0,V103 >= 0]). eq(l9(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = V107,V111 >= 0,V27 = V112,V3 = V110,V25 = V111,V108 >= 0,V112 >= 0,V2 = V107,V107 >= 0,V109 >= 0,V1 = V108,V5 = V109,V110 >= 0]). eq(l6(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = 0,V117 >= 0,V27 = V118,V25 = V117,V3 = V114,V113 >= 0,V115 >= 0,V118 >= 0,V114 >= 0,V116 >= 0,V2 = V113,V1 = V115,V5 = V116]). eq(l4(V2, V1, V3, V5, V25, V27, Out),1,[l5(V124, V119, V120, V121, V122, 1, Ret14)],[Out = Ret14,V122 >= 0,V27 = V123,V1 = V119,V25 = V122,V3 = V120,V124 >= 0,V119 >= 0,V123 >= 0,V120 >= 0,V121 >= 0,V5 = V121,V2 = V124]). eq(l1(V2, V1, V3, V5, V25, V27, Out),1,[l2(V125, V127, V126, V128, V129, 1, Ret15)],[Out = Ret15,V129 >= 0,V27 = V130,V25 = V129,V3 = V126,V125 >= 0,V127 >= 0,V130 >= 0,V126 >= 0,V128 >= 0,V2 = V125,V1 = V127,V5 = V128]). eq(e7(V2, V1, V3, V5, Out),1,[],[Out = 1,V2 = V134,V131 >= 0,V134 >= 0,V3 = V132,V5 = V133,V1 = V131,V133 >= 0,V132 >= 0]). eq(e6(V2, V1, V3, V5, Out),1,[],[Out = 1,V2 = V138,V136 >= 0,V138 >= 0,V3 = V137,V5 = V135,V1 = V136,V135 >= 0,V137 >= 0]). eq(e5(V2, V1, V3, V5, Out),1,[],[Out = 2,V2 = V141,V140 >= 0,V141 >= 0,V3 = V142,V5 = V139,V1 = V140,V139 >= 0,V142 >= 0]). eq(monus(V2, V1, Out),1,[m1(V143, V144, 1, 1, Ret16)],[Out = Ret16,V2 = V143,V144 >= 0,V143 >= 0,V1 = V144]). eq(m5(V2, V1, V3, V5, Out),1,[],[Out = V147,V2 = V145,V148 >= 0,V145 >= 0,V3 = V147,V5 = V146,V1 = V148,V146 >= 0,V147 >= 0]). eq(l7(V2, V1, V3, V5, V25, V27, Out),1,[equal0(V150, V149, Ret31),l8(V150, V149, V154, Ret31, V152, V153, Ret17)],[Out = Ret17,V152 >= 0,V27 = V153,V25 = V152,V3 = V154,V150 >= 0,V149 >= 0,V153 >= 0,V154 >= 0,V151 >= 0,V2 = V150,V1 = V149,V5 = V151]). eq(l3(V2, V1, V3, V5, V25, V27, Out),1,[l4(V157, V156, 0, V158, V159, V160, Ret18)],[Out = Ret18,V159 >= 0,V27 = V160,V25 = V159,V3 = V155,V157 >= 0,V156 >= 0,V160 >= 0,V155 >= 0,V158 >= 0,V2 = V157,V1 = V156,V5 = V158]). eq(l16(V2, V1, V3, V5, V25, V27, Out),1,[],[Out = V161,V165 >= 0,V27 = V166,V25 = V165,V3 = V161,V163 >= 0,V162 >= 0,V166 >= 0,V161 >= 0,V164 >= 0,V2 = V163,V1 = V162,V5 = V164]). eq(l14(V2, V1, V3, V5, V25, V27, Out),1,[monus(V169, V168, Ret41),l15(V169, V168, V167, V170, Ret41, V172, Ret19)],[Out = Ret19,V171 >= 0,V27 = V172,V25 = V171,V3 = V167,V169 >= 0,V168 >= 0,V172 >= 0,V167 >= 0,V170 >= 0,V2 = V169,V1 = V168,V5 = V170]). eq(l12(V2, V1, V3, V5, V25, V27, Out),1,[monus(V174, V176, Ret42),l13(V174, V176, V173, V177, Ret42, V175, Ret20)],[Out = Ret20,V178 >= 0,V27 = V175,V25 = V178,V3 = V173,V174 >= 0,V176 >= 0,V175 >= 0,V173 >= 0,V177 >= 0,V2 = V174,V1 = V176,V5 = V177]). eq(l10(V2, V1, V3, V5, V25, V27, Out),1,[lt(V181, V183, Ret51),l11(V181, V183, V180, V179, V184, Ret51, Ret25)],[Out = Ret25,V184 >= 0,V27 = V182,V25 = V184,V3 = V180,V181 >= 0,V183 >= 0,V182 >= 0,V180 >= 0,V179 >= 0,V2 = V181,V1 = V183,V5 = V179]). eq(gcd(V2, V1, Out),1,[l1(V185, V186, 0, 1, 1, 1, Ret26)],[Out = Ret26,V185 >= 0,V186 >= 0,V2 = V185,V1 = V186]). eq(equal0(V2, V1, Out),1,[e1(V187, V188, 1, 1, Ret27)],[Out = Ret27,V2 = V187,V188 >= 0,V187 >= 0,V1 = V188]). eq(e8(V2, V1, V3, V5, Out),1,[],[Out = V189,V2 = V190,V192 >= 0,V190 >= 0,V3 = V189,V5 = V191,V1 = V192,V191 >= 0,V189 >= 0]). eq(e3(V2, V1, V3, V5, Out),1,[lt(V193, V194, Ret32),e4(V194, V193, V195, Ret32, Ret28)],[Out = Ret28,V2 = V194,V193 >= 0,V194 >= 0,V3 = V195,V5 = V196,V1 = V193,V196 >= 0,V195 >= 0]). eq(e1(V2, V1, V3, V5, Out),1,[lt(V199, V198, Ret33),e2(V199, V198, V200, Ret33, Ret29)],[Out = Ret29,V2 = V199,V198 >= 0,V199 >= 0,V3 = V200,V5 = V197,V1 = V198,V197 >= 0,V200 >= 0]). eq(lt(V2, V1, Out),0,[lt(V202, V201, Ret30)],[Out = Ret30,V1 = 1 + V201,V202 >= 0,V201 >= 0,V2 = 1 + V202]). eq(lt(V2, V1, Out),0,[],[Out = 2,V1 = 1 + V203,V203 >= 0,V2 = 0]). eq(lt(V2, V1, Out),0,[],[Out = 1,V204 >= 0,V2 = V204,V1 = 0]). eq(lt(V2, V1, Out),0,[],[Out = 0,V206 >= 0,V205 >= 0,V2 = V206,V1 = V205]). eq(m2(V2, V1, V3, V5, Out),0,[],[Out = 0,V5 = V209,V208 >= 0,V3 = V210,V207 >= 0,V2 = V208,V1 = V207,V210 >= 0,V209 >= 0]). eq(l8(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V216,V27 = V214,V213 >= 0,V215 >= 0,V3 = V211,V212 >= 0,V214 >= 0,V2 = V213,V1 = V212,V25 = V215,V211 >= 0,V216 >= 0]). eq(l5(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V218,V27 = V221,V217 >= 0,V222 >= 0,V3 = V219,V220 >= 0,V221 >= 0,V2 = V217,V1 = V220,V25 = V222,V219 >= 0,V218 >= 0]). eq(e4(V2, V1, V3, V5, Out),0,[],[Out = 0,V5 = V225,V224 >= 0,V3 = V226,V223 >= 0,V2 = V224,V1 = V223,V226 >= 0,V225 >= 0]). eq(e2(V2, V1, V3, V5, Out),0,[],[Out = 0,V5 = V229,V228 >= 0,V3 = V230,V227 >= 0,V2 = V228,V1 = V227,V230 >= 0,V229 >= 0]). eq(l15(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V234,V27 = V235,V233 >= 0,V236 >= 0,V3 = V231,V232 >= 0,V235 >= 0,V2 = V233,V1 = V232,V25 = V236,V231 >= 0,V234 >= 0]). eq(l13(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V238,V27 = V242,V237 >= 0,V241 >= 0,V3 = V239,V240 >= 0,V242 >= 0,V2 = V237,V1 = V240,V25 = V241,V239 >= 0,V238 >= 0]). eq(m4(V2, V1, V3, V5, Out),0,[],[Out = 0,V5 = V245,V244 >= 0,V3 = V246,V243 >= 0,V2 = V244,V1 = V243,V246 >= 0,V245 >= 0]). eq(l2(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V247,V27 = V250,V248 >= 0,V252 >= 0,V3 = V249,V251 >= 0,V250 >= 0,V2 = V248,V1 = V251,V25 = V252,V249 >= 0,V247 >= 0]). eq(l11(V2, V1, V3, V5, V25, V27, Out),0,[],[Out = 0,V5 = V257,V27 = V254,V253 >= 0,V258 >= 0,V3 = V255,V256 >= 0,V254 >= 0,V2 = V253,V1 = V256,V25 = V258,V255 >= 0,V257 >= 0]). eq(bool2Nat(V2, Out),0,[],[Out = 0,V259 >= 0,V2 = V259]). eq(m3(V2, V1, V3, V5, Out),0,[],[Out = 0,V5 = V263,V260 >= 0,V3 = V261,V262 >= 0,V2 = V260,V1 = V262,V261 >= 0,V263 >= 0]). eq(help1(V2, Out),0,[],[Out = 0,V264 >= 0,V2 = V264]). input_output_vars(m2(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(m3(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(l8(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l5(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(help1(V2,Out),[V2],[Out]). input_output_vars(e4(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(e2(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(l15(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l13(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(m4(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(l2(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l11(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(bool2Nat(V2,Out),[V2],[Out]). input_output_vars(m1(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(l9(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l6(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l4(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l1(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(e7(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(e6(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(e5(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(monus(V2,V1,Out),[V2,V1],[Out]). input_output_vars(m5(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(l7(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l3(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l16(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l14(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l12(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(l10(V2,V1,V3,V5,V25,V27,Out),[V2,V1,V3,V5,V25,V27],[Out]). input_output_vars(gcd(V2,V1,Out),[V2,V1],[Out]). input_output_vars(equal0(V2,V1,Out),[V2,V1],[Out]). input_output_vars(e8(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(e3(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(e1(V2,V1,V3,V5,Out),[V2,V1,V3,V5],[Out]). input_output_vars(lt(V2,V1,Out),[V2,V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [bool2Nat/2] 1. non_recursive : [e4/5] 2. recursive : [lt/3] 3. non_recursive : [e3/5] 4. non_recursive : [e2/5] 5. non_recursive : [e1/5] 6. non_recursive : [e5/5] 7. non_recursive : [e6/5] 8. non_recursive : [e7/5] 9. non_recursive : [e8/5] 10. non_recursive : [equal0/3] 11. non_recursive : [l16/7] 12. non_recursive : [m5/5] 13. recursive [non_tail] : [m1/5,m2/5,m4/5,monus/3] 14. recursive [non_tail] : [gcd/3,l1/7,l10/7,l11/7,l12/7,l13/7,l14/7,l15/7,l2/7,l3/7,l4/7,l5/7,l7/7,l8/7] 15. non_recursive : [help1/2] 16. non_recursive : [l6/7] 17. non_recursive : [l9/7] 18. non_recursive : [m3/5] 19. non_recursive : [start/6] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into bool2Nat/2 1. SCC is partially evaluated into e4/5 2. SCC is partially evaluated into lt/3 3. SCC is partially evaluated into e3/5 4. SCC is partially evaluated into e2/5 5. SCC is partially evaluated into e1/5 6. SCC is completely evaluated into other SCCs 7. SCC is completely evaluated into other SCCs 8. SCC is completely evaluated into other SCCs 9. SCC is completely evaluated into other SCCs 10. SCC is completely evaluated into other SCCs 11. SCC is completely evaluated into other SCCs 12. SCC is completely evaluated into other SCCs 13. SCC is partially evaluated into monus/3 14. SCC is partially evaluated into gcd/3 15. SCC is partially evaluated into help1/2 16. SCC is completely evaluated into other SCCs 17. SCC is completely evaluated into other SCCs 18. SCC is partially evaluated into m3/5 19. SCC is partially evaluated into start/6 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations bool2Nat/2 * CE 134 is refined into CE [137] * CE 133 is refined into CE [138] * CE 135 is refined into CE [139] ### Cost equations --> "Loop" of bool2Nat/2 * CEs [137] --> Loop 37 * CEs [138,139] --> Loop 38 ### Ranking functions of CR bool2Nat(V2,Out) #### Partial ranking functions of CR bool2Nat(V2,Out) ### Specialization of cost equations e4/5 * CE 129 is refined into CE [140] * CE 128 is refined into CE [141] * CE 127 is refined into CE [142] ### Cost equations --> "Loop" of e4/5 * CEs [140] --> Loop 39 * CEs [141] --> Loop 40 * CEs [142] --> Loop 41 ### Ranking functions of CR e4(V2,V1,V3,V5,Out) #### Partial ranking functions of CR e4(V2,V1,V3,V5,Out) ### Specialization of cost equations lt/3 * CE 104 is refined into CE [143] * CE 103 is refined into CE [144] * CE 102 is refined into CE [145] * CE 101 is refined into CE [146] ### Cost equations --> "Loop" of lt/3 * CEs [146] --> Loop 42 * CEs [143] --> Loop 43 * CEs [144] --> Loop 44 * CEs [145] --> Loop 45 ### Ranking functions of CR lt(V2,V1,Out) * RF of phase [42]: [V1,V2] #### Partial ranking functions of CR lt(V2,V1,Out) * Partial RF of phase [42]: - RF of loop [42:1]: V1 V2 ### Specialization of cost equations e3/5 * CE 136 is refined into CE [147,148,149,150,151,152,153,154,155] ### Cost equations --> "Loop" of e3/5 * CEs [154] --> Loop 46 * CEs [152] --> Loop 47 * CEs [147] --> Loop 48 * CEs [148] --> Loop 49 * CEs [149] --> Loop 50 * CEs [150,151,153,155] --> Loop 51 ### Ranking functions of CR e3(V2,V1,V3,V5,Out) #### Partial ranking functions of CR e3(V2,V1,V3,V5,Out) ### Specialization of cost equations e2/5 * CE 132 is refined into CE [156] * CE 131 is refined into CE [157,158,159,160,161] * CE 130 is refined into CE [162] ### Cost equations --> "Loop" of e2/5 * CEs [161] --> Loop 52 * CEs [160] --> Loop 53 * CEs [156,158] --> Loop 54 * CEs [162] --> Loop 55 * CEs [159] --> Loop 56 * CEs [157] --> Loop 57 ### Ranking functions of CR e2(V2,V1,V3,V5,Out) #### Partial ranking functions of CR e2(V2,V1,V3,V5,Out) ### Specialization of cost equations e1/5 * CE 100 is refined into CE [163,164,165,166,167,168,169,170,171] ### Cost equations --> "Loop" of e1/5 * CEs [168] --> Loop 58 * CEs [170] --> Loop 59 * CEs [165] --> Loop 60 * CEs [166] --> Loop 61 * CEs [163] --> Loop 62 * CEs [164,167,169,171] --> Loop 63 ### Ranking functions of CR e1(V2,V1,V3,V5,Out) #### Partial ranking functions of CR e1(V2,V1,V3,V5,Out) ### Specialization of cost equations monus/3 * CE 105 is refined into CE [172] * CE 107 is refined into CE [173] * CE 106 is refined into CE [174] ### Cost equations --> "Loop" of monus/3 * CEs [174] --> Loop 64 * CEs [172,173] --> Loop 65 ### Ranking functions of CR monus(V2,V1,Out) * RF of phase [64]: [V1,V2] #### Partial ranking functions of CR monus(V2,V1,Out) * Partial RF of phase [64]: - RF of loop [64:1]: V1 V2 ### Specialization of cost equations gcd/3 * CE 109 is discarded (unfeasible) * CE 108 is refined into CE [175,176,177,178,179] * CE 110 is refined into CE [180,181,182,183,184,185,186,187] * CE 113 is refined into CE [188,189] * CE 116 is refined into CE [190,191] * CE 117 is refined into CE [192] * CE 118 is refined into CE [193] * CE 115 is discarded (unfeasible) * CE 114 is discarded (unfeasible) * CE 112 is discarded (unfeasible) * CE 111 is discarded (unfeasible) ### Cost equations --> "Loop" of gcd/3 * CEs [177,182,183,190] --> Loop 66 * CEs [175,176,178,179,180,181,184,185,186,187,188,189,191,192,193] --> Loop 67 ### Ranking functions of CR gcd(V2,V1,Out) #### Partial ranking functions of CR gcd(V2,V1,Out) ### Specialization of cost equations help1/2 * CE 124 is refined into CE [194] * CE 126 is refined into CE [195] * CE 123 is refined into CE [196] * CE 125 is refined into CE [197] ### Cost equations --> "Loop" of help1/2 * CEs [194] --> Loop 68 * CEs [195] --> Loop 69 * CEs [196] --> Loop 70 * CEs [197] --> Loop 71 ### Ranking functions of CR help1(V2,Out) #### Partial ranking functions of CR help1(V2,Out) ### Specialization of cost equations m3/5 * CE 120 is refined into CE [198] * CE 122 is refined into CE [199] * CE 119 is refined into CE [200] * CE 121 is refined into CE [201] ### Cost equations --> "Loop" of m3/5 * CEs [198] --> Loop 72 * CEs [199] --> Loop 73 * CEs [200] --> Loop 74 * CEs [201] --> Loop 75 ### Ranking functions of CR m3(V2,V1,V3,V5,Out) #### Partial ranking functions of CR m3(V2,V1,V3,V5,Out) ### Specialization of cost equations start/6 * CE 76 is refined into CE [202] * CE 78 is discarded (unfeasible) * CE 82 is discarded (unfeasible) * CE 2 is refined into CE [203,204,205,206,207] * CE 5 is refined into CE [208,209,210,211,212] * CE 13 is refined into CE [213,214,215,216,217,218,219,220] * CE 16 is refined into CE [221,222,223,224,225,226,227,228] * CE 20 is discarded (unfeasible) * CE 23 is discarded (unfeasible) * CE 27 is discarded (unfeasible) * CE 30 is discarded (unfeasible) * CE 34 is refined into CE [229,230] * CE 37 is refined into CE [231,232] * CE 41 is discarded (unfeasible) * CE 44 is discarded (unfeasible) * CE 48 is discarded (unfeasible) * CE 51 is discarded (unfeasible) * CE 55 is refined into CE [233,234] * CE 58 is refined into CE [235,236] * CE 62 is refined into CE [237] * CE 65 is refined into CE [238] * CE 68 is discarded (unfeasible) * CE 72 is discarded (unfeasible) * CE 70 is refined into CE [239] * CE 80 is refined into CE [240] * CE 74 is refined into CE [241] * CE 84 is refined into CE [242] * CE 87 is refined into CE [243] * CE 1 is refined into CE [244,245,246,247,248] * CE 3 is refined into CE [249,250,251,252,253] * CE 4 is refined into CE [254,255,256,257,258] * CE 6 is refined into CE [259,260,261,262,263] * CE 7 is refined into CE [264] * CE 8 is discarded (unfeasible) * CE 9 is discarded (unfeasible) * CE 10 is discarded (unfeasible) * CE 11 is refined into CE [265] * CE 12 is refined into CE [266,267,268,269,270,271,272,273] * CE 14 is refined into CE [274,275,276,277,278,279,280,281] * CE 15 is refined into CE [282,283,284,285,286,287,288,289] * CE 17 is refined into CE [290,291,292,293,294,295,296,297] * CE 18 is refined into CE [298,299,300,301,302] * CE 19 is discarded (unfeasible) * CE 21 is discarded (unfeasible) * CE 22 is discarded (unfeasible) * CE 24 is discarded (unfeasible) * CE 25 is discarded (unfeasible) * CE 26 is discarded (unfeasible) * CE 28 is discarded (unfeasible) * CE 29 is discarded (unfeasible) * CE 31 is discarded (unfeasible) * CE 32 is discarded (unfeasible) * CE 33 is refined into CE [303,304] * CE 35 is refined into CE [305,306] * CE 36 is refined into CE [307,308] * CE 38 is refined into CE [309,310] * CE 39 is refined into CE [311,312] * CE 40 is discarded (unfeasible) * CE 42 is discarded (unfeasible) * CE 43 is discarded (unfeasible) * CE 45 is discarded (unfeasible) * CE 46 is discarded (unfeasible) * CE 47 is discarded (unfeasible) * CE 49 is discarded (unfeasible) * CE 50 is discarded (unfeasible) * CE 52 is discarded (unfeasible) * CE 53 is discarded (unfeasible) * CE 54 is refined into CE [313,314] * CE 56 is refined into CE [315,316] * CE 57 is refined into CE [317,318] * CE 59 is refined into CE [319,320] * CE 60 is refined into CE [321,322] * CE 61 is refined into CE [323] * CE 63 is refined into CE [324] * CE 64 is refined into CE [325,326] * CE 66 is refined into CE [327] * CE 67 is discarded (unfeasible) * CE 69 is discarded (unfeasible) * CE 71 is discarded (unfeasible) * CE 73 is discarded (unfeasible) * CE 75 is refined into CE [328,329] * CE 77 is discarded (unfeasible) * CE 79 is discarded (unfeasible) * CE 81 is discarded (unfeasible) * CE 83 is discarded (unfeasible) * CE 85 is refined into CE [330,331,332,333,334] * CE 86 is refined into CE [335] * CE 88 is refined into CE [336] * CE 89 is refined into CE [337,338,339,340] * CE 90 is refined into CE [341,342,343,344] * CE 91 is refined into CE [345,346,347] * CE 92 is refined into CE [348,349,350,351,352,353] * CE 93 is refined into CE [354,355] * CE 94 is refined into CE [356] * CE 95 is refined into CE [357] * CE 96 is refined into CE [358,359,360,361,362] * CE 97 is refined into CE [363,364,365,366,367] * CE 98 is refined into CE [368,369,370,371,372] * CE 99 is refined into CE [373,374,375,376,377] ### Cost equations --> "Loop" of start/6 * CEs [202] --> Loop 76 * CEs [239,240] --> Loop 77 * CEs [241,242] --> Loop 78 * CEs [243,300,301,302,312,322,345,350] --> Loop 79 * CEs [204,205,206,207,209,210,211,212,215,216,217,218,219,220,223,224,225,226,227,228,230,232,233,234,235,236,237,238] --> Loop 80 * CEs [346,349,351,352] --> Loop 81 * CEs [246,251,256,261,268,269,276,277,284,285,292,293,299,313,315,317,319,321,325,331,360,365,370,374] --> Loop 82 * CEs [354] --> Loop 83 * CEs [338,342] --> Loop 84 * CEs [203,208,213,214,221,222,229,231,244,245,247,248,249,250,252,253,254,255,257,258,259,260,262,263,264,265,266,267,270,271,272,273,274,275,278,279,280,281,282,283,286,287,288,289,290,291,294,295,296,297,298,303,304,305,306,307,308,309,310,311,314,316,318,320,323,324,326,327,328,329,330,332,333,334,335,336,337,339,340,341,343,344,347,348,353,355,356,357,358,359,361,362,363,364,366,367,368,369,371,372,373,375,376,377] --> Loop 85 ### Ranking functions of CR start(V2,V1,V3,V5,V25,V27) #### Partial ranking functions of CR start(V2,V1,V3,V5,V25,V27) Computing Bounds ===================================== #### Cost of chains of bool2Nat(V2,Out): * Chain [38]: 1 with precondition: [Out=0,V2>=0] * Chain [37]: 1 with precondition: [V2=2,Out=1] #### Cost of chains of e4(V2,V1,V3,V5,Out): * Chain [41]: 1 with precondition: [V5=1,Out=1,V2>=0,V1>=0,V3>=0] * Chain [40]: 1 with precondition: [V5=2,Out=2,V2>=0,V1>=0,V3>=0] * Chain [39]: 0 with precondition: [Out=0,V2>=0,V1>=0,V3>=0,V5>=0] #### Cost of chains of lt(V2,V1,Out): * Chain [[42],45]: 0 with precondition: [Out=2,V2>=1,V1>=V2+1] * Chain [[42],44]: 0 with precondition: [Out=1,V1>=1,V2>=V1] * Chain [[42],43]: 0 with precondition: [Out=0,V2>=1,V1>=1] * Chain [45]: 0 with precondition: [V2=0,Out=2,V1>=1] * Chain [44]: 0 with precondition: [V1=0,Out=1,V2>=0] * Chain [43]: 0 with precondition: [Out=0,V2>=0,V1>=0] #### Cost of chains of e3(V2,V1,V3,V5,Out): * Chain [51]: 1 with precondition: [Out=0,V2>=0,V1>=0,V3>=0,V5>=0] * Chain [50]: 2 with precondition: [V2=0,Out=1,V1>=0,V3>=0,V5>=0] * Chain [49]: 1 with precondition: [V1=0,Out=0,V2>=1,V3>=0,V5>=0] * Chain [48]: 2 with precondition: [V1=0,Out=2,V2>=1,V3>=0,V5>=0] * Chain [47]: 2 with precondition: [Out=1,V2>=1,V3>=0,V5>=0,V1>=V2] * Chain [46]: 2 with precondition: [Out=2,V1>=1,V3>=0,V5>=0,V2>=V1+1] #### Cost of chains of e2(V2,V1,V3,V5,Out): * Chain [57]: 3 with precondition: [V2=0,V5=2,Out=1,V1>=0,V3>=0] * Chain [56]: 3 with precondition: [V1=0,V5=2,Out=2,V2>=1,V3>=0] * Chain [55]: 1 with precondition: [V5=1,Out=1,V2>=0,V1>=0,V3>=0] * Chain [54]: 2 with precondition: [Out=0,V2>=0,V1>=0,V3>=0,V5>=0] * Chain [53]: 3 with precondition: [V5=2,Out=1,V2>=1,V3>=0,V1>=V2] * Chain [52]: 3 with precondition: [V5=2,Out=2,V1>=1,V3>=0,V2>=V1+1] #### Cost of chains of e1(V2,V1,V3,V5,Out): * Chain [63]: 3 with precondition: [Out=0,V2>=0,V1>=0,V3>=0,V5>=0] * Chain [62]: 4 with precondition: [V2=0,Out=1,V1>=1,V3>=0,V5>=0] * Chain [61]: 3 with precondition: [V1=0,Out=0,V2>=0,V3>=0,V5>=0] * Chain [60]: 2 with precondition: [V1=0,Out=1,V2>=0,V3>=0,V5>=0] * Chain [59]: 4 with precondition: [Out=1,V2>=1,V3>=0,V5>=0,V1>=V2+1] * Chain [58]: 2 with precondition: [Out=1,V1>=1,V3>=0,V5>=0,V2>=V1] #### Cost of chains of monus(V2,V1,Out): * Chain [[64],65]: 5*it(64)+3 Such that:it(64) =< V1 with precondition: [Out=0,V2>=1,V1>=1] * Chain [65]: 3 with precondition: [Out=0,V2>=0,V1>=0] #### Cost of chains of gcd(V2,V1,Out): * Chain [67]: 15*s(2)+19 Such that:aux(1) =< V1 s(2) =< aux(1) with precondition: [Out=0,V2>=0,V1>=0] * Chain [66]: 17 with precondition: [V1=0,Out=0,V2>=0] #### Cost of chains of help1(V2,Out): * Chain [71]: 1 with precondition: [V2=0,Out=1] * Chain [70]: 1 with precondition: [V2=1,Out=1] * Chain [69]: 0 with precondition: [Out=0,V2>=0] * Chain [68]: 1 with precondition: [Out=2,V2>=2] #### Cost of chains of m3(V2,V1,V3,V5,Out): * Chain [75]: 1 with precondition: [V2=0,Out=1,V1>=0,V3>=0,V5>=0] * Chain [74]: 1 with precondition: [V2=1,Out=1,V1>=0,V3>=0,V5>=0] * Chain [73]: 0 with precondition: [Out=0,V2>=0,V1>=0,V3>=0,V5>=0] * Chain [72]: 1 with precondition: [Out=2,V2>=2,V1>=0,V3>=0,V5>=0] #### Cost of chains of start(V2,V1,V3,V5,V25,V27): * Chain [85]: 125*s(8)+19 Such that:aux(2) =< V1 s(8) =< aux(2) with precondition: [V2>=0] * Chain [84]: 1 with precondition: [V2=1] * Chain [83]: 1 with precondition: [V2=2] * Chain [82]: 16 with precondition: [V1=0,V2>=0] * Chain [81]: 3 with precondition: [V5=2,V2>=0,V1>=0,V3>=0] * Chain [80]: 25*s(38)+17 Such that:aux(3) =< V1 s(38) =< aux(3) with precondition: [V27=1,V2>=0,V1>=0,V3>=0,V5>=0,V25>=0] * Chain [79]: 15*s(45)+7 Such that:aux(4) =< V1 s(45) =< aux(4) with precondition: [V5=1,V2>=0,V1>=0,V3>=0] * Chain [78]: 15*s(51)+21 Such that:s(50) =< V1 s(51) =< s(50) with precondition: [V25=1,V2>=0,V1>=0,V3>=0,V5>=0,V27>=0] * Chain [77]: 15*s(53)+15*s(55)+21 Such that:s(52) =< 1 s(54) =< V1 s(53) =< s(52) s(55) =< s(54) with precondition: [V25=2,V2>=0,V1>=0,V3>=0,V5>=0,V27>=0] * Chain [76]: 5*s(56)+5 Such that:s(56) =< V1 with precondition: [V27=2,V2>=0,V1>=0,V3>=0,V5>=0,V25>=0] Closed-form bounds of start(V2,V1,V3,V5,V25,V27): ------------------------------------- * Chain [85] with precondition: [V2>=0] - Upper bound: nat(V1)*125+19 - Complexity: n * Chain [84] with precondition: [V2=1] - Upper bound: 1 - Complexity: constant * Chain [83] with precondition: [V2=2] - Upper bound: 1 - Complexity: constant * Chain [82] with precondition: [V1=0,V2>=0] - Upper bound: 16 - Complexity: constant * Chain [81] with precondition: [V5=2,V2>=0,V1>=0,V3>=0] - Upper bound: 3 - Complexity: constant * Chain [80] with precondition: [V27=1,V2>=0,V1>=0,V3>=0,V5>=0,V25>=0] - Upper bound: 25*V1+17 - Complexity: n * Chain [79] with precondition: [V5=1,V2>=0,V1>=0,V3>=0] - Upper bound: 15*V1+7 - Complexity: n * Chain [78] with precondition: [V25=1,V2>=0,V1>=0,V3>=0,V5>=0,V27>=0] - Upper bound: 15*V1+21 - Complexity: n * Chain [77] with precondition: [V25=2,V2>=0,V1>=0,V3>=0,V5>=0,V27>=0] - Upper bound: 15*V1+36 - Complexity: n * Chain [76] with precondition: [V27=2,V2>=0,V1>=0,V3>=0,V5>=0,V25>=0] - Upper bound: 5*V1+5 - Complexity: n ### Maximum cost of start(V2,V1,V3,V5,V25,V27): max([15,nat(V1)*10+2+max([29,nat(V1)*100+2+(nat(V1)*10+10)])+(nat(V1)*5+4)])+1 Asymptotic class: n * Total analysis performed in 3176 ms. ---------------------------------------- (14) BOUNDS(1, n^1) ---------------------------------------- (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (16) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False m2(S(S(x)), b, res, True) -> True m2(0, b, res, True) -> False m3(S(0), b, res, t) -> False m3(S(S(x)), b, res, t) -> True m3(0, b, res, t) -> False l8(res, y, res', True, mtmp, t) -> res l5(x, y, res, tmp, mtmp, True) -> 0 help1(S(0)) -> False help1(S(S(x))) -> True e4(a, b, res, False) -> False e4(a, b, res, True) -> True e2(a, b, res, False) -> False l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) m2(a, b, res, False) -> m4(a, b, res, False) l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, True) -> res l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) help1(0) -> False e2(a, b, res, True) -> e3(a, b, res, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(a, x, res, t) -> m2(a, x, res, False) l9(res, y, res', tmp, mtmp, t) -> res l6(x, y, res, tmp, mtmp, t) -> 0 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) e7(a, b, res, t) -> False e6(a, b, res, t) -> False e5(a, b, res, t) -> True monus(a, b) -> m1(a, b, False, False) m5(a, b, res, t) -> res l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) l16(x, y, res, tmp, mtmp, t) -> res l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) gcd(x, y) -> l1(x, y, 0, False, False, False) equal0(a, b) -> e1(a, b, False, False) e8(a, b, res, t) -> res e3(a, b, res, t) -> e4(a, b, res, <(b, a)) e1(a, b, res, t) -> e2(a, b, res, <(a, b)) The (relative) TRS S consists of the following rules: <(S(x), S(y)) -> <(x, y) <(0, S(y)) -> True <(x, 0) -> False Rewrite Strategy: INNERMOST ---------------------------------------- (17) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence monus(S(x'1_0), S(x2_0)) ->^+ m5(S(x'1_0), S(x2_0), monus(x'1_0, x2_0), False) gives rise to a decreasing loop by considering the right hand sides subterm at position [2]. The pumping substitution is [x'1_0 / S(x'1_0), x2_0 / S(x2_0)]. The result substitution is [ ]. ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) 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, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False m2(S(S(x)), b, res, True) -> True m2(0, b, res, True) -> False m3(S(0), b, res, t) -> False m3(S(S(x)), b, res, t) -> True m3(0, b, res, t) -> False l8(res, y, res', True, mtmp, t) -> res l5(x, y, res, tmp, mtmp, True) -> 0 help1(S(0)) -> False help1(S(S(x))) -> True e4(a, b, res, False) -> False e4(a, b, res, True) -> True e2(a, b, res, False) -> False l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) m2(a, b, res, False) -> m4(a, b, res, False) l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, True) -> res l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) help1(0) -> False e2(a, b, res, True) -> e3(a, b, res, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(a, x, res, t) -> m2(a, x, res, False) l9(res, y, res', tmp, mtmp, t) -> res l6(x, y, res, tmp, mtmp, t) -> 0 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) e7(a, b, res, t) -> False e6(a, b, res, t) -> False e5(a, b, res, t) -> True monus(a, b) -> m1(a, b, False, False) m5(a, b, res, t) -> res l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) l16(x, y, res, tmp, mtmp, t) -> res l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) gcd(x, y) -> l1(x, y, 0, False, False, False) equal0(a, b) -> e1(a, b, False, False) e8(a, b, res, t) -> res e3(a, b, res, t) -> e4(a, b, res, <(b, a)) e1(a, b, res, t) -> e2(a, b, res, <(a, b)) The (relative) TRS S consists of the following rules: <(S(x), S(y)) -> <(x, y) <(0, S(y)) -> True <(x, 0) -> False Rewrite Strategy: INNERMOST ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^1, INF) ---------------------------------------- (22) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: m2(S(0), b, res, True) -> False m2(S(S(x)), b, res, True) -> True m2(0, b, res, True) -> False m3(S(0), b, res, t) -> False m3(S(S(x)), b, res, t) -> True m3(0, b, res, t) -> False l8(res, y, res', True, mtmp, t) -> res l5(x, y, res, tmp, mtmp, True) -> 0 help1(S(0)) -> False help1(S(S(x))) -> True e4(a, b, res, False) -> False e4(a, b, res, True) -> True e2(a, b, res, False) -> False l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) m2(a, b, res, False) -> m4(a, b, res, False) l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) l2(x, y, res, tmp, mtmp, True) -> res l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) help1(0) -> False e2(a, b, res, True) -> e3(a, b, res, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(a, x, res, t) -> m2(a, x, res, False) l9(res, y, res', tmp, mtmp, t) -> res l6(x, y, res, tmp, mtmp, t) -> 0 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) e7(a, b, res, t) -> False e6(a, b, res, t) -> False e5(a, b, res, t) -> True monus(a, b) -> m1(a, b, False, False) m5(a, b, res, t) -> res l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) l16(x, y, res, tmp, mtmp, t) -> res l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) gcd(x, y) -> l1(x, y, 0, False, False, False) equal0(a, b) -> e1(a, b, False, False) e8(a, b, res, t) -> res e3(a, b, res, t) -> e4(a, b, res, <(b, a)) e1(a, b, res, t) -> e2(a, b, res, <(a, b)) The (relative) TRS S consists of the following rules: <(S(x), S(y)) -> <(x, y) <(0, S(y)) -> True <(x, 0) -> False Rewrite Strategy: INNERMOST