WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/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), 151 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), 2 ms] (10) CdtProblem (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 176 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 92 ms] (16) CdtProblem (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CdtProblem (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 63 ms] (20) CdtProblem (21) CdtKnowledgeProof [FINISHED, 0 ms] (22) BOUNDS(1, 1) (23) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (24) CpxRelTRS (25) SlicingProof [LOWER BOUND(ID), 74 ms] (26) CpxRelTRS (27) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (28) typed CpxTrs (29) OrderProof [LOWER BOUND(ID), 0 ms] (30) typed CpxTrs (31) RewriteLemmaProof [LOWER BOUND(ID), 284 ms] (32) typed CpxTrs (33) RewriteLemmaProof [LOWER BOUND(ID), 171 ms] (34) BEST (35) proven lower bound (36) LowerBoundPropagationProof [FINISHED, 0 ms] (37) BOUNDS(n^1, INF) (38) typed CpxTrs (39) RewriteLemmaProof [LOWER BOUND(ID), 150 ms] (40) typed CpxTrs (41) RewriteLemmaProof [LOWER BOUND(ID), 142 ms] (42) typed CpxTrs (43) RewriteLemmaProof [LOWER BOUND(ID), 138 ms] (44) typed CpxTrs (45) RewriteLemmaProof [LOWER BOUND(ID), 93 ms] (46) typed CpxTrs ---------------------------------------- (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: BOOL2NAT(False) -> c30 M2(S(0), z0, z1, True) -> c3 L9(z0, z1, z2, z3, z4, z5) -> c33 HELP1(0) -> c16 BOOL2NAT(True) -> c31 E6(z0, z1, z2, z3) -> c38 <'(0, S(z0)) -> c1 <'(z0, 0) -> c2 M3(S(S(z0)), z1, z2, z3) -> c8 M2(S(S(z0)), z1, z2, True) -> c4 L16(z0, z1, z2, z3, z4, z5) -> c44 M3(0, z0, z1, z2) -> c9 E5(z0, z1, z2, z3) -> c39 L5(z0, z1, z2, z3, z4, True) -> c12 E4(z0, z1, z2, False) -> c17 HELP1(S(0)) -> c14 M2(0, z0, z1, True) -> c5 E8(z0, z1, z2, z3) -> c50 E7(z0, z1, z2, z3) -> c37 L6(z0, z1, z2, z3, z4, z5) -> c34 L2(z0, z1, z2, z3, z4, True) -> c27 M5(z0, z1, z2, z3) -> c41 L8(z0, z1, z2, True, z3, z4) -> c10 E4(z0, z1, z2, True) -> c18 HELP1(S(S(z0))) -> c15 M3(S(0), z0, z1, z2) -> c7 E2(z0, z1, z2, False) -> c19 ---------------------------------------- (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) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (24) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: 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) SlicingProof (LOWER BOUND(ID)) Sliced the following arguments: m2/2 m3/1 m3/2 m3/3 l8/2 l8/4 l8/5 l5/2 l5/3 l5/4 e4/0 e4/1 e4/2 e2/2 l15/0 l15/2 l15/3 l15/5 l16/0 l16/1 l16/3 l16/4 l16/5 l13/0 l13/2 l13/3 l13/5 m4/2 m4/3 m5/0 m5/1 m5/3 l10/2 l10/3 l10/4 l10/5 l7/2 l7/3 l7/4 l7/5 l2/3 l2/4 l3/2 l3/3 l3/4 l3/5 l11/2 l11/3 l11/4 l14/2 l14/3 l14/4 l14/5 l12/2 l12/3 l12/4 l12/5 e3/2 e3/3 m1/2 m1/3 l9/1 l9/2 l9/3 l9/4 l9/5 l6/0 l6/1 l6/2 l6/3 l6/4 l6/5 l4/2 l4/3 l4/4 l4/5 l1/3 l1/4 l1/5 e7/0 e7/1 e7/2 e7/3 e6/0 e6/1 e6/2 e6/3 e5/0 e5/1 e5/2 e5/3 e1/2 e1/3 e8/0 e8/1 e8/3 ---------------------------------------- (26) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(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 ---------------------------------------- (27) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (28) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S ---------------------------------------- (29) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: l15, gcd, l13, m4, monus, l10, l7, l3, l14, l12, m1, l4, < They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 < < l10 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (30) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: <, l15, gcd, l13, m4, monus, l10, l7, l3, l14, l12, m1, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 < < l10 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (31) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) Induction Base: <(gen_0':S5_17(0), gen_0':S5_17(+(1, 0))) ->_R^Omega(0) True Induction Step: <(gen_0':S5_17(+(n7_17, 1)), gen_0':S5_17(+(1, +(n7_17, 1)))) ->_R^Omega(0) <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) ->_IH True We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (32) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: monus, l15, gcd, l13, m4, l10, l7, l3, l14, l12, m1, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (33) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: monus(gen_0':S5_17(n619_17), gen_0':S5_17(n619_17)) -> *6_17, rt in Omega(n619_17) Induction Base: monus(gen_0':S5_17(0), gen_0':S5_17(0)) Induction Step: monus(gen_0':S5_17(+(n619_17, 1)), gen_0':S5_17(+(n619_17, 1))) ->_R^Omega(1) m1(gen_0':S5_17(+(n619_17, 1)), gen_0':S5_17(+(n619_17, 1))) ->_R^Omega(1) m2(gen_0':S5_17(+(1, n619_17)), gen_0':S5_17(+(1, n619_17)), False) ->_R^Omega(1) m4(gen_0':S5_17(+(1, n619_17)), gen_0':S5_17(+(1, n619_17))) ->_R^Omega(1) m5(monus(gen_0':S5_17(n619_17), gen_0':S5_17(n619_17))) ->_IH m5(*6_17) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (34) Complex Obligation (BEST) ---------------------------------------- (35) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: monus, l15, gcd, l13, m4, l10, l7, l3, l14, l12, m1, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (36) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (37) BOUNDS(n^1, INF) ---------------------------------------- (38) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) monus(gen_0':S5_17(n619_17), gen_0':S5_17(n619_17)) -> *6_17, rt in Omega(n619_17) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: m1, l15, gcd, l13, m4, l10, l7, l3, l14, l12, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (39) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: m1(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17)) -> *6_17, rt in Omega(n2619_17) Induction Base: m1(gen_0':S5_17(0), gen_0':S5_17(0)) Induction Step: m1(gen_0':S5_17(+(n2619_17, 1)), gen_0':S5_17(+(n2619_17, 1))) ->_R^Omega(1) m2(gen_0':S5_17(+(n2619_17, 1)), gen_0':S5_17(+(n2619_17, 1)), False) ->_R^Omega(1) m4(gen_0':S5_17(+(1, n2619_17)), gen_0':S5_17(+(1, n2619_17))) ->_R^Omega(1) m5(monus(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17))) ->_R^Omega(1) m5(m1(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17))) ->_IH m5(*6_17) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (40) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) monus(gen_0':S5_17(n619_17), gen_0':S5_17(n619_17)) -> *6_17, rt in Omega(n619_17) m1(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17)) -> *6_17, rt in Omega(n2619_17) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: m4, l15, gcd, l13, monus, l10, l7, l3, l14, l12, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (41) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: m4(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17))) -> *6_17, rt in Omega(n4685_17) Induction Base: m4(gen_0':S5_17(+(1, 0)), gen_0':S5_17(+(1, 0))) Induction Step: m4(gen_0':S5_17(+(1, +(n4685_17, 1))), gen_0':S5_17(+(1, +(n4685_17, 1)))) ->_R^Omega(1) m5(monus(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17)))) ->_R^Omega(1) m5(m1(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17)))) ->_R^Omega(1) m5(m2(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17)), False)) ->_R^Omega(1) m5(m4(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17)))) ->_IH m5(*6_17) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (42) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) monus(gen_0':S5_17(n619_17), gen_0':S5_17(n619_17)) -> *6_17, rt in Omega(n619_17) m1(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17)) -> *6_17, rt in Omega(n2619_17) m4(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17))) -> *6_17, rt in Omega(n4685_17) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: monus, l15, gcd, l13, l10, l7, l3, l14, l12, m1, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (43) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: monus(gen_0':S5_17(n7477_17), gen_0':S5_17(n7477_17)) -> *6_17, rt in Omega(n7477_17) Induction Base: monus(gen_0':S5_17(0), gen_0':S5_17(0)) Induction Step: monus(gen_0':S5_17(+(n7477_17, 1)), gen_0':S5_17(+(n7477_17, 1))) ->_R^Omega(1) m1(gen_0':S5_17(+(n7477_17, 1)), gen_0':S5_17(+(n7477_17, 1))) ->_R^Omega(1) m2(gen_0':S5_17(+(1, n7477_17)), gen_0':S5_17(+(1, n7477_17)), False) ->_R^Omega(1) m4(gen_0':S5_17(+(1, n7477_17)), gen_0':S5_17(+(1, n7477_17))) ->_R^Omega(1) m5(monus(gen_0':S5_17(n7477_17), gen_0':S5_17(n7477_17))) ->_IH m5(*6_17) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (44) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) monus(gen_0':S5_17(n7477_17), gen_0':S5_17(n7477_17)) -> *6_17, rt in Omega(n7477_17) m1(gen_0':S5_17(n2619_17), gen_0':S5_17(n2619_17)) -> *6_17, rt in Omega(n2619_17) m4(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17))) -> *6_17, rt in Omega(n4685_17) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: m1, l15, gcd, l13, l10, l7, l3, l14, l12, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 m4 = monus m4 = m1 monus < l14 monus < l12 monus = m1 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4 ---------------------------------------- (45) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: m1(gen_0':S5_17(n10155_17), gen_0':S5_17(n10155_17)) -> *6_17, rt in Omega(n10155_17) Induction Base: m1(gen_0':S5_17(0), gen_0':S5_17(0)) Induction Step: m1(gen_0':S5_17(+(n10155_17, 1)), gen_0':S5_17(+(n10155_17, 1))) ->_R^Omega(1) m2(gen_0':S5_17(+(n10155_17, 1)), gen_0':S5_17(+(n10155_17, 1)), False) ->_R^Omega(1) m4(gen_0':S5_17(+(1, n10155_17)), gen_0':S5_17(+(1, n10155_17))) ->_R^Omega(1) m5(monus(gen_0':S5_17(n10155_17), gen_0':S5_17(n10155_17))) ->_R^Omega(1) m5(m1(gen_0':S5_17(n10155_17), gen_0':S5_17(n10155_17))) ->_IH m5(*6_17) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (46) Obligation: Innermost TRS: Rules: m2(S(0'), b, True) -> False m2(S(S(x)), b, True) -> True m2(0', b, True) -> False m3(S(0')) -> False m3(S(S(x))) -> True m3(0') -> False l8(res, y, True) -> res l5(x, y, True) -> 0' help1(S(0')) -> False help1(S(S(x))) -> True e4(False) -> False e4(True) -> True e2(a, b, False) -> False l15(y, False) -> l16(gcd(y, 0')) l15(y, True) -> l16(gcd(y, S(0'))) l13(y, False) -> l16(gcd(0', y)) l13(y, True) -> l16(gcd(S(0'), y)) m4(S(x'), S(x)) -> m5(monus(x', x)) m2(a, b, False) -> m4(a, b) l8(x, y, False) -> l10(x, y) l5(x, y, False) -> l7(x, y) l2(x, y, res, False) -> l3(x, y) l2(x, y, res, True) -> res l11(x, y, False) -> l14(x, y) l11(x, y, True) -> l12(x, y) help1(0') -> False e2(a, b, True) -> e3(a, b) bool2Nat(False) -> 0' bool2Nat(True) -> S(0') m1(a, x) -> m2(a, x, False) l9(res) -> res l6 -> 0' l4(x', x) -> l5(x', x, False) l1(x, y, res) -> l2(x, y, res, False) e7 -> False e6 -> False e5 -> True monus(a, b) -> m1(a, b) m5(res) -> res l7(x, y) -> l8(x, y, equal0(x, y)) l3(x, y) -> l4(x, y) l16(res) -> res l14(x, y) -> l15(y, monus(x, y)) l12(x, y) -> l13(y, monus(x, y)) l10(x, y) -> l11(x, y, <(x, y)) gcd(x, y) -> l1(x, y, 0') equal0(a, b) -> e1(a, b) e8(res) -> res e3(a, b) -> e4(<(b, a)) e1(a, b) -> e2(a, b, <(a, b)) <(S(x), S(y)) -> <(x, y) <(0', S(y)) -> True <(x, 0') -> False Types: m2 :: 0':S -> 0':S -> True:False -> True:False S :: 0':S -> 0':S 0' :: 0':S True :: True:False False :: True:False m3 :: 0':S -> True:False l8 :: 0':S -> 0':S -> True:False -> 0':S l5 :: 0':S -> 0':S -> True:False -> 0':S help1 :: 0':S -> True:False e4 :: True:False -> True:False e2 :: 0':S -> 0':S -> True:False -> True:False l15 :: 0':S -> True:False -> 0':S l16 :: 0':S -> 0':S gcd :: 0':S -> 0':S -> 0':S l13 :: 0':S -> True:False -> 0':S m4 :: 0':S -> 0':S -> True:False m5 :: True:False -> True:False monus :: 0':S -> 0':S -> True:False l10 :: 0':S -> 0':S -> 0':S l7 :: 0':S -> 0':S -> 0':S l2 :: 0':S -> 0':S -> 0':S -> True:False -> 0':S l3 :: 0':S -> 0':S -> 0':S l11 :: 0':S -> 0':S -> True:False -> 0':S l14 :: 0':S -> 0':S -> 0':S l12 :: 0':S -> 0':S -> 0':S e3 :: 0':S -> 0':S -> True:False bool2Nat :: True:False -> 0':S m1 :: 0':S -> 0':S -> True:False l9 :: l9 -> l9 l6 :: 0':S l4 :: 0':S -> 0':S -> 0':S l1 :: 0':S -> 0':S -> 0':S -> 0':S e7 :: True:False e6 :: True:False e5 :: True:False equal0 :: 0':S -> 0':S -> True:False < :: 0':S -> 0':S -> True:False e1 :: 0':S -> 0':S -> True:False e8 :: e8 -> e8 hole_True:False1_17 :: True:False hole_0':S2_17 :: 0':S hole_l93_17 :: l9 hole_e84_17 :: e8 gen_0':S5_17 :: Nat -> 0':S Lemmas: <(gen_0':S5_17(n7_17), gen_0':S5_17(+(1, n7_17))) -> True, rt in Omega(0) monus(gen_0':S5_17(n7477_17), gen_0':S5_17(n7477_17)) -> *6_17, rt in Omega(n7477_17) m1(gen_0':S5_17(n10155_17), gen_0':S5_17(n10155_17)) -> *6_17, rt in Omega(n10155_17) m4(gen_0':S5_17(+(1, n4685_17)), gen_0':S5_17(+(1, n4685_17))) -> *6_17, rt in Omega(n4685_17) Generator Equations: gen_0':S5_17(0) <=> 0' gen_0':S5_17(+(x, 1)) <=> S(gen_0':S5_17(x)) The following defined symbols remain to be analysed: gcd, l15, l13, l10, l7, l3, l14, l12, l4 They will be analysed ascendingly in the following order: l15 = gcd l15 = l13 l15 = l10 l15 = l7 l15 = l3 l15 = l14 l15 = l12 l15 = l4 gcd = l13 gcd = l10 gcd = l7 gcd = l3 gcd = l14 gcd = l12 gcd = l4 l13 = l10 l13 = l7 l13 = l3 l13 = l14 l13 = l12 l13 = l4 l10 = l7 l10 = l3 l10 = l14 l10 = l12 l10 = l4 l7 = l3 l7 = l14 l7 = l12 l7 = l4 l3 = l14 l3 = l12 l3 = l4 l14 = l12 l14 = l4 l12 = l4