/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxRelTRS (1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 92 ms] (2) CpxRelTRS (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (4) CdtProblem (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 158 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 72 ms] (16) CdtProblem (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CdtProblem (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms] (20) CdtProblem (21) CdtKnowledgeProof [FINISHED, 0 ms] (22) BOUNDS(1, 1) (23) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 4 ms] (24) TRS for Loop Detection (25) DecreasingLoopProof [LOWER BOUND(ID), 418 ms] (26) BEST (27) proven lower bound (28) LowerBoundPropagationProof [FINISHED, 0 ms] (29) BOUNDS(n^1, INF) (30) 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) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost 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) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False m2(S(0), z0, z1, True) -> False m2(S(S(z0)), z1, z2, True) -> True m2(0, z0, z1, True) -> False m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m3(S(0), z0, z1, z2) -> False m3(S(S(z0)), z1, z2, z3) -> True m3(0, z0, z1, z2) -> False l8(z0, z1, z2, True, z3, z4) -> z0 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) l5(z0, z1, z2, z3, z4, True) -> 0 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) help1(S(0)) -> False help1(S(S(z0))) -> True help1(0) -> False e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) l2(z0, z1, z2, z3, z4, True) -> z2 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) l9(z0, z1, z2, z3, z4, z5) -> z0 l6(z0, z1, z2, z3, z4, z5) -> 0 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) e7(z0, z1, z2, z3) -> False e6(z0, z1, z2, z3) -> False e5(z0, z1, z2, z3) -> True monus(z0, z1) -> m1(z0, z1, False, False) m5(z0, z1, z2, z3) -> z2 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) l16(z0, z1, z2, z3, z4, z5) -> z2 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) equal0(z0, z1) -> e1(z0, z1, False, False) e8(z0, z1, z2, z3) -> z2 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) <'(0, S(z0)) -> c1 <'(z0, 0) -> c2 M2(S(0), z0, z1, True) -> c3 M2(S(S(z0)), z1, z2, True) -> c4 M2(0, z0, z1, True) -> c5 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) M3(S(0), z0, z1, z2) -> c7 M3(S(S(z0)), z1, z2, z3) -> c8 M3(0, z0, z1, z2) -> c9 L8(z0, z1, z2, True, z3, z4) -> c10 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, True) -> c12 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) HELP1(S(0)) -> c14 HELP1(S(S(z0))) -> c15 HELP1(0) -> c16 E4(z0, z1, z2, False) -> c17 E4(z0, z1, z2, True) -> c18 E2(z0, z1, z2, False) -> c19 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L2(z0, z1, z2, z3, z4, True) -> c27 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) BOOL2NAT(False) -> c30 BOOL2NAT(True) -> c31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L9(z0, z1, z2, z3, z4, z5) -> c33 L6(z0, z1, z2, z3, z4, z5) -> c34 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) E7(z0, z1, z2, z3) -> c37 E6(z0, z1, z2, z3) -> c38 E5(z0, z1, z2, z3) -> c39 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) M5(z0, z1, z2, z3) -> c41 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L16(z0, z1, z2, z3, z4, z5) -> c44 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E8(z0, z1, z2, z3) -> c50 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) S tuples: M2(S(0), z0, z1, True) -> c3 M2(S(S(z0)), z1, z2, True) -> c4 M2(0, z0, z1, True) -> c5 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) M3(S(0), z0, z1, z2) -> c7 M3(S(S(z0)), z1, z2, z3) -> c8 M3(0, z0, z1, z2) -> c9 L8(z0, z1, z2, True, z3, z4) -> c10 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, True) -> c12 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) HELP1(S(0)) -> c14 HELP1(S(S(z0))) -> c15 HELP1(0) -> c16 E4(z0, z1, z2, False) -> c17 E4(z0, z1, z2, True) -> c18 E2(z0, z1, z2, False) -> c19 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L2(z0, z1, z2, z3, z4, True) -> c27 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) BOOL2NAT(False) -> c30 BOOL2NAT(True) -> c31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L9(z0, z1, z2, z3, z4, z5) -> c33 L6(z0, z1, z2, z3, z4, z5) -> c34 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) E7(z0, z1, z2, z3) -> c37 E6(z0, z1, z2, z3) -> c38 E5(z0, z1, z2, z3) -> c39 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) M5(z0, z1, z2, z3) -> c41 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L16(z0, z1, z2, z3, z4, z5) -> c44 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E8(z0, z1, z2, z3) -> c50 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) K tuples:none Defined Rule Symbols: m2_4, m3_4, l8_6, l5_6, help1_1, e4_4, e2_4, l15_6, l13_6, m4_4, l2_6, l11_6, bool2Nat_1, m1_4, l9_6, l6_6, l4_6, l1_6, e7_4, e6_4, e5_4, monus_2, m5_4, l7_6, l3_6, l16_6, l14_6, l12_6, l10_6, gcd_2, equal0_2, e8_4, e3_4, e1_4, <_2 Defined Pair Symbols: <'_2, M2_4, M3_4, L8_6, L5_6, HELP1_1, E4_4, E2_4, L15_6, L13_6, M4_4, L2_6, L11_6, BOOL2NAT_1, M1_4, L9_6, L6_6, L4_6, L1_6, E7_4, E6_4, E5_4, MONUS_2, M5_4, L7_6, L3_6, L16_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, E8_4, E3_4, E1_4 Compound Symbols: c_1, c1, c2, c3, c4, c5, c6_1, c7, c8, c9, c10, c11_1, c12, c13_1, c14, c15, c16, c17, c18, c19, c20_1, c21_2, c22_2, c23_2, c24_2, c25_2, c26_1, c27, c28_1, c29_1, c30, c31, c32_1, c33, c34, c35_1, c36_1, c37, c38, c39, c40_1, c41, c42_2, c43_1, c44, c45_2, c46_2, c47_2, c48_1, c49_1, c50, c51_2, c52_2 ---------------------------------------- (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 27 trailing nodes: M5(z0, z1, z2, z3) -> c41 M3(S(S(z0)), z1, z2, z3) -> c8 M2(S(0), z0, z1, True) -> c3 HELP1(S(S(z0))) -> c15 HELP1(S(0)) -> c14 E2(z0, z1, z2, False) -> c19 L8(z0, z1, z2, True, z3, z4) -> c10 L2(z0, z1, z2, z3, z4, True) -> c27 L16(z0, z1, z2, z3, z4, z5) -> c44 <'(0, S(z0)) -> c1 E8(z0, z1, z2, z3) -> c50 M3(0, z0, z1, z2) -> c9 M3(S(0), z0, z1, z2) -> c7 BOOL2NAT(True) -> c31 <'(z0, 0) -> c2 E7(z0, z1, z2, z3) -> c37 E6(z0, z1, z2, z3) -> c38 M2(S(S(z0)), z1, z2, True) -> c4 L5(z0, z1, z2, z3, z4, True) -> c12 L6(z0, z1, z2, z3, z4, z5) -> c34 L9(z0, z1, z2, z3, z4, z5) -> c33 E4(z0, z1, z2, True) -> c18 E5(z0, z1, z2, z3) -> c39 BOOL2NAT(False) -> c30 E4(z0, z1, z2, False) -> c17 HELP1(0) -> c16 M2(0, z0, z1, True) -> c5 ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False m2(S(0), z0, z1, True) -> False m2(S(S(z0)), z1, z2, True) -> True m2(0, z0, z1, True) -> False m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m3(S(0), z0, z1, z2) -> False m3(S(S(z0)), z1, z2, z3) -> True m3(0, z0, z1, z2) -> False l8(z0, z1, z2, True, z3, z4) -> z0 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) l5(z0, z1, z2, z3, z4, True) -> 0 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) help1(S(0)) -> False help1(S(S(z0))) -> True help1(0) -> False e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) l2(z0, z1, z2, z3, z4, True) -> z2 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) l9(z0, z1, z2, z3, z4, z5) -> z0 l6(z0, z1, z2, z3, z4, z5) -> 0 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) e7(z0, z1, z2, z3) -> False e6(z0, z1, z2, z3) -> False e5(z0, z1, z2, z3) -> True monus(z0, z1) -> m1(z0, z1, False, False) m5(z0, z1, z2, z3) -> z2 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) l16(z0, z1, z2, z3, z4, z5) -> z2 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) equal0(z0, z1) -> e1(z0, z1, False, False) e8(z0, z1, z2, z3) -> z2 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) K tuples:none Defined Rule Symbols: m2_4, m3_4, l8_6, l5_6, help1_1, e4_4, e2_4, l15_6, l13_6, m4_4, l2_6, l11_6, bool2Nat_1, m1_4, l9_6, l6_6, l4_6, l1_6, e7_4, e6_4, e5_4, monus_2, m5_4, l7_6, l3_6, l16_6, l14_6, l12_6, l10_6, gcd_2, equal0_2, e8_4, e3_4, e1_4, <_2 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L15_6, L13_6, M4_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c21_2, c22_2, c23_2, c24_2, c25_2, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c51_2, c52_2 ---------------------------------------- (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 6 trailing tuple parts ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False m2(S(0), z0, z1, True) -> False m2(S(S(z0)), z1, z2, True) -> True m2(0, z0, z1, True) -> False m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m3(S(0), z0, z1, z2) -> False m3(S(S(z0)), z1, z2, z3) -> True m3(0, z0, z1, z2) -> False l8(z0, z1, z2, True, z3, z4) -> z0 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) l5(z0, z1, z2, z3, z4, True) -> 0 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) help1(S(0)) -> False help1(S(S(z0))) -> True help1(0) -> False e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) l2(z0, z1, z2, z3, z4, True) -> z2 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) l9(z0, z1, z2, z3, z4, z5) -> z0 l6(z0, z1, z2, z3, z4, z5) -> 0 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) e7(z0, z1, z2, z3) -> False e6(z0, z1, z2, z3) -> False e5(z0, z1, z2, z3) -> True monus(z0, z1) -> m1(z0, z1, False, False) m5(z0, z1, z2, z3) -> z2 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) l16(z0, z1, z2, z3, z4, z5) -> z2 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) equal0(z0, z1) -> e1(z0, z1, False, False) e8(z0, z1, z2, z3) -> z2 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) K tuples:none Defined Rule Symbols: m2_4, m3_4, l8_6, l5_6, help1_1, e4_4, e2_4, l15_6, l13_6, m4_4, l2_6, l11_6, bool2Nat_1, m1_4, l9_6, l6_6, l4_6, l1_6, e7_4, e6_4, e5_4, monus_2, m5_4, l7_6, l3_6, l16_6, l14_6, l12_6, l10_6, gcd_2, equal0_2, e8_4, e3_4, e1_4, <_2 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, E1_4, L15_6, L13_6, M4_4, E3_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c52_2, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1 ---------------------------------------- (9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False m2(S(0), z0, z1, True) -> False m2(S(S(z0)), z1, z2, True) -> True m2(0, z0, z1, True) -> False m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m3(S(0), z0, z1, z2) -> False m3(S(S(z0)), z1, z2, z3) -> True m3(0, z0, z1, z2) -> False l8(z0, z1, z2, True, z3, z4) -> z0 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) l5(z0, z1, z2, z3, z4, True) -> 0 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) help1(S(0)) -> False help1(S(S(z0))) -> True help1(0) -> False e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) l2(z0, z1, z2, z3, z4, True) -> z2 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) l9(z0, z1, z2, z3, z4, z5) -> z0 l6(z0, z1, z2, z3, z4, z5) -> 0 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) e7(z0, z1, z2, z3) -> False e6(z0, z1, z2, z3) -> False e5(z0, z1, z2, z3) -> True monus(z0, z1) -> m1(z0, z1, False, False) m5(z0, z1, z2, z3) -> z2 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) l16(z0, z1, z2, z3, z4, z5) -> z2 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) equal0(z0, z1) -> e1(z0, z1, False, False) e8(z0, z1, z2, z3) -> z2 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) K tuples:none Defined Rule Symbols: m2_4, m3_4, l8_6, l5_6, help1_1, e4_4, e2_4, l15_6, l13_6, m4_4, l2_6, l11_6, bool2Nat_1, m1_4, l9_6, l6_6, l4_6, l1_6, e7_4, e6_4, e5_4, monus_2, m5_4, l7_6, l3_6, l16_6, l14_6, l12_6, l10_6, gcd_2, equal0_2, e8_4, e3_4, e1_4, <_2 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: m2(S(0), z0, z1, True) -> False m2(S(S(z0)), z1, z2, True) -> True m2(0, z0, z1, True) -> False m3(S(0), z0, z1, z2) -> False m3(S(S(z0)), z1, z2, z3) -> True m3(0, z0, z1, z2) -> False l8(z0, z1, z2, True, z3, z4) -> z0 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) l5(z0, z1, z2, z3, z4, True) -> 0 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) help1(S(0)) -> False help1(S(S(z0))) -> True help1(0) -> False l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) l2(z0, z1, z2, z3, z4, True) -> z2 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) bool2Nat(False) -> 0 bool2Nat(True) -> S(0) l9(z0, z1, z2, z3, z4, z5) -> z0 l6(z0, z1, z2, z3, z4, z5) -> 0 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) e7(z0, z1, z2, z3) -> False e6(z0, z1, z2, z3) -> False e5(z0, z1, z2, z3) -> True l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) l16(z0, z1, z2, z3, z4, z5) -> z2 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) e8(z0, z1, z2, z3) -> z2 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: equal0(z0, z1) -> e1(z0, z1, False, False) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True monus(z0, z1) -> m1(z0, z1, False, False) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) K tuples:none Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) We considered the (Usable) Rules: m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) monus(z0, z1) -> m1(z0, z1, False, False) And the Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(<(x_1, x_2)) = x_2 POL(<'(x_1, x_2)) = 0 POL(E1(x_1, x_2, x_3, x_4)) = [1] POL(E2(x_1, x_2, x_3, x_4)) = [1] POL(E3(x_1, x_2, x_3, x_4)) = [1] POL(EQUAL0(x_1, x_2)) = [1] POL(False) = [1] POL(GCD(x_1, x_2)) = [1] POL(L1(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L10(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L11(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L12(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 POL(L14(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L15(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 POL(L2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 POL(L3(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L4(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L5(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 POL(L7(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L8(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(M1(x_1, x_2, x_3, x_4)) = 0 POL(M2(x_1, x_2, x_3, x_4)) = 0 POL(M4(x_1, x_2, x_3, x_4)) = 0 POL(MONUS(x_1, x_2)) = 0 POL(S(x_1)) = 0 POL(True) = [1] POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c20(x_1)) = x_1 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23(x_1)) = x_1 POL(c24(x_1)) = x_1 POL(c25(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c28(x_1)) = x_1 POL(c29(x_1)) = x_1 POL(c32(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42(x_1, x_2)) = x_1 + x_2 POL(c43(x_1)) = x_1 POL(c45(x_1, x_2)) = x_1 + x_2 POL(c46(x_1, x_2)) = x_1 + x_2 POL(c47(x_1, x_2)) = x_1 + x_2 POL(c48(x_1)) = x_1 POL(c49(x_1)) = x_1 POL(c51(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(e1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_4 POL(e2(x_1, x_2, x_3, x_4)) = x_1 + x_4 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_4 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 POL(m1(x_1, x_2, x_3, x_4)) = 0 POL(m2(x_1, x_2, x_3, x_4)) = 0 POL(m4(x_1, x_2, x_3, x_4)) = 0 POL(m5(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 POL(monus(x_1, x_2)) = 0 ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: equal0(z0, z1) -> e1(z0, z1, False, False) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True monus(z0, z1) -> m1(z0, z1, False, False) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) K tuples: E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) We considered the (Usable) Rules: m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) monus(z0, z1) -> m1(z0, z1, False, False) And the Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(<(x_1, x_2)) = x_2 POL(<'(x_1, x_2)) = 0 POL(E1(x_1, x_2, x_3, x_4)) = 0 POL(E2(x_1, x_2, x_3, x_4)) = 0 POL(E3(x_1, x_2, x_3, x_4)) = 0 POL(EQUAL0(x_1, x_2)) = 0 POL(False) = [1] POL(GCD(x_1, x_2)) = [1] POL(L1(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L10(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L11(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L12(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 POL(L14(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L15(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 POL(L2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 POL(L3(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 POL(L4(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L5(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L7(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(L8(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 POL(M1(x_1, x_2, x_3, x_4)) = 0 POL(M2(x_1, x_2, x_3, x_4)) = 0 POL(M4(x_1, x_2, x_3, x_4)) = 0 POL(MONUS(x_1, x_2)) = 0 POL(S(x_1)) = 0 POL(True) = [1] POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c20(x_1)) = x_1 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23(x_1)) = x_1 POL(c24(x_1)) = x_1 POL(c25(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c28(x_1)) = x_1 POL(c29(x_1)) = x_1 POL(c32(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42(x_1, x_2)) = x_1 + x_2 POL(c43(x_1)) = x_1 POL(c45(x_1, x_2)) = x_1 + x_2 POL(c46(x_1, x_2)) = x_1 + x_2 POL(c47(x_1, x_2)) = x_1 + x_2 POL(c48(x_1)) = x_1 POL(c49(x_1)) = x_1 POL(c51(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(e1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_4 POL(e2(x_1, x_2, x_3, x_4)) = x_1 + x_4 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_4 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 POL(m1(x_1, x_2, x_3, x_4)) = 0 POL(m2(x_1, x_2, x_3, x_4)) = 0 POL(m4(x_1, x_2, x_3, x_4)) = 0 POL(m5(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 POL(monus(x_1, x_2)) = 0 ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: equal0(z0, z1) -> e1(z0, z1, False, False) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True monus(z0, z1) -> m1(z0, z1, False, False) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) K tuples: E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) The following tuples could be moved from S to K by knowledge propagation: L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: equal0(z0, z1) -> e1(z0, z1, False, False) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True monus(z0, z1) -> m1(z0, z1, False, False) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) K tuples: E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) We considered the (Usable) Rules: m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) monus(z0, z1) -> m1(z0, z1, False, False) And the Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(<(x_1, x_2)) = x_2 POL(<'(x_1, x_2)) = 0 POL(E1(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(E2(x_1, x_2, x_3, x_4)) = x_3 POL(E3(x_1, x_2, x_3, x_4)) = x_3 POL(EQUAL0(x_1, x_2)) = 0 POL(False) = 0 POL(GCD(x_1, x_2)) = [1] + x_1 + x_2 POL(L1(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L10(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L11(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 POL(L12(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_2 + x_3 + x_4 + x_5 POL(L14(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L15(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_2 + x_3 + x_4 + x_5 + x_6 POL(L2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L3(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L4(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L5(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L7(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 POL(L8(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_1 + x_2 + x_3 + x_5 + x_6 POL(M1(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 POL(M2(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 POL(M4(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 POL(MONUS(x_1, x_2)) = x_1 POL(S(x_1)) = [1] + x_1 POL(True) = [1] POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c20(x_1)) = x_1 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23(x_1)) = x_1 POL(c24(x_1)) = x_1 POL(c25(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c28(x_1)) = x_1 POL(c29(x_1)) = x_1 POL(c32(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42(x_1, x_2)) = x_1 + x_2 POL(c43(x_1)) = x_1 POL(c45(x_1, x_2)) = x_1 + x_2 POL(c46(x_1, x_2)) = x_1 + x_2 POL(c47(x_1, x_2)) = x_1 + x_2 POL(c48(x_1)) = x_1 POL(c49(x_1)) = x_1 POL(c51(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(e1(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4 POL(e2(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_3 + x_4 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_3 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_3 + x_4 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 POL(m1(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(m2(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(m4(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(m5(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(monus(x_1, x_2)) = 0 ---------------------------------------- (20) Obligation: Complexity Dependency Tuples Problem Rules: equal0(z0, z1) -> e1(z0, z1, False, False) e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) e2(z0, z1, z2, False) -> False e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) <(S(z0), S(z1)) -> <(z0, z1) <(0, S(z0)) -> True <(z0, 0) -> False e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) e4(z0, z1, z2, False) -> False e4(z0, z1, z2, True) -> True monus(z0, z1) -> m1(z0, z1, False, False) m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) m5(z0, z1, z2, z3) -> z2 Tuples: <'(S(z0), S(z1)) -> c(<'(z0, z1)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) S tuples: M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) K tuples: E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 Defined Pair Symbols: <'_2, M2_4, L8_6, L5_6, E2_4, L2_6, L11_6, M1_4, L4_6, L1_6, MONUS_2, L7_6, L3_6, L14_6, L12_6, L10_6, GCD_2, EQUAL0_2, L15_6, L13_6, M4_4, E3_4, E1_4 Compound Symbols: c_1, c6_1, c11_1, c13_1, c20_1, c26_1, c28_1, c29_1, c32_1, c35_1, c36_1, c40_1, c42_2, c43_1, c45_2, c46_2, c47_2, c48_1, c49_1, c21_1, c22_1, c23_1, c24_1, c25_1, c51_1, c1_1 ---------------------------------------- (21) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) Now S is empty ---------------------------------------- (22) BOUNDS(1, 1) ---------------------------------------- (23) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (24) 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 ---------------------------------------- (25) 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 [ ]. ---------------------------------------- (26) Complex Obligation (BEST) ---------------------------------------- (27) 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 ---------------------------------------- (28) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (29) BOUNDS(n^1, INF) ---------------------------------------- (30) 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