24.94/7.24 WORST_CASE(Omega(n^1), O(n^1)) 24.94/7.25 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 24.94/7.25 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 24.94/7.25 24.94/7.25 24.94/7.25 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 24.94/7.25 24.94/7.25 (0) CpxRelTRS 24.94/7.25 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 148 ms] 24.94/7.25 (2) CpxRelTRS 24.94/7.25 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 24.94/7.25 (4) CdtProblem 24.94/7.25 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 24.94/7.25 (6) CdtProblem 24.94/7.25 (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 24.94/7.25 (8) CdtProblem 24.94/7.25 (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] 24.94/7.25 (10) CdtProblem 24.94/7.25 (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 24.94/7.25 (12) CdtProblem 24.94/7.25 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 179 ms] 24.94/7.25 (14) CdtProblem 24.94/7.25 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 91 ms] 24.94/7.25 (16) CdtProblem 24.94/7.25 (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 24.94/7.25 (18) CdtProblem 24.94/7.25 (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 78 ms] 24.94/7.25 (20) CdtProblem 24.94/7.25 (21) CdtKnowledgeProof [FINISHED, 0 ms] 24.94/7.25 (22) BOUNDS(1, 1) 24.94/7.25 (23) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 24.94/7.25 (24) TRS for Loop Detection 24.94/7.25 (25) DecreasingLoopProof [LOWER BOUND(ID), 408 ms] 24.94/7.25 (26) BEST 24.94/7.25 (27) proven lower bound 24.94/7.25 (28) LowerBoundPropagationProof [FINISHED, 0 ms] 24.94/7.25 (29) BOUNDS(n^1, INF) 24.94/7.25 (30) TRS for Loop Detection 24.94/7.25 24.94/7.25 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (0) 24.94/7.25 Obligation: 24.94/7.25 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 24.94/7.25 24.94/7.25 24.94/7.25 The TRS R consists of the following rules: 24.94/7.25 24.94/7.25 m2(S(0), b, res, True) -> False 24.94/7.25 m2(S(S(x)), b, res, True) -> True 24.94/7.25 m2(0, b, res, True) -> False 24.94/7.25 m3(S(0), b, res, t) -> False 24.94/7.25 m3(S(S(x)), b, res, t) -> True 24.94/7.25 m3(0, b, res, t) -> False 24.94/7.25 l8(res, y, res', True, mtmp, t) -> res 24.94/7.25 l5(x, y, res, tmp, mtmp, True) -> 0 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(x))) -> True 24.94/7.25 e4(a, b, res, False) -> False 24.94/7.25 e4(a, b, res, True) -> True 24.94/7.25 e2(a, b, res, False) -> False 24.94/7.25 l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) 24.94/7.25 l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) 24.94/7.25 l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) 24.94/7.25 l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) 24.94/7.25 m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) 24.94/7.25 m2(a, b, res, False) -> m4(a, b, res, False) 24.94/7.25 l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) 24.94/7.25 l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) 24.94/7.25 l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) 24.94/7.25 l2(x, y, res, tmp, mtmp, True) -> res 24.94/7.25 l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) 24.94/7.25 l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) 24.94/7.25 help1(0) -> False 24.94/7.25 e2(a, b, res, True) -> e3(a, b, res, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(a, x, res, t) -> m2(a, x, res, False) 24.94/7.25 l9(res, y, res', tmp, mtmp, t) -> res 24.94/7.25 l6(x, y, res, tmp, mtmp, t) -> 0 24.94/7.25 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) 24.94/7.25 l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) 24.94/7.25 e7(a, b, res, t) -> False 24.94/7.25 e6(a, b, res, t) -> False 24.94/7.25 e5(a, b, res, t) -> True 24.94/7.25 monus(a, b) -> m1(a, b, False, False) 24.94/7.25 m5(a, b, res, t) -> res 24.94/7.25 l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) 24.94/7.25 l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) 24.94/7.25 l16(x, y, res, tmp, mtmp, t) -> res 24.94/7.25 l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) 24.94/7.25 l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) 24.94/7.25 l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) 24.94/7.25 gcd(x, y) -> l1(x, y, 0, False, False, False) 24.94/7.25 equal0(a, b) -> e1(a, b, False, False) 24.94/7.25 e8(a, b, res, t) -> res 24.94/7.25 e3(a, b, res, t) -> e4(a, b, res, <(b, a)) 24.94/7.25 e1(a, b, res, t) -> e2(a, b, res, <(a, b)) 24.94/7.25 24.94/7.25 The (relative) TRS S consists of the following rules: 24.94/7.25 24.94/7.25 <(S(x), S(y)) -> <(x, y) 24.94/7.25 <(0, S(y)) -> True 24.94/7.25 <(x, 0) -> False 24.94/7.25 24.94/7.25 Rewrite Strategy: INNERMOST 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 24.94/7.25 proved termination of relative rules 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (2) 24.94/7.25 Obligation: 24.94/7.25 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 24.94/7.25 24.94/7.25 24.94/7.25 The TRS R consists of the following rules: 24.94/7.25 24.94/7.25 m2(S(0), b, res, True) -> False 24.94/7.25 m2(S(S(x)), b, res, True) -> True 24.94/7.25 m2(0, b, res, True) -> False 24.94/7.25 m3(S(0), b, res, t) -> False 24.94/7.25 m3(S(S(x)), b, res, t) -> True 24.94/7.25 m3(0, b, res, t) -> False 24.94/7.25 l8(res, y, res', True, mtmp, t) -> res 24.94/7.25 l5(x, y, res, tmp, mtmp, True) -> 0 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(x))) -> True 24.94/7.25 e4(a, b, res, False) -> False 24.94/7.25 e4(a, b, res, True) -> True 24.94/7.25 e2(a, b, res, False) -> False 24.94/7.25 l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) 24.94/7.25 l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) 24.94/7.25 l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) 24.94/7.25 l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) 24.94/7.25 m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) 24.94/7.25 m2(a, b, res, False) -> m4(a, b, res, False) 24.94/7.25 l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) 24.94/7.25 l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) 24.94/7.25 l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) 24.94/7.25 l2(x, y, res, tmp, mtmp, True) -> res 24.94/7.25 l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) 24.94/7.25 l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) 24.94/7.25 help1(0) -> False 24.94/7.25 e2(a, b, res, True) -> e3(a, b, res, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(a, x, res, t) -> m2(a, x, res, False) 24.94/7.25 l9(res, y, res', tmp, mtmp, t) -> res 24.94/7.25 l6(x, y, res, tmp, mtmp, t) -> 0 24.94/7.25 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) 24.94/7.25 l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) 24.94/7.25 e7(a, b, res, t) -> False 24.94/7.25 e6(a, b, res, t) -> False 24.94/7.25 e5(a, b, res, t) -> True 24.94/7.25 monus(a, b) -> m1(a, b, False, False) 24.94/7.25 m5(a, b, res, t) -> res 24.94/7.25 l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) 24.94/7.25 l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) 24.94/7.25 l16(x, y, res, tmp, mtmp, t) -> res 24.94/7.25 l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) 24.94/7.25 l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) 24.94/7.25 l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) 24.94/7.25 gcd(x, y) -> l1(x, y, 0, False, False, False) 24.94/7.25 equal0(a, b) -> e1(a, b, False, False) 24.94/7.25 e8(a, b, res, t) -> res 24.94/7.25 e3(a, b, res, t) -> e4(a, b, res, <(b, a)) 24.94/7.25 e1(a, b, res, t) -> e2(a, b, res, <(a, b)) 24.94/7.25 24.94/7.25 The (relative) TRS S consists of the following rules: 24.94/7.25 24.94/7.25 <(S(x), S(y)) -> <(x, y) 24.94/7.25 <(0, S(y)) -> True 24.94/7.25 <(x, 0) -> False 24.94/7.25 24.94/7.25 Rewrite Strategy: INNERMOST 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 24.94/7.25 Converted Cpx (relative) TRS to CDT 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (4) 24.94/7.25 Obligation: 24.94/7.25 Complexity Dependency Tuples Problem 24.94/7.25 24.94/7.25 Rules: 24.94/7.25 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.25 <(0, S(z0)) -> True 24.94/7.25 <(z0, 0) -> False 24.94/7.25 m2(S(0), z0, z1, True) -> False 24.94/7.25 m2(S(S(z0)), z1, z2, True) -> True 24.94/7.25 m2(0, z0, z1, True) -> False 24.94/7.25 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.25 m3(S(0), z0, z1, z2) -> False 24.94/7.25 m3(S(S(z0)), z1, z2, z3) -> True 24.94/7.25 m3(0, z0, z1, z2) -> False 24.94/7.25 l8(z0, z1, z2, True, z3, z4) -> z0 24.94/7.25 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) 24.94/7.25 l5(z0, z1, z2, z3, z4, True) -> 0 24.94/7.25 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(z0))) -> True 24.94/7.25 help1(0) -> False 24.94/7.25 e4(z0, z1, z2, False) -> False 24.94/7.25 e4(z0, z1, z2, True) -> True 24.94/7.25 e2(z0, z1, z2, False) -> False 24.94/7.25 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.25 l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) 24.94/7.25 l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) 24.94/7.25 l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) 24.94/7.25 l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) 24.94/7.25 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.25 l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) 24.94/7.25 l2(z0, z1, z2, z3, z4, True) -> z2 24.94/7.25 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) 24.94/7.25 l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.25 l9(z0, z1, z2, z3, z4, z5) -> z0 24.94/7.25 l6(z0, z1, z2, z3, z4, z5) -> 0 24.94/7.25 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) 24.94/7.25 l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) 24.94/7.25 e7(z0, z1, z2, z3) -> False 24.94/7.25 e6(z0, z1, z2, z3) -> False 24.94/7.25 e5(z0, z1, z2, z3) -> True 24.94/7.25 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.25 m5(z0, z1, z2, z3) -> z2 24.94/7.25 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) 24.94/7.25 l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) 24.94/7.25 l16(z0, z1, z2, z3, z4, z5) -> z2 24.94/7.25 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) 24.94/7.25 gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) 24.94/7.25 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.25 e8(z0, z1, z2, z3) -> z2 24.94/7.25 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.25 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.25 Tuples: 24.94/7.25 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.25 <'(0, S(z0)) -> c1 24.94/7.25 <'(z0, 0) -> c2 24.94/7.25 M2(S(0), z0, z1, True) -> c3 24.94/7.25 M2(S(S(z0)), z1, z2, True) -> c4 24.94/7.25 M2(0, z0, z1, True) -> c5 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 M3(S(0), z0, z1, z2) -> c7 24.94/7.25 M3(S(S(z0)), z1, z2, z3) -> c8 24.94/7.25 M3(0, z0, z1, z2) -> c9 24.94/7.25 L8(z0, z1, z2, True, z3, z4) -> c10 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, True) -> c12 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 HELP1(S(0)) -> c14 24.94/7.25 HELP1(S(S(z0))) -> c15 24.94/7.25 HELP1(0) -> c16 24.94/7.25 E4(z0, z1, z2, False) -> c17 24.94/7.25 E4(z0, z1, z2, True) -> c18 24.94/7.25 E2(z0, z1, z2, False) -> c19 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L2(z0, z1, z2, z3, z4, True) -> c27 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 BOOL2NAT(False) -> c30 24.94/7.25 BOOL2NAT(True) -> c31 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L9(z0, z1, z2, z3, z4, z5) -> c33 24.94/7.25 L6(z0, z1, z2, z3, z4, z5) -> c34 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 E7(z0, z1, z2, z3) -> c37 24.94/7.25 E6(z0, z1, z2, z3) -> c38 24.94/7.25 E5(z0, z1, z2, z3) -> c39 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 M5(z0, z1, z2, z3) -> c41 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L16(z0, z1, z2, z3, z4, z5) -> c44 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E8(z0, z1, z2, z3) -> c50 24.94/7.25 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 S tuples: 24.94/7.25 M2(S(0), z0, z1, True) -> c3 24.94/7.25 M2(S(S(z0)), z1, z2, True) -> c4 24.94/7.25 M2(0, z0, z1, True) -> c5 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 M3(S(0), z0, z1, z2) -> c7 24.94/7.25 M3(S(S(z0)), z1, z2, z3) -> c8 24.94/7.25 M3(0, z0, z1, z2) -> c9 24.94/7.25 L8(z0, z1, z2, True, z3, z4) -> c10 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, True) -> c12 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 HELP1(S(0)) -> c14 24.94/7.25 HELP1(S(S(z0))) -> c15 24.94/7.25 HELP1(0) -> c16 24.94/7.25 E4(z0, z1, z2, False) -> c17 24.94/7.25 E4(z0, z1, z2, True) -> c18 24.94/7.25 E2(z0, z1, z2, False) -> c19 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L2(z0, z1, z2, z3, z4, True) -> c27 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 BOOL2NAT(False) -> c30 24.94/7.25 BOOL2NAT(True) -> c31 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L9(z0, z1, z2, z3, z4, z5) -> c33 24.94/7.25 L6(z0, z1, z2, z3, z4, z5) -> c34 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 E7(z0, z1, z2, z3) -> c37 24.94/7.25 E6(z0, z1, z2, z3) -> c38 24.94/7.25 E5(z0, z1, z2, z3) -> c39 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 M5(z0, z1, z2, z3) -> c41 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L16(z0, z1, z2, z3, z4, z5) -> c44 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E8(z0, z1, z2, z3) -> c50 24.94/7.25 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 K tuples:none 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 24.94/7.25 Removed 27 trailing nodes: 24.94/7.25 <'(0, S(z0)) -> c1 24.94/7.25 L6(z0, z1, z2, z3, z4, z5) -> c34 24.94/7.25 E4(z0, z1, z2, True) -> c18 24.94/7.25 E6(z0, z1, z2, z3) -> c38 24.94/7.25 M3(0, z0, z1, z2) -> c9 24.94/7.25 HELP1(S(S(z0))) -> c15 24.94/7.25 M2(S(S(z0)), z1, z2, True) -> c4 24.94/7.25 E4(z0, z1, z2, False) -> c17 24.94/7.25 L16(z0, z1, z2, z3, z4, z5) -> c44 24.94/7.25 L8(z0, z1, z2, True, z3, z4) -> c10 24.94/7.25 HELP1(S(0)) -> c14 24.94/7.25 HELP1(0) -> c16 24.94/7.25 <'(z0, 0) -> c2 24.94/7.25 E8(z0, z1, z2, z3) -> c50 24.94/7.25 M2(S(0), z0, z1, True) -> c3 24.94/7.25 L5(z0, z1, z2, z3, z4, True) -> c12 24.94/7.25 E2(z0, z1, z2, False) -> c19 24.94/7.25 M2(0, z0, z1, True) -> c5 24.94/7.25 L9(z0, z1, z2, z3, z4, z5) -> c33 24.94/7.25 BOOL2NAT(False) -> c30 24.94/7.25 M5(z0, z1, z2, z3) -> c41 24.94/7.25 M3(S(S(z0)), z1, z2, z3) -> c8 24.94/7.25 E5(z0, z1, z2, z3) -> c39 24.94/7.25 E7(z0, z1, z2, z3) -> c37 24.94/7.25 BOOL2NAT(True) -> c31 24.94/7.25 M3(S(0), z0, z1, z2) -> c7 24.94/7.25 L2(z0, z1, z2, z3, z4, True) -> c27 24.94/7.25 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (6) 24.94/7.25 Obligation: 24.94/7.25 Complexity Dependency Tuples Problem 24.94/7.25 24.94/7.25 Rules: 24.94/7.25 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.25 <(0, S(z0)) -> True 24.94/7.25 <(z0, 0) -> False 24.94/7.25 m2(S(0), z0, z1, True) -> False 24.94/7.25 m2(S(S(z0)), z1, z2, True) -> True 24.94/7.25 m2(0, z0, z1, True) -> False 24.94/7.25 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.25 m3(S(0), z0, z1, z2) -> False 24.94/7.25 m3(S(S(z0)), z1, z2, z3) -> True 24.94/7.25 m3(0, z0, z1, z2) -> False 24.94/7.25 l8(z0, z1, z2, True, z3, z4) -> z0 24.94/7.25 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) 24.94/7.25 l5(z0, z1, z2, z3, z4, True) -> 0 24.94/7.25 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(z0))) -> True 24.94/7.25 help1(0) -> False 24.94/7.25 e4(z0, z1, z2, False) -> False 24.94/7.25 e4(z0, z1, z2, True) -> True 24.94/7.25 e2(z0, z1, z2, False) -> False 24.94/7.25 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.25 l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) 24.94/7.25 l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) 24.94/7.25 l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) 24.94/7.25 l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) 24.94/7.25 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.25 l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) 24.94/7.25 l2(z0, z1, z2, z3, z4, True) -> z2 24.94/7.25 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) 24.94/7.25 l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.25 l9(z0, z1, z2, z3, z4, z5) -> z0 24.94/7.25 l6(z0, z1, z2, z3, z4, z5) -> 0 24.94/7.25 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) 24.94/7.25 l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) 24.94/7.25 e7(z0, z1, z2, z3) -> False 24.94/7.25 e6(z0, z1, z2, z3) -> False 24.94/7.25 e5(z0, z1, z2, z3) -> True 24.94/7.25 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.25 m5(z0, z1, z2, z3) -> z2 24.94/7.25 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) 24.94/7.25 l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) 24.94/7.25 l16(z0, z1, z2, z3, z4, z5) -> z2 24.94/7.25 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) 24.94/7.25 gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) 24.94/7.25 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.25 e8(z0, z1, z2, z3) -> z2 24.94/7.25 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.25 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.25 Tuples: 24.94/7.25 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 S tuples: 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(L16(z0, z1, gcd(z1, 0), z3, False, z4), GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(L16(z0, z1, gcd(z1, S(0)), z3, True, z4), GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(L16(z0, z1, gcd(0, z1), z3, False, z4), GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(L16(z0, z1, gcd(S(0), z1), z3, True, z4), GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(M5(S(z0), S(z1), monus(z0, z1), z3), MONUS(z0, z1)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E3(z0, z1, z2, z3) -> c51(E4(z0, z1, z2, <(z1, z0)), <'(z1, z0)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 K tuples:none 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 24.94/7.25 Removed 6 trailing tuple parts 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (8) 24.94/7.25 Obligation: 24.94/7.25 Complexity Dependency Tuples Problem 24.94/7.25 24.94/7.25 Rules: 24.94/7.25 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.25 <(0, S(z0)) -> True 24.94/7.25 <(z0, 0) -> False 24.94/7.25 m2(S(0), z0, z1, True) -> False 24.94/7.25 m2(S(S(z0)), z1, z2, True) -> True 24.94/7.25 m2(0, z0, z1, True) -> False 24.94/7.25 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.25 m3(S(0), z0, z1, z2) -> False 24.94/7.25 m3(S(S(z0)), z1, z2, z3) -> True 24.94/7.25 m3(0, z0, z1, z2) -> False 24.94/7.25 l8(z0, z1, z2, True, z3, z4) -> z0 24.94/7.25 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) 24.94/7.25 l5(z0, z1, z2, z3, z4, True) -> 0 24.94/7.25 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(z0))) -> True 24.94/7.25 help1(0) -> False 24.94/7.25 e4(z0, z1, z2, False) -> False 24.94/7.25 e4(z0, z1, z2, True) -> True 24.94/7.25 e2(z0, z1, z2, False) -> False 24.94/7.25 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.25 l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) 24.94/7.25 l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) 24.94/7.25 l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) 24.94/7.25 l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) 24.94/7.25 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.25 l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) 24.94/7.25 l2(z0, z1, z2, z3, z4, True) -> z2 24.94/7.25 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) 24.94/7.25 l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.25 l9(z0, z1, z2, z3, z4, z5) -> z0 24.94/7.25 l6(z0, z1, z2, z3, z4, z5) -> 0 24.94/7.25 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) 24.94/7.25 l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) 24.94/7.25 e7(z0, z1, z2, z3) -> False 24.94/7.25 e6(z0, z1, z2, z3) -> False 24.94/7.25 e5(z0, z1, z2, z3) -> True 24.94/7.25 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.25 m5(z0, z1, z2, z3) -> z2 24.94/7.25 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) 24.94/7.25 l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) 24.94/7.25 l16(z0, z1, z2, z3, z4, z5) -> z2 24.94/7.25 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) 24.94/7.25 gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) 24.94/7.25 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.25 e8(z0, z1, z2, z3) -> z2 24.94/7.25 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.25 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.25 Tuples: 24.94/7.25 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.25 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.25 S tuples: 24.94/7.25 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.25 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.25 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.25 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.25 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.25 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.25 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.25 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.25 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.25 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.25 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.25 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.25 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.25 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.25 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.25 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.25 E1(z0, z1, z2, z3) -> c52(E2(z0, z1, z2, <(z0, z1)), <'(z0, z1)) 24.94/7.25 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.25 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.25 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.25 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.25 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.25 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.25 K tuples:none 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 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 24.94/7.25 24.94/7.25 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) 24.94/7.25 Split RHS of tuples not part of any SCC 24.94/7.25 ---------------------------------------- 24.94/7.25 24.94/7.25 (10) 24.94/7.25 Obligation: 24.94/7.25 Complexity Dependency Tuples Problem 24.94/7.25 24.94/7.25 Rules: 24.94/7.25 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.25 <(0, S(z0)) -> True 24.94/7.25 <(z0, 0) -> False 24.94/7.25 m2(S(0), z0, z1, True) -> False 24.94/7.25 m2(S(S(z0)), z1, z2, True) -> True 24.94/7.25 m2(0, z0, z1, True) -> False 24.94/7.25 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.25 m3(S(0), z0, z1, z2) -> False 24.94/7.25 m3(S(S(z0)), z1, z2, z3) -> True 24.94/7.25 m3(0, z0, z1, z2) -> False 24.94/7.25 l8(z0, z1, z2, True, z3, z4) -> z0 24.94/7.25 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) 24.94/7.25 l5(z0, z1, z2, z3, z4, True) -> 0 24.94/7.25 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) 24.94/7.25 help1(S(0)) -> False 24.94/7.25 help1(S(S(z0))) -> True 24.94/7.25 help1(0) -> False 24.94/7.25 e4(z0, z1, z2, False) -> False 24.94/7.25 e4(z0, z1, z2, True) -> True 24.94/7.25 e2(z0, z1, z2, False) -> False 24.94/7.25 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.25 l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) 24.94/7.25 l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) 24.94/7.25 l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) 24.94/7.25 l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) 24.94/7.25 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.25 l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) 24.94/7.25 l2(z0, z1, z2, z3, z4, True) -> z2 24.94/7.25 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) 24.94/7.25 l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) 24.94/7.25 bool2Nat(False) -> 0 24.94/7.25 bool2Nat(True) -> S(0) 24.94/7.25 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.25 l9(z0, z1, z2, z3, z4, z5) -> z0 24.94/7.25 l6(z0, z1, z2, z3, z4, z5) -> 0 24.94/7.25 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) 24.94/7.25 l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) 24.94/7.25 e7(z0, z1, z2, z3) -> False 24.94/7.25 e6(z0, z1, z2, z3) -> False 24.94/7.25 e5(z0, z1, z2, z3) -> True 24.94/7.25 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.25 m5(z0, z1, z2, z3) -> z2 24.94/7.25 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) 24.94/7.25 l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) 24.94/7.25 l16(z0, z1, z2, z3, z4, z5) -> z2 24.94/7.25 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.25 l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) 24.94/7.25 gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) 24.94/7.28 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.28 e8(z0, z1, z2, z3) -> z2 24.94/7.28 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.28 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.28 Tuples: 24.94/7.28 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.28 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.28 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.28 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.28 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.28 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.28 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.28 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.28 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.28 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.28 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.28 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.28 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.28 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.28 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.28 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.28 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.28 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.28 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.28 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.28 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.28 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.28 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.28 S tuples: 24.94/7.28 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.28 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.28 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.28 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.28 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.28 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.28 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.28 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.28 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.28 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.28 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.28 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.28 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.28 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.28 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.28 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.28 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.28 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.28 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.28 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.28 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.28 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.28 K tuples:none 24.94/7.28 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 24.94/7.28 24.94/7.28 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 24.94/7.28 24.94/7.28 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 24.94/7.28 24.94/7.28 24.94/7.28 ---------------------------------------- 24.94/7.28 24.94/7.28 (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 24.94/7.28 The following rules are not usable and were removed: 24.94/7.28 m2(S(0), z0, z1, True) -> False 24.94/7.28 m2(S(S(z0)), z1, z2, True) -> True 24.94/7.28 m2(0, z0, z1, True) -> False 24.94/7.28 m3(S(0), z0, z1, z2) -> False 24.94/7.28 m3(S(S(z0)), z1, z2, z3) -> True 24.94/7.28 m3(0, z0, z1, z2) -> False 24.94/7.28 l8(z0, z1, z2, True, z3, z4) -> z0 24.94/7.28 l8(z0, z1, z2, False, z3, z4) -> l10(z0, z1, z2, False, z3, z4) 24.94/7.28 l5(z0, z1, z2, z3, z4, True) -> 0 24.94/7.28 l5(z0, z1, z2, z3, z4, False) -> l7(z0, z1, z2, z3, z4, False) 24.94/7.28 help1(S(0)) -> False 24.94/7.28 help1(S(S(z0))) -> True 24.94/7.28 help1(0) -> False 24.94/7.28 l15(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(z1, 0), z3, False, z4) 24.94/7.28 l15(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(z1, S(0)), z3, True, z4) 24.94/7.28 l13(z0, z1, z2, z3, False, z4) -> l16(z0, z1, gcd(0, z1), z3, False, z4) 24.94/7.28 l13(z0, z1, z2, z3, True, z4) -> l16(z0, z1, gcd(S(0), z1), z3, True, z4) 24.94/7.28 l2(z0, z1, z2, z3, z4, False) -> l3(z0, z1, z2, z3, z4, False) 24.94/7.28 l2(z0, z1, z2, z3, z4, True) -> z2 24.94/7.28 l11(z0, z1, z2, z3, z4, False) -> l14(z0, z1, z2, z3, z4, False) 24.94/7.28 l11(z0, z1, z2, z3, z4, True) -> l12(z0, z1, z2, z3, z4, True) 24.94/7.28 bool2Nat(False) -> 0 24.94/7.28 bool2Nat(True) -> S(0) 24.94/7.28 l9(z0, z1, z2, z3, z4, z5) -> z0 24.94/7.28 l6(z0, z1, z2, z3, z4, z5) -> 0 24.94/7.28 l4(z0, z1, z2, z3, z4, z5) -> l5(z0, z1, z2, z3, z4, False) 24.94/7.28 l1(z0, z1, z2, z3, z4, z5) -> l2(z0, z1, z2, z3, z4, False) 24.94/7.28 e7(z0, z1, z2, z3) -> False 24.94/7.28 e6(z0, z1, z2, z3) -> False 24.94/7.28 e5(z0, z1, z2, z3) -> True 24.94/7.28 l7(z0, z1, z2, z3, z4, z5) -> l8(z0, z1, z2, equal0(z0, z1), z4, z5) 24.94/7.28 l3(z0, z1, z2, z3, z4, z5) -> l4(z0, z1, 0, z3, z4, z5) 24.94/7.28 l16(z0, z1, z2, z3, z4, z5) -> z2 24.94/7.28 l14(z0, z1, z2, z3, z4, z5) -> l15(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.28 l12(z0, z1, z2, z3, z4, z5) -> l13(z0, z1, z2, z3, monus(z0, z1), z5) 24.94/7.28 l10(z0, z1, z2, z3, z4, z5) -> l11(z0, z1, z2, z3, z4, <(z0, z1)) 24.94/7.28 gcd(z0, z1) -> l1(z0, z1, 0, False, False, False) 24.94/7.28 e8(z0, z1, z2, z3) -> z2 24.94/7.28 24.94/7.28 ---------------------------------------- 24.94/7.28 24.94/7.28 (12) 24.94/7.28 Obligation: 24.94/7.28 Complexity Dependency Tuples Problem 24.94/7.28 24.94/7.28 Rules: 24.94/7.28 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.28 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.28 e2(z0, z1, z2, False) -> False 24.94/7.28 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.28 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.28 <(0, S(z0)) -> True 24.94/7.28 <(z0, 0) -> False 24.94/7.28 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.28 e4(z0, z1, z2, False) -> False 24.94/7.28 e4(z0, z1, z2, True) -> True 24.94/7.28 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.28 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.28 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.28 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.28 m5(z0, z1, z2, z3) -> z2 24.94/7.28 Tuples: 24.94/7.28 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.28 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.28 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.28 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.28 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.28 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.28 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.28 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.28 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.28 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.28 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.28 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.28 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.28 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.28 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.28 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.28 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.28 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 S tuples: 24.94/7.29 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.29 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.29 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.29 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.29 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.29 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.29 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.29 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.29 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.29 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.29 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.29 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.29 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 K tuples:none 24.94/7.29 Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 24.94/7.29 24.94/7.29 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 24.94/7.29 24.94/7.29 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 24.94/7.29 24.94/7.29 24.94/7.29 ---------------------------------------- 24.94/7.29 24.94/7.29 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 24.94/7.29 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 We considered the (Usable) Rules: 24.94/7.29 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.29 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.29 m5(z0, z1, z2, z3) -> z2 24.94/7.29 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.29 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.29 And the Tuples: 24.94/7.29 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.29 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.29 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.29 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.29 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.29 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.29 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.29 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.29 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.29 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.29 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.29 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.29 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.29 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 The order we found is given by the following interpretation: 24.94/7.29 24.94/7.29 Polynomial interpretation : 24.94/7.29 24.94/7.29 POL(0) = 0 24.94/7.29 POL(<(x_1, x_2)) = x_2 24.94/7.29 POL(<'(x_1, x_2)) = 0 24.94/7.29 POL(E1(x_1, x_2, x_3, x_4)) = [1] 24.94/7.29 POL(E2(x_1, x_2, x_3, x_4)) = [1] 24.94/7.29 POL(E3(x_1, x_2, x_3, x_4)) = [1] 24.94/7.29 POL(EQUAL0(x_1, x_2)) = [1] 24.94/7.29 POL(False) = [1] 24.94/7.29 POL(GCD(x_1, x_2)) = [1] 24.94/7.29 POL(L1(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L10(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L11(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L12(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 24.94/7.29 POL(L14(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L15(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 24.94/7.29 POL(L2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 24.94/7.29 POL(L3(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L4(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L5(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 24.94/7.29 POL(L7(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L8(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(M1(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(M2(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(M4(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(MONUS(x_1, x_2)) = 0 24.94/7.29 POL(S(x_1)) = 0 24.94/7.29 POL(True) = [1] 24.94/7.29 POL(c(x_1)) = x_1 24.94/7.29 POL(c1(x_1)) = x_1 24.94/7.29 POL(c11(x_1)) = x_1 24.94/7.29 POL(c13(x_1)) = x_1 24.94/7.29 POL(c20(x_1)) = x_1 24.94/7.29 POL(c21(x_1)) = x_1 24.94/7.29 POL(c22(x_1)) = x_1 24.94/7.29 POL(c23(x_1)) = x_1 24.94/7.29 POL(c24(x_1)) = x_1 24.94/7.29 POL(c25(x_1)) = x_1 24.94/7.29 POL(c26(x_1)) = x_1 24.94/7.29 POL(c28(x_1)) = x_1 24.94/7.29 POL(c29(x_1)) = x_1 24.94/7.29 POL(c32(x_1)) = x_1 24.94/7.29 POL(c35(x_1)) = x_1 24.94/7.29 POL(c36(x_1)) = x_1 24.94/7.29 POL(c40(x_1)) = x_1 24.94/7.29 POL(c42(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c43(x_1)) = x_1 24.94/7.29 POL(c45(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c46(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c47(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c48(x_1)) = x_1 24.94/7.29 POL(c49(x_1)) = x_1 24.94/7.29 POL(c51(x_1)) = x_1 24.94/7.29 POL(c6(x_1)) = x_1 24.94/7.29 POL(e1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_4 24.94/7.29 POL(e2(x_1, x_2, x_3, x_4)) = x_1 + x_4 24.94/7.29 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 24.94/7.29 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_4 24.94/7.29 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 24.94/7.29 POL(m1(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m2(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m4(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m5(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 24.94/7.29 POL(monus(x_1, x_2)) = 0 24.94/7.29 24.94/7.29 ---------------------------------------- 24.94/7.29 24.94/7.29 (14) 24.94/7.29 Obligation: 24.94/7.29 Complexity Dependency Tuples Problem 24.94/7.29 24.94/7.29 Rules: 24.94/7.29 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.29 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.29 e2(z0, z1, z2, False) -> False 24.94/7.29 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.29 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.29 <(0, S(z0)) -> True 24.94/7.29 <(z0, 0) -> False 24.94/7.29 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.29 e4(z0, z1, z2, False) -> False 24.94/7.29 e4(z0, z1, z2, True) -> True 24.94/7.29 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.29 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.29 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.29 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.29 m5(z0, z1, z2, z3) -> z2 24.94/7.29 Tuples: 24.94/7.29 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.29 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.29 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.29 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.29 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.29 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.29 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.29 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.29 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.29 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.29 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.29 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.29 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.29 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 S tuples: 24.94/7.29 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.29 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.29 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.29 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.29 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.29 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.29 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.29 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.29 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.29 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.29 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.29 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.29 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 K tuples: 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 24.94/7.29 24.94/7.29 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 24.94/7.29 24.94/7.29 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 24.94/7.29 24.94/7.29 24.94/7.29 ---------------------------------------- 24.94/7.29 24.94/7.29 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 24.94/7.29 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 We considered the (Usable) Rules: 24.94/7.29 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 24.94/7.29 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 24.94/7.29 m5(z0, z1, z2, z3) -> z2 24.94/7.29 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 24.94/7.29 monus(z0, z1) -> m1(z0, z1, False, False) 24.94/7.29 And the Tuples: 24.94/7.29 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 24.94/7.29 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 24.94/7.29 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 24.94/7.29 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 24.94/7.29 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 24.94/7.29 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 24.94/7.29 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 24.94/7.29 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 24.94/7.29 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 24.94/7.29 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 24.94/7.29 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 24.94/7.29 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 24.94/7.29 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 24.94/7.29 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 24.94/7.29 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 24.94/7.29 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 24.94/7.29 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 24.94/7.29 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 24.94/7.29 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 24.94/7.29 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 24.94/7.29 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 24.94/7.29 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 24.94/7.29 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 24.94/7.29 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 24.94/7.29 The order we found is given by the following interpretation: 24.94/7.29 24.94/7.29 Polynomial interpretation : 24.94/7.29 24.94/7.29 POL(0) = 0 24.94/7.29 POL(<(x_1, x_2)) = x_2 24.94/7.29 POL(<'(x_1, x_2)) = 0 24.94/7.29 POL(E1(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(E2(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(E3(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(EQUAL0(x_1, x_2)) = 0 24.94/7.29 POL(False) = [1] 24.94/7.29 POL(GCD(x_1, x_2)) = [1] 24.94/7.29 POL(L1(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L10(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L11(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L12(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 24.94/7.29 POL(L14(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L15(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 24.94/7.29 POL(L2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_6 24.94/7.29 POL(L3(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_3 24.94/7.29 POL(L4(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L5(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L7(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(L8(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 24.94/7.29 POL(M1(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(M2(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(M4(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(MONUS(x_1, x_2)) = 0 24.94/7.29 POL(S(x_1)) = 0 24.94/7.29 POL(True) = [1] 24.94/7.29 POL(c(x_1)) = x_1 24.94/7.29 POL(c1(x_1)) = x_1 24.94/7.29 POL(c11(x_1)) = x_1 24.94/7.29 POL(c13(x_1)) = x_1 24.94/7.29 POL(c20(x_1)) = x_1 24.94/7.29 POL(c21(x_1)) = x_1 24.94/7.29 POL(c22(x_1)) = x_1 24.94/7.29 POL(c23(x_1)) = x_1 24.94/7.29 POL(c24(x_1)) = x_1 24.94/7.29 POL(c25(x_1)) = x_1 24.94/7.29 POL(c26(x_1)) = x_1 24.94/7.29 POL(c28(x_1)) = x_1 24.94/7.29 POL(c29(x_1)) = x_1 24.94/7.29 POL(c32(x_1)) = x_1 24.94/7.29 POL(c35(x_1)) = x_1 24.94/7.29 POL(c36(x_1)) = x_1 24.94/7.29 POL(c40(x_1)) = x_1 24.94/7.29 POL(c42(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c43(x_1)) = x_1 24.94/7.29 POL(c45(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c46(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c47(x_1, x_2)) = x_1 + x_2 24.94/7.29 POL(c48(x_1)) = x_1 24.94/7.29 POL(c49(x_1)) = x_1 24.94/7.29 POL(c51(x_1)) = x_1 24.94/7.29 POL(c6(x_1)) = x_1 24.94/7.29 POL(e1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_4 24.94/7.29 POL(e2(x_1, x_2, x_3, x_4)) = x_1 + x_4 24.94/7.29 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 24.94/7.29 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_4 24.94/7.29 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 24.94/7.29 POL(m1(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m2(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m4(x_1, x_2, x_3, x_4)) = 0 24.94/7.29 POL(m5(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 24.94/7.29 POL(monus(x_1, x_2)) = 0 24.94/7.29 24.94/7.29 ---------------------------------------- 24.94/7.29 24.94/7.29 (16) 24.94/7.29 Obligation: 24.94/7.29 Complexity Dependency Tuples Problem 24.94/7.29 24.94/7.29 Rules: 24.94/7.29 equal0(z0, z1) -> e1(z0, z1, False, False) 24.94/7.29 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 24.94/7.29 e2(z0, z1, z2, False) -> False 24.94/7.29 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 24.94/7.29 <(S(z0), S(z1)) -> <(z0, z1) 24.94/7.29 <(0, S(z0)) -> True 24.94/7.29 <(z0, 0) -> False 24.94/7.29 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 24.94/7.29 e4(z0, z1, z2, False) -> False 24.94/7.29 e4(z0, z1, z2, True) -> True 25.28/7.30 monus(z0, z1) -> m1(z0, z1, False, False) 25.28/7.30 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 25.28/7.30 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 25.28/7.30 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 25.28/7.30 m5(z0, z1, z2, z3) -> z2 25.28/7.30 Tuples: 25.28/7.30 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 25.28/7.30 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.30 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.30 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.30 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.30 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.30 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.30 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.30 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.30 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.30 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.30 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.30 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.30 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.30 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.30 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.30 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.30 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.30 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.30 S tuples: 25.28/7.30 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.30 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.30 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.30 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.30 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.30 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.30 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.30 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.30 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.30 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.30 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.30 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.30 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.30 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.30 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.30 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.30 K tuples: 25.28/7.30 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.30 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.30 Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 25.28/7.30 25.28/7.30 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 25.28/7.30 25.28/7.30 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 25.28/7.30 25.28/7.30 25.28/7.30 ---------------------------------------- 25.28/7.30 25.28/7.30 (17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 25.28/7.30 The following tuples could be moved from S to K by knowledge propagation: 25.28/7.30 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.30 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.30 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.30 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.30 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.30 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.30 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.30 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.30 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.30 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.30 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.30 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.30 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.30 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.30 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.30 25.28/7.30 ---------------------------------------- 25.28/7.30 25.28/7.30 (18) 25.28/7.30 Obligation: 25.28/7.30 Complexity Dependency Tuples Problem 25.28/7.30 25.28/7.30 Rules: 25.28/7.30 equal0(z0, z1) -> e1(z0, z1, False, False) 25.28/7.30 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 25.28/7.30 e2(z0, z1, z2, False) -> False 25.28/7.30 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 25.28/7.30 <(S(z0), S(z1)) -> <(z0, z1) 25.28/7.30 <(0, S(z0)) -> True 25.28/7.30 <(z0, 0) -> False 25.28/7.30 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 25.28/7.30 e4(z0, z1, z2, False) -> False 25.28/7.30 e4(z0, z1, z2, True) -> True 25.28/7.30 monus(z0, z1) -> m1(z0, z1, False, False) 25.28/7.30 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 25.28/7.30 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 25.28/7.30 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 25.28/7.30 m5(z0, z1, z2, z3) -> z2 25.28/7.30 Tuples: 25.28/7.30 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 25.28/7.30 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.30 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.30 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.30 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.30 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.30 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.30 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.30 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.30 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.30 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.30 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.30 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.30 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.30 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.30 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.30 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.30 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.30 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.30 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.30 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.30 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.30 S tuples: 25.28/7.30 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.30 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.30 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.30 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.30 K tuples: 25.28/7.30 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.30 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.30 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.30 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.30 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.30 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.30 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.30 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.30 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.30 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.30 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.31 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.31 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.31 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.31 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.31 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.31 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.31 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.31 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.31 Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 25.28/7.31 25.28/7.31 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 25.28/7.31 25.28/7.31 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 25.28/7.31 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.28/7.31 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.28/7.31 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.31 We considered the (Usable) Rules: 25.28/7.31 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 25.28/7.31 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 25.28/7.31 m5(z0, z1, z2, z3) -> z2 25.28/7.31 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 25.28/7.31 monus(z0, z1) -> m1(z0, z1, False, False) 25.28/7.31 And the Tuples: 25.28/7.31 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 25.28/7.31 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.31 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.31 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.31 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.31 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.31 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.31 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.31 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.31 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.31 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.31 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.31 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.31 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.31 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.31 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.31 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.31 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.31 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.31 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.31 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.31 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.31 The order we found is given by the following interpretation: 25.28/7.31 25.28/7.31 Polynomial interpretation : 25.28/7.31 25.28/7.31 POL(0) = 0 25.28/7.31 POL(<(x_1, x_2)) = x_2 25.28/7.31 POL(<'(x_1, x_2)) = 0 25.28/7.31 POL(E1(x_1, x_2, x_3, x_4)) = x_3 + x_4 25.28/7.31 POL(E2(x_1, x_2, x_3, x_4)) = x_3 25.28/7.31 POL(E3(x_1, x_2, x_3, x_4)) = x_3 25.28/7.31 POL(EQUAL0(x_1, x_2)) = 0 25.28/7.31 POL(False) = 0 25.28/7.31 POL(GCD(x_1, x_2)) = [1] + x_1 + x_2 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 POL(L13(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_2 + x_3 + x_4 + x_5 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 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 25.28/7.31 POL(M1(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 25.28/7.31 POL(M2(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 25.28/7.31 POL(M4(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 25.28/7.31 POL(MONUS(x_1, x_2)) = x_1 25.28/7.31 POL(S(x_1)) = [1] + x_1 25.28/7.31 POL(True) = [1] 25.28/7.31 POL(c(x_1)) = x_1 25.28/7.31 POL(c1(x_1)) = x_1 25.28/7.31 POL(c11(x_1)) = x_1 25.28/7.31 POL(c13(x_1)) = x_1 25.28/7.31 POL(c20(x_1)) = x_1 25.28/7.31 POL(c21(x_1)) = x_1 25.28/7.31 POL(c22(x_1)) = x_1 25.28/7.31 POL(c23(x_1)) = x_1 25.28/7.31 POL(c24(x_1)) = x_1 25.28/7.31 POL(c25(x_1)) = x_1 25.28/7.31 POL(c26(x_1)) = x_1 25.28/7.31 POL(c28(x_1)) = x_1 25.28/7.31 POL(c29(x_1)) = x_1 25.28/7.31 POL(c32(x_1)) = x_1 25.28/7.31 POL(c35(x_1)) = x_1 25.28/7.31 POL(c36(x_1)) = x_1 25.28/7.31 POL(c40(x_1)) = x_1 25.28/7.31 POL(c42(x_1, x_2)) = x_1 + x_2 25.28/7.31 POL(c43(x_1)) = x_1 25.28/7.31 POL(c45(x_1, x_2)) = x_1 + x_2 25.28/7.31 POL(c46(x_1, x_2)) = x_1 + x_2 25.28/7.31 POL(c47(x_1, x_2)) = x_1 + x_2 25.28/7.31 POL(c48(x_1)) = x_1 25.28/7.31 POL(c49(x_1)) = x_1 25.28/7.31 POL(c51(x_1)) = x_1 25.28/7.31 POL(c6(x_1)) = x_1 25.28/7.31 POL(e1(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4 25.28/7.31 POL(e2(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_3 + x_4 25.28/7.31 POL(e3(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_3 25.28/7.31 POL(e4(x_1, x_2, x_3, x_4)) = [1] + x_3 + x_4 25.28/7.31 POL(equal0(x_1, x_2)) = [1] + x_1 + x_2 25.28/7.31 POL(m1(x_1, x_2, x_3, x_4)) = x_3 + x_4 25.28/7.31 POL(m2(x_1, x_2, x_3, x_4)) = x_3 + x_4 25.28/7.31 POL(m4(x_1, x_2, x_3, x_4)) = x_3 + x_4 25.28/7.31 POL(m5(x_1, x_2, x_3, x_4)) = x_3 + x_4 25.28/7.31 POL(monus(x_1, x_2)) = 0 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (20) 25.28/7.31 Obligation: 25.28/7.31 Complexity Dependency Tuples Problem 25.28/7.31 25.28/7.31 Rules: 25.28/7.31 equal0(z0, z1) -> e1(z0, z1, False, False) 25.28/7.31 e1(z0, z1, z2, z3) -> e2(z0, z1, z2, <(z0, z1)) 25.28/7.31 e2(z0, z1, z2, False) -> False 25.28/7.31 e2(z0, z1, z2, True) -> e3(z0, z1, z2, True) 25.28/7.31 <(S(z0), S(z1)) -> <(z0, z1) 25.28/7.31 <(0, S(z0)) -> True 25.28/7.31 <(z0, 0) -> False 25.28/7.31 e3(z0, z1, z2, z3) -> e4(z0, z1, z2, <(z1, z0)) 25.28/7.31 e4(z0, z1, z2, False) -> False 25.28/7.31 e4(z0, z1, z2, True) -> True 25.28/7.31 monus(z0, z1) -> m1(z0, z1, False, False) 25.28/7.31 m1(z0, z1, z2, z3) -> m2(z0, z1, z2, False) 25.28/7.31 m2(z0, z1, z2, False) -> m4(z0, z1, z2, False) 25.28/7.31 m4(S(z0), S(z1), z2, z3) -> m5(S(z0), S(z1), monus(z0, z1), z3) 25.28/7.31 m5(z0, z1, z2, z3) -> z2 25.28/7.31 Tuples: 25.28/7.31 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 25.28/7.31 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.31 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.31 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.31 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.31 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.31 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.31 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.31 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.31 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.31 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.31 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.31 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.31 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.31 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.31 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.31 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.31 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.31 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.31 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.31 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.31 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.31 S tuples: 25.28/7.31 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.31 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.31 K tuples: 25.28/7.31 E3(z0, z1, z2, z3) -> c51(<'(z1, z0)) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(<'(z0, z1)) 25.28/7.31 L3(z0, z1, z2, z3, z4, z5) -> c43(L4(z0, z1, 0, z3, z4, z5)) 25.28/7.31 L4(z0, z1, z2, z3, z4, z5) -> c35(L5(z0, z1, z2, z3, z4, False)) 25.28/7.31 L5(z0, z1, z2, z3, z4, False) -> c13(L7(z0, z1, z2, z3, z4, False)) 25.28/7.31 L7(z0, z1, z2, z3, z4, z5) -> c42(L8(z0, z1, z2, equal0(z0, z1), z4, z5), EQUAL0(z0, z1)) 25.28/7.31 L8(z0, z1, z2, False, z3, z4) -> c11(L10(z0, z1, z2, False, z3, z4)) 25.28/7.31 EQUAL0(z0, z1) -> c49(E1(z0, z1, False, False)) 25.28/7.31 L10(z0, z1, z2, z3, z4, z5) -> c47(L11(z0, z1, z2, z3, z4, <(z0, z1)), <'(z0, z1)) 25.28/7.31 E1(z0, z1, z2, z3) -> c1(E2(z0, z1, z2, <(z0, z1))) 25.28/7.31 L11(z0, z1, z2, z3, z4, False) -> c28(L14(z0, z1, z2, z3, z4, False)) 25.28/7.31 L11(z0, z1, z2, z3, z4, True) -> c29(L12(z0, z1, z2, z3, z4, True)) 25.28/7.31 E2(z0, z1, z2, True) -> c20(E3(z0, z1, z2, True)) 25.28/7.31 L14(z0, z1, z2, z3, z4, z5) -> c45(L15(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L12(z0, z1, z2, z3, z4, z5) -> c46(L13(z0, z1, z2, z3, monus(z0, z1), z5), MONUS(z0, z1)) 25.28/7.31 L15(z0, z1, z2, z3, False, z4) -> c21(GCD(z1, 0)) 25.28/7.31 L15(z0, z1, z2, z3, True, z4) -> c22(GCD(z1, S(0))) 25.28/7.31 L13(z0, z1, z2, z3, False, z4) -> c23(GCD(0, z1)) 25.28/7.31 L13(z0, z1, z2, z3, True, z4) -> c24(GCD(S(0), z1)) 25.28/7.31 GCD(z0, z1) -> c48(L1(z0, z1, 0, False, False, False)) 25.28/7.31 L1(z0, z1, z2, z3, z4, z5) -> c36(L2(z0, z1, z2, z3, z4, False)) 25.28/7.31 L2(z0, z1, z2, z3, z4, False) -> c26(L3(z0, z1, z2, z3, z4, False)) 25.28/7.31 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.31 Defined Rule Symbols: equal0_2, e1_4, e2_4, <_2, e3_4, e4_4, monus_2, m1_4, m2_4, m4_4, m5_4 25.28/7.31 25.28/7.31 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 25.28/7.31 25.28/7.31 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 25.28/7.31 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (21) CdtKnowledgeProof (FINISHED) 25.28/7.31 The following tuples could be moved from S to K by knowledge propagation: 25.28/7.31 MONUS(z0, z1) -> c40(M1(z0, z1, False, False)) 25.28/7.31 M1(z0, z1, z2, z3) -> c32(M2(z0, z1, z2, False)) 25.28/7.31 M2(z0, z1, z2, False) -> c6(M4(z0, z1, z2, False)) 25.28/7.31 M4(S(z0), S(z1), z2, z3) -> c25(MONUS(z0, z1)) 25.28/7.31 Now S is empty 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (22) 25.28/7.31 BOUNDS(1, 1) 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (23) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 25.28/7.31 Transformed a relative TRS into a decreasing-loop problem. 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (24) 25.28/7.31 Obligation: 25.28/7.31 Analyzing the following TRS for decreasing loops: 25.28/7.31 25.28/7.31 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 25.28/7.31 25.28/7.31 25.28/7.31 The TRS R consists of the following rules: 25.28/7.31 25.28/7.31 m2(S(0), b, res, True) -> False 25.28/7.31 m2(S(S(x)), b, res, True) -> True 25.28/7.31 m2(0, b, res, True) -> False 25.28/7.31 m3(S(0), b, res, t) -> False 25.28/7.31 m3(S(S(x)), b, res, t) -> True 25.28/7.31 m3(0, b, res, t) -> False 25.28/7.31 l8(res, y, res', True, mtmp, t) -> res 25.28/7.31 l5(x, y, res, tmp, mtmp, True) -> 0 25.28/7.31 help1(S(0)) -> False 25.28/7.31 help1(S(S(x))) -> True 25.28/7.31 e4(a, b, res, False) -> False 25.28/7.31 e4(a, b, res, True) -> True 25.28/7.31 e2(a, b, res, False) -> False 25.28/7.31 l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) 25.28/7.31 l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) 25.28/7.31 l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) 25.28/7.31 l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) 25.28/7.31 m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) 25.28/7.31 m2(a, b, res, False) -> m4(a, b, res, False) 25.28/7.31 l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) 25.28/7.31 l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, True) -> res 25.28/7.31 l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) 25.28/7.31 l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) 25.28/7.31 help1(0) -> False 25.28/7.31 e2(a, b, res, True) -> e3(a, b, res, True) 25.28/7.31 bool2Nat(False) -> 0 25.28/7.31 bool2Nat(True) -> S(0) 25.28/7.31 m1(a, x, res, t) -> m2(a, x, res, False) 25.28/7.31 l9(res, y, res', tmp, mtmp, t) -> res 25.28/7.31 l6(x, y, res, tmp, mtmp, t) -> 0 25.28/7.31 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) 25.28/7.31 l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) 25.28/7.31 e7(a, b, res, t) -> False 25.28/7.31 e6(a, b, res, t) -> False 25.28/7.31 e5(a, b, res, t) -> True 25.28/7.31 monus(a, b) -> m1(a, b, False, False) 25.28/7.31 m5(a, b, res, t) -> res 25.28/7.31 l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) 25.28/7.31 l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) 25.28/7.31 l16(x, y, res, tmp, mtmp, t) -> res 25.28/7.31 l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) 25.28/7.31 gcd(x, y) -> l1(x, y, 0, False, False, False) 25.28/7.31 equal0(a, b) -> e1(a, b, False, False) 25.28/7.31 e8(a, b, res, t) -> res 25.28/7.31 e3(a, b, res, t) -> e4(a, b, res, <(b, a)) 25.28/7.31 e1(a, b, res, t) -> e2(a, b, res, <(a, b)) 25.28/7.31 25.28/7.31 The (relative) TRS S consists of the following rules: 25.28/7.31 25.28/7.31 <(S(x), S(y)) -> <(x, y) 25.28/7.31 <(0, S(y)) -> True 25.28/7.31 <(x, 0) -> False 25.28/7.31 25.28/7.31 Rewrite Strategy: INNERMOST 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (25) DecreasingLoopProof (LOWER BOUND(ID)) 25.28/7.31 The following loop(s) give(s) rise to the lower bound Omega(n^1): 25.28/7.31 25.28/7.31 The rewrite sequence 25.28/7.31 25.28/7.31 monus(S(x'1_0), S(x2_0)) ->^+ m5(S(x'1_0), S(x2_0), monus(x'1_0, x2_0), False) 25.28/7.31 25.28/7.31 gives rise to a decreasing loop by considering the right hand sides subterm at position [2]. 25.28/7.31 25.28/7.31 The pumping substitution is [x'1_0 / S(x'1_0), x2_0 / S(x2_0)]. 25.28/7.31 25.28/7.31 The result substitution is [ ]. 25.28/7.31 25.28/7.31 25.28/7.31 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (26) 25.28/7.31 Complex Obligation (BEST) 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (27) 25.28/7.31 Obligation: 25.28/7.31 Proved the lower bound n^1 for the following obligation: 25.28/7.31 25.28/7.31 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 25.28/7.31 25.28/7.31 25.28/7.31 The TRS R consists of the following rules: 25.28/7.31 25.28/7.31 m2(S(0), b, res, True) -> False 25.28/7.31 m2(S(S(x)), b, res, True) -> True 25.28/7.31 m2(0, b, res, True) -> False 25.28/7.31 m3(S(0), b, res, t) -> False 25.28/7.31 m3(S(S(x)), b, res, t) -> True 25.28/7.31 m3(0, b, res, t) -> False 25.28/7.31 l8(res, y, res', True, mtmp, t) -> res 25.28/7.31 l5(x, y, res, tmp, mtmp, True) -> 0 25.28/7.31 help1(S(0)) -> False 25.28/7.31 help1(S(S(x))) -> True 25.28/7.31 e4(a, b, res, False) -> False 25.28/7.31 e4(a, b, res, True) -> True 25.28/7.31 e2(a, b, res, False) -> False 25.28/7.31 l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) 25.28/7.31 l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) 25.28/7.31 l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) 25.28/7.31 l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) 25.28/7.31 m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) 25.28/7.31 m2(a, b, res, False) -> m4(a, b, res, False) 25.28/7.31 l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) 25.28/7.31 l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, True) -> res 25.28/7.31 l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) 25.28/7.31 l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) 25.28/7.31 help1(0) -> False 25.28/7.31 e2(a, b, res, True) -> e3(a, b, res, True) 25.28/7.31 bool2Nat(False) -> 0 25.28/7.31 bool2Nat(True) -> S(0) 25.28/7.31 m1(a, x, res, t) -> m2(a, x, res, False) 25.28/7.31 l9(res, y, res', tmp, mtmp, t) -> res 25.28/7.31 l6(x, y, res, tmp, mtmp, t) -> 0 25.28/7.31 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) 25.28/7.31 l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) 25.28/7.31 e7(a, b, res, t) -> False 25.28/7.31 e6(a, b, res, t) -> False 25.28/7.31 e5(a, b, res, t) -> True 25.28/7.31 monus(a, b) -> m1(a, b, False, False) 25.28/7.31 m5(a, b, res, t) -> res 25.28/7.31 l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) 25.28/7.31 l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) 25.28/7.31 l16(x, y, res, tmp, mtmp, t) -> res 25.28/7.31 l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) 25.28/7.31 gcd(x, y) -> l1(x, y, 0, False, False, False) 25.28/7.31 equal0(a, b) -> e1(a, b, False, False) 25.28/7.31 e8(a, b, res, t) -> res 25.28/7.31 e3(a, b, res, t) -> e4(a, b, res, <(b, a)) 25.28/7.31 e1(a, b, res, t) -> e2(a, b, res, <(a, b)) 25.28/7.31 25.28/7.31 The (relative) TRS S consists of the following rules: 25.28/7.31 25.28/7.31 <(S(x), S(y)) -> <(x, y) 25.28/7.31 <(0, S(y)) -> True 25.28/7.31 <(x, 0) -> False 25.28/7.31 25.28/7.31 Rewrite Strategy: INNERMOST 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (28) LowerBoundPropagationProof (FINISHED) 25.28/7.31 Propagated lower bound. 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (29) 25.28/7.31 BOUNDS(n^1, INF) 25.28/7.31 25.28/7.31 ---------------------------------------- 25.28/7.31 25.28/7.31 (30) 25.28/7.31 Obligation: 25.28/7.31 Analyzing the following TRS for decreasing loops: 25.28/7.31 25.28/7.31 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 25.28/7.31 25.28/7.31 25.28/7.31 The TRS R consists of the following rules: 25.28/7.31 25.28/7.31 m2(S(0), b, res, True) -> False 25.28/7.31 m2(S(S(x)), b, res, True) -> True 25.28/7.31 m2(0, b, res, True) -> False 25.28/7.31 m3(S(0), b, res, t) -> False 25.28/7.31 m3(S(S(x)), b, res, t) -> True 25.28/7.31 m3(0, b, res, t) -> False 25.28/7.31 l8(res, y, res', True, mtmp, t) -> res 25.28/7.31 l5(x, y, res, tmp, mtmp, True) -> 0 25.28/7.31 help1(S(0)) -> False 25.28/7.31 help1(S(S(x))) -> True 25.28/7.31 e4(a, b, res, False) -> False 25.28/7.31 e4(a, b, res, True) -> True 25.28/7.31 e2(a, b, res, False) -> False 25.28/7.31 l15(x, y, res, tmp, False, t) -> l16(x, y, gcd(y, 0), tmp, False, t) 25.28/7.31 l15(x, y, res, tmp, True, t) -> l16(x, y, gcd(y, S(0)), tmp, True, t) 25.28/7.31 l13(x, y, res, tmp, False, t) -> l16(x, y, gcd(0, y), tmp, False, t) 25.28/7.31 l13(x, y, res, tmp, True, t) -> l16(x, y, gcd(S(0), y), tmp, True, t) 25.28/7.31 m4(S(x'), S(x), res, t) -> m5(S(x'), S(x), monus(x', x), t) 25.28/7.31 m2(a, b, res, False) -> m4(a, b, res, False) 25.28/7.31 l8(x, y, res, False, mtmp, t) -> l10(x, y, res, False, mtmp, t) 25.28/7.31 l5(x, y, res, tmp, mtmp, False) -> l7(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, False) -> l3(x, y, res, tmp, mtmp, False) 25.28/7.31 l2(x, y, res, tmp, mtmp, True) -> res 25.28/7.31 l11(x, y, res, tmp, mtmp, False) -> l14(x, y, res, tmp, mtmp, False) 25.28/7.31 l11(x, y, res, tmp, mtmp, True) -> l12(x, y, res, tmp, mtmp, True) 25.28/7.31 help1(0) -> False 25.28/7.31 e2(a, b, res, True) -> e3(a, b, res, True) 25.28/7.31 bool2Nat(False) -> 0 25.28/7.31 bool2Nat(True) -> S(0) 25.28/7.31 m1(a, x, res, t) -> m2(a, x, res, False) 25.28/7.31 l9(res, y, res', tmp, mtmp, t) -> res 25.28/7.31 l6(x, y, res, tmp, mtmp, t) -> 0 25.28/7.31 l4(x', x, res, tmp, mtmp, t) -> l5(x', x, res, tmp, mtmp, False) 25.28/7.31 l1(x, y, res, tmp, mtmp, t) -> l2(x, y, res, tmp, mtmp, False) 25.28/7.31 e7(a, b, res, t) -> False 25.28/7.31 e6(a, b, res, t) -> False 25.28/7.31 e5(a, b, res, t) -> True 25.28/7.31 monus(a, b) -> m1(a, b, False, False) 25.28/7.31 m5(a, b, res, t) -> res 25.28/7.31 l7(x, y, res, tmp, mtmp, t) -> l8(x, y, res, equal0(x, y), mtmp, t) 25.28/7.31 l3(x, y, res, tmp, mtmp, t) -> l4(x, y, 0, tmp, mtmp, t) 25.28/7.31 l16(x, y, res, tmp, mtmp, t) -> res 25.28/7.31 l14(x, y, res, tmp, mtmp, t) -> l15(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l12(x, y, res, tmp, mtmp, t) -> l13(x, y, res, tmp, monus(x, y), t) 25.28/7.31 l10(x, y, res, tmp, mtmp, t) -> l11(x, y, res, tmp, mtmp, <(x, y)) 25.28/7.31 gcd(x, y) -> l1(x, y, 0, False, False, False) 25.28/7.31 equal0(a, b) -> e1(a, b, False, False) 25.28/7.31 e8(a, b, res, t) -> res 25.28/7.31 e3(a, b, res, t) -> e4(a, b, res, <(b, a)) 25.28/7.31 e1(a, b, res, t) -> e2(a, b, res, <(a, b)) 25.28/7.31 25.28/7.31 The (relative) TRS S consists of the following rules: 25.28/7.31 25.28/7.31 <(S(x), S(y)) -> <(x, y) 25.28/7.31 <(0, S(y)) -> True 25.28/7.31 <(x, 0) -> False 25.28/7.31 25.28/7.31 Rewrite Strategy: INNERMOST 25.93/7.90 EOF