332.74/291.50 WORST_CASE(Omega(n^1), O(n^2)) 332.75/291.52 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 332.75/291.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 332.75/291.52 332.75/291.52 332.75/291.52 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 332.75/291.52 332.75/291.52 (0) CpxRelTRS 332.75/291.52 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 250 ms] 332.75/291.52 (2) CpxRelTRS 332.75/291.52 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 332.75/291.52 (4) CdtProblem 332.75/291.52 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (6) CdtProblem 332.75/291.52 (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (8) CdtProblem 332.75/291.52 (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (10) CdtProblem 332.75/291.52 (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (12) CdtProblem 332.75/291.52 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 68 ms] 332.75/291.52 (14) CdtProblem 332.75/291.52 (15) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (16) CdtProblem 332.75/291.52 (17) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (18) CdtProblem 332.75/291.52 (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 221 ms] 332.75/291.52 (20) CdtProblem 332.75/291.52 (21) CdtKnowledgeProof [FINISHED, 0 ms] 332.75/291.52 (22) BOUNDS(1, 1) 332.75/291.52 (23) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (24) CpxRelTRS 332.75/291.52 (25) SlicingProof [LOWER BOUND(ID), 0 ms] 332.75/291.52 (26) CpxRelTRS 332.75/291.52 (27) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 332.75/291.52 (28) typed CpxTrs 332.75/291.52 (29) OrderProof [LOWER BOUND(ID), 0 ms] 332.75/291.52 (30) typed CpxTrs 332.75/291.52 (31) RewriteLemmaProof [LOWER BOUND(ID), 504 ms] 332.75/291.52 (32) BEST 332.75/291.52 (33) proven lower bound 332.75/291.52 (34) LowerBoundPropagationProof [FINISHED, 0 ms] 332.75/291.52 (35) BOUNDS(n^1, INF) 332.75/291.52 (36) typed CpxTrs 332.75/291.52 (37) RewriteLemmaProof [LOWER BOUND(ID), 53 ms] 332.75/291.52 (38) typed CpxTrs 332.75/291.52 332.75/291.52 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (0) 332.75/291.52 Obligation: 332.75/291.52 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 332.75/291.52 332.75/291.52 332.75/291.52 The TRS R consists of the following rules: 332.75/291.52 332.75/291.52 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.52 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.52 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.52 332.75/291.52 The (relative) TRS S consists of the following rules: 332.75/291.52 332.75/291.52 <(S(x), S(y)) -> <(x, y) 332.75/291.52 <(0, S(y)) -> True 332.75/291.52 <(x, 0) -> False 332.75/291.52 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.52 gcd[Ite](True, x, y) -> x 332.75/291.52 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.52 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.52 equal0[Ite](False, a, b) -> False 332.75/291.52 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a), a, b) 332.75/291.52 equal0[True][Ite](False, a, b) -> False 332.75/291.52 equal0[True][Ite](True, a, b) -> True 332.75/291.52 332.75/291.52 Rewrite Strategy: INNERMOST 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 332.75/291.52 proved termination of relative rules 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (2) 332.75/291.52 Obligation: 332.75/291.52 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 332.75/291.52 332.75/291.52 332.75/291.52 The TRS R consists of the following rules: 332.75/291.52 332.75/291.52 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.52 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.52 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.52 332.75/291.52 The (relative) TRS S consists of the following rules: 332.75/291.52 332.75/291.52 <(S(x), S(y)) -> <(x, y) 332.75/291.52 <(0, S(y)) -> True 332.75/291.52 <(x, 0) -> False 332.75/291.52 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.52 gcd[Ite](True, x, y) -> x 332.75/291.52 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.52 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.52 equal0[Ite](False, a, b) -> False 332.75/291.52 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a), a, b) 332.75/291.52 equal0[True][Ite](False, a, b) -> False 332.75/291.52 equal0[True][Ite](True, a, b) -> True 332.75/291.52 332.75/291.52 Rewrite Strategy: INNERMOST 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 332.75/291.52 Converted Cpx (relative) TRS to CDT 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (4) 332.75/291.52 Obligation: 332.75/291.52 Complexity Dependency Tuples Problem 332.75/291.52 332.75/291.52 Rules: 332.75/291.52 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.52 <(0, S(z0)) -> True 332.75/291.52 <(z0, 0) -> False 332.75/291.52 gcd[Ite](False, z0, z1) -> gcd[False][Ite](<(z0, z1), z0, z1) 332.75/291.52 gcd[Ite](True, z0, z1) -> z0 332.75/291.52 gcd[False][Ite](False, z0, z1) -> gcd(z1, monus(z1, z0)) 332.75/291.52 gcd[False][Ite](True, z0, z1) -> gcd(monus(z0, z1), z1) 332.75/291.52 equal0[Ite](False, z0, z1) -> False 332.75/291.52 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.52 equal0[True][Ite](False, z0, z1) -> False 332.75/291.52 equal0[True][Ite](True, z0, z1) -> True 332.75/291.52 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.52 gcd(z0, z1) -> gcd[Ite](equal0(z0, z1), z0, z1) 332.75/291.52 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.52 Tuples: 332.75/291.52 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.52 <'(0, S(z0)) -> c1 332.75/291.52 <'(z0, 0) -> c2 332.75/291.52 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 GCD[ITE](True, z0, z1) -> c4 332.75/291.52 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.52 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.52 EQUAL0[ITE](False, z0, z1) -> c7 332.75/291.52 EQUAL0[ITE](True, z0, z1) -> c8(EQUAL0[TRUE][ITE](<(z1, z0), z0, z1), <'(z1, z0)) 332.75/291.52 EQUAL0[TRUE][ITE](False, z0, z1) -> c9 332.75/291.52 EQUAL0[TRUE][ITE](True, z0, z1) -> c10 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 S tuples: 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 K tuples:none 332.75/291.52 Defined Rule Symbols: monus_2, gcd_2, equal0_2, <_2, gcd[Ite]_3, gcd[False][Ite]_3, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.52 332.75/291.52 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, EQUAL0[ITE]_3, EQUAL0[TRUE][ITE]_3, MONUS_2, GCD_2, EQUAL0_2 332.75/291.52 332.75/291.52 Compound Symbols: c_1, c1, c2, c3_2, c4, c5_2, c6_2, c7, c8_2, c9, c10, c11_1, c12_2, c13_2 332.75/291.52 332.75/291.52 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 332.75/291.52 Removed 6 trailing nodes: 332.75/291.52 <'(z0, 0) -> c2 332.75/291.52 <'(0, S(z0)) -> c1 332.75/291.52 EQUAL0[ITE](False, z0, z1) -> c7 332.75/291.52 EQUAL0[TRUE][ITE](True, z0, z1) -> c10 332.75/291.52 EQUAL0[TRUE][ITE](False, z0, z1) -> c9 332.75/291.52 GCD[ITE](True, z0, z1) -> c4 332.75/291.52 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (6) 332.75/291.52 Obligation: 332.75/291.52 Complexity Dependency Tuples Problem 332.75/291.52 332.75/291.52 Rules: 332.75/291.52 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.52 <(0, S(z0)) -> True 332.75/291.52 <(z0, 0) -> False 332.75/291.52 gcd[Ite](False, z0, z1) -> gcd[False][Ite](<(z0, z1), z0, z1) 332.75/291.52 gcd[Ite](True, z0, z1) -> z0 332.75/291.52 gcd[False][Ite](False, z0, z1) -> gcd(z1, monus(z1, z0)) 332.75/291.52 gcd[False][Ite](True, z0, z1) -> gcd(monus(z0, z1), z1) 332.75/291.52 equal0[Ite](False, z0, z1) -> False 332.75/291.52 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.52 equal0[True][Ite](False, z0, z1) -> False 332.75/291.52 equal0[True][Ite](True, z0, z1) -> True 332.75/291.52 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.52 gcd(z0, z1) -> gcd[Ite](equal0(z0, z1), z0, z1) 332.75/291.52 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.52 Tuples: 332.75/291.52 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.52 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.52 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.52 EQUAL0[ITE](True, z0, z1) -> c8(EQUAL0[TRUE][ITE](<(z1, z0), z0, z1), <'(z1, z0)) 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 S tuples: 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 K tuples:none 332.75/291.52 Defined Rule Symbols: monus_2, gcd_2, equal0_2, <_2, gcd[Ite]_3, gcd[False][Ite]_3, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.52 332.75/291.52 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, EQUAL0[ITE]_3, MONUS_2, GCD_2, EQUAL0_2 332.75/291.52 332.75/291.52 Compound Symbols: c_1, c3_2, c5_2, c6_2, c8_2, c11_1, c12_2, c13_2 332.75/291.52 332.75/291.52 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 332.75/291.52 Removed 1 trailing tuple parts 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (8) 332.75/291.52 Obligation: 332.75/291.52 Complexity Dependency Tuples Problem 332.75/291.52 332.75/291.52 Rules: 332.75/291.52 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.52 <(0, S(z0)) -> True 332.75/291.52 <(z0, 0) -> False 332.75/291.52 gcd[Ite](False, z0, z1) -> gcd[False][Ite](<(z0, z1), z0, z1) 332.75/291.52 gcd[Ite](True, z0, z1) -> z0 332.75/291.52 gcd[False][Ite](False, z0, z1) -> gcd(z1, monus(z1, z0)) 332.75/291.52 gcd[False][Ite](True, z0, z1) -> gcd(monus(z0, z1), z1) 332.75/291.52 equal0[Ite](False, z0, z1) -> False 332.75/291.52 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.52 equal0[True][Ite](False, z0, z1) -> False 332.75/291.52 equal0[True][Ite](True, z0, z1) -> True 332.75/291.52 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.52 gcd(z0, z1) -> gcd[Ite](equal0(z0, z1), z0, z1) 332.75/291.52 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.52 Tuples: 332.75/291.52 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.52 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.52 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.52 S tuples: 332.75/291.52 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.52 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.52 EQUAL0(z0, z1) -> c13(EQUAL0[ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.52 K tuples:none 332.75/291.52 Defined Rule Symbols: monus_2, gcd_2, equal0_2, <_2, gcd[Ite]_3, gcd[False][Ite]_3, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.52 332.75/291.52 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0_2, EQUAL0[ITE]_3 332.75/291.52 332.75/291.52 Compound Symbols: c_1, c3_2, c5_2, c6_2, c11_1, c12_2, c13_2, c8_1 332.75/291.52 332.75/291.52 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) 332.75/291.52 Split RHS of tuples not part of any SCC 332.75/291.52 ---------------------------------------- 332.75/291.52 332.75/291.52 (10) 332.75/291.52 Obligation: 332.75/291.52 Complexity Dependency Tuples Problem 332.75/291.52 332.75/291.52 Rules: 332.75/291.52 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.52 <(0, S(z0)) -> True 332.75/291.52 <(z0, 0) -> False 332.75/291.52 gcd[Ite](False, z0, z1) -> gcd[False][Ite](<(z0, z1), z0, z1) 332.75/291.52 gcd[Ite](True, z0, z1) -> z0 332.75/291.52 gcd[False][Ite](False, z0, z1) -> gcd(z1, monus(z1, z0)) 332.75/291.52 gcd[False][Ite](True, z0, z1) -> gcd(monus(z0, z1), z1) 332.75/291.52 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 gcd(z0, z1) -> gcd[Ite](equal0(z0, z1), z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 S tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples:none 332.75/291.53 Defined Rule Symbols: monus_2, gcd_2, equal0_2, <_2, gcd[Ite]_3, gcd[False][Ite]_3, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c3_2, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 332.75/291.53 The following rules are not usable and were removed: 332.75/291.53 gcd[Ite](False, z0, z1) -> gcd[False][Ite](<(z0, z1), z0, z1) 332.75/291.53 gcd[Ite](True, z0, z1) -> z0 332.75/291.53 gcd[False][Ite](False, z0, z1) -> gcd(z1, monus(z1, z0)) 332.75/291.53 gcd[False][Ite](True, z0, z1) -> gcd(monus(z0, z1), z1) 332.75/291.53 gcd(z0, z1) -> gcd[Ite](equal0(z0, z1), z0, z1) 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (12) 332.75/291.53 Obligation: 332.75/291.53 Complexity Dependency Tuples Problem 332.75/291.53 332.75/291.53 Rules: 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(z0, 0) -> False 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 S tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples:none 332.75/291.53 Defined Rule Symbols: <_2, monus_2, equal0_2, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c3_2, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 332.75/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 We considered the (Usable) Rules: 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 And the Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 The order we found is given by the following interpretation: 332.75/291.53 332.75/291.53 Polynomial interpretation : 332.75/291.53 332.75/291.53 POL(0) = 0 332.75/291.53 POL(<(x_1, x_2)) = 0 332.75/291.53 POL(<'(x_1, x_2)) = 0 332.75/291.53 POL(EQUAL0(x_1, x_2)) = 0 332.75/291.53 POL(EQUAL0[ITE](x_1, x_2, x_3)) = 0 332.75/291.53 POL(False) = 0 332.75/291.53 POL(GCD(x_1, x_2)) = x_1 + [2]x_2 332.75/291.53 POL(GCD[FALSE][ITE](x_1, x_2, x_3)) = x_2 + [2]x_3 332.75/291.53 POL(GCD[ITE](x_1, x_2, x_3)) = x_2 + [2]x_3 332.75/291.53 POL(MONUS(x_1, x_2)) = x_1 332.75/291.53 POL(S(x_1)) = [2] + x_1 332.75/291.53 POL(True) = 0 332.75/291.53 POL(c(x_1)) = x_1 332.75/291.53 POL(c1(x_1)) = x_1 332.75/291.53 POL(c11(x_1)) = x_1 332.75/291.53 POL(c12(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c3(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c5(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c6(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c8(x_1)) = x_1 332.75/291.53 POL(equal0(x_1, x_2)) = [1] + x_1 + [3]x_2 332.75/291.53 POL(equal0[Ite](x_1, x_2, x_3)) = [3] + [3]x_2 + [3]x_3 332.75/291.53 POL(equal0[True][Ite](x_1, x_2, x_3)) = [3] + [3]x_2 + [3]x_3 332.75/291.53 POL(monus(x_1, x_2)) = 0 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (14) 332.75/291.53 Obligation: 332.75/291.53 Complexity Dependency Tuples Problem 332.75/291.53 332.75/291.53 Rules: 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(z0, 0) -> False 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 S tuples: 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 Defined Rule Symbols: <_2, monus_2, equal0_2, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[ITE]_3, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c3_2, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (15) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) 332.75/291.53 Use narrowing to replace GCD[ITE](False, z0, z1) -> c3(GCD[FALSE][ITE](<(z0, z1), z0, z1), <'(z0, z1)) by 332.75/291.53 GCD[ITE](False, S(z0), S(z1)) -> c3(GCD[FALSE][ITE](<(z0, z1), S(z0), S(z1)), <'(S(z0), S(z1))) 332.75/291.53 GCD[ITE](False, 0, S(z0)) -> c3(GCD[FALSE][ITE](True, 0, S(z0)), <'(0, S(z0))) 332.75/291.53 GCD[ITE](False, z0, 0) -> c3(GCD[FALSE][ITE](False, z0, 0), <'(z0, 0)) 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (16) 332.75/291.53 Obligation: 332.75/291.53 Complexity Dependency Tuples Problem 332.75/291.53 332.75/291.53 Rules: 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(z0, 0) -> False 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, S(z0), S(z1)) -> c3(GCD[FALSE][ITE](<(z0, z1), S(z0), S(z1)), <'(S(z0), S(z1))) 332.75/291.53 GCD[ITE](False, 0, S(z0)) -> c3(GCD[FALSE][ITE](True, 0, S(z0)), <'(0, S(z0))) 332.75/291.53 GCD[ITE](False, z0, 0) -> c3(GCD[FALSE][ITE](False, z0, 0), <'(z0, 0)) 332.75/291.53 S tuples: 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 Defined Rule Symbols: <_2, monus_2, equal0_2, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2, GCD[ITE]_3 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1, c3_2 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (17) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 332.75/291.53 Removed 2 trailing tuple parts 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (18) 332.75/291.53 Obligation: 332.75/291.53 Complexity Dependency Tuples Problem 332.75/291.53 332.75/291.53 Rules: 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(z0, 0) -> False 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, S(z0), S(z1)) -> c3(GCD[FALSE][ITE](<(z0, z1), S(z0), S(z1)), <'(S(z0), S(z1))) 332.75/291.53 GCD[ITE](False, 0, S(z0)) -> c3(GCD[FALSE][ITE](True, 0, S(z0))) 332.75/291.53 GCD[ITE](False, z0, 0) -> c3(GCD[FALSE][ITE](False, z0, 0)) 332.75/291.53 S tuples: 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 Defined Rule Symbols: <_2, monus_2, equal0_2, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2, GCD[ITE]_3 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1, c3_2, c3_1 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 332.75/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 We considered the (Usable) Rules: 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 <(z0, 0) -> False 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 And the Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, S(z0), S(z1)) -> c3(GCD[FALSE][ITE](<(z0, z1), S(z0), S(z1)), <'(S(z0), S(z1))) 332.75/291.53 GCD[ITE](False, 0, S(z0)) -> c3(GCD[FALSE][ITE](True, 0, S(z0))) 332.75/291.53 GCD[ITE](False, z0, 0) -> c3(GCD[FALSE][ITE](False, z0, 0)) 332.75/291.53 The order we found is given by the following interpretation: 332.75/291.53 332.75/291.53 Polynomial interpretation : 332.75/291.53 332.75/291.53 POL(0) = [2] 332.75/291.53 POL(<(x_1, x_2)) = x_1 332.75/291.53 POL(<'(x_1, x_2)) = 0 332.75/291.53 POL(EQUAL0(x_1, x_2)) = 0 332.75/291.53 POL(EQUAL0[ITE](x_1, x_2, x_3)) = 0 332.75/291.53 POL(False) = 0 332.75/291.53 POL(GCD(x_1, x_2)) = [1] + x_2 + [2]x_1*x_2 332.75/291.53 POL(GCD[FALSE][ITE](x_1, x_2, x_3)) = [1] + [2]x_1*x_3 332.75/291.53 POL(GCD[ITE](x_1, x_2, x_3)) = x_3 + [2]x_2*x_3 332.75/291.53 POL(MONUS(x_1, x_2)) = 0 332.75/291.53 POL(S(x_1)) = [1] + x_1 332.75/291.53 POL(True) = [1] 332.75/291.53 POL(c(x_1)) = x_1 332.75/291.53 POL(c1(x_1)) = x_1 332.75/291.53 POL(c11(x_1)) = x_1 332.75/291.53 POL(c12(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c3(x_1)) = x_1 332.75/291.53 POL(c3(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c5(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c6(x_1, x_2)) = x_1 + x_2 332.75/291.53 POL(c8(x_1)) = x_1 332.75/291.53 POL(equal0(x_1, x_2)) = 0 332.75/291.53 POL(equal0[Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 332.75/291.53 POL(equal0[True][Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 332.75/291.53 POL(monus(x_1, x_2)) = 0 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (20) 332.75/291.53 Obligation: 332.75/291.53 Complexity Dependency Tuples Problem 332.75/291.53 332.75/291.53 Rules: 332.75/291.53 <(S(z0), S(z1)) -> <(z0, z1) 332.75/291.53 <(0, S(z0)) -> True 332.75/291.53 <(z0, 0) -> False 332.75/291.53 monus(S(z0), S(z1)) -> monus(z0, z1) 332.75/291.53 equal0(z0, z1) -> equal0[Ite](<(z0, z1), z0, z1) 332.75/291.53 equal0[Ite](False, z0, z1) -> False 332.75/291.53 equal0[Ite](True, z0, z1) -> equal0[True][Ite](<(z1, z0), z0, z1) 332.75/291.53 equal0[True][Ite](False, z0, z1) -> False 332.75/291.53 equal0[True][Ite](True, z0, z1) -> True 332.75/291.53 Tuples: 332.75/291.53 <'(S(z0), S(z1)) -> c(<'(z0, z1)) 332.75/291.53 GCD[FALSE][ITE](False, z0, z1) -> c5(GCD(z1, monus(z1, z0)), MONUS(z1, z0)) 332.75/291.53 GCD[FALSE][ITE](True, z0, z1) -> c6(GCD(monus(z0, z1), z1), MONUS(z0, z1)) 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 GCD[ITE](False, S(z0), S(z1)) -> c3(GCD[FALSE][ITE](<(z0, z1), S(z0), S(z1)), <'(S(z0), S(z1))) 332.75/291.53 GCD[ITE](False, 0, S(z0)) -> c3(GCD[FALSE][ITE](True, 0, S(z0))) 332.75/291.53 GCD[ITE](False, z0, 0) -> c3(GCD[FALSE][ITE](False, z0, 0)) 332.75/291.53 S tuples: 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 K tuples: 332.75/291.53 MONUS(S(z0), S(z1)) -> c11(MONUS(z0, z1)) 332.75/291.53 GCD(z0, z1) -> c12(GCD[ITE](equal0(z0, z1), z0, z1), EQUAL0(z0, z1)) 332.75/291.53 Defined Rule Symbols: <_2, monus_2, equal0_2, equal0[Ite]_3, equal0[True][Ite]_3 332.75/291.53 332.75/291.53 Defined Pair Symbols: <'_2, GCD[FALSE][ITE]_3, MONUS_2, GCD_2, EQUAL0[ITE]_3, EQUAL0_2, GCD[ITE]_3 332.75/291.53 332.75/291.53 Compound Symbols: c_1, c5_2, c6_2, c11_1, c12_2, c8_1, c1_1, c3_2, c3_1 332.75/291.53 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (21) CdtKnowledgeProof (FINISHED) 332.75/291.53 The following tuples could be moved from S to K by knowledge propagation: 332.75/291.53 EQUAL0(z0, z1) -> c1(EQUAL0[ITE](<(z0, z1), z0, z1)) 332.75/291.53 EQUAL0(z0, z1) -> c1(<'(z0, z1)) 332.75/291.53 EQUAL0[ITE](True, z0, z1) -> c8(<'(z1, z0)) 332.75/291.53 Now S is empty 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (22) 332.75/291.53 BOUNDS(1, 1) 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (23) RenamingProof (BOTH BOUNDS(ID, ID)) 332.75/291.53 Renamed function symbols to avoid clashes with predefined symbol. 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (24) 332.75/291.53 Obligation: 332.75/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 332.75/291.53 332.75/291.53 332.75/291.53 The TRS R consists of the following rules: 332.75/291.53 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 332.75/291.53 The (relative) TRS S consists of the following rules: 332.75/291.53 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a), a, b) 332.75/291.53 equal0[True][Ite](False, a, b) -> False 332.75/291.53 equal0[True][Ite](True, a, b) -> True 332.75/291.53 332.75/291.53 Rewrite Strategy: INNERMOST 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (25) SlicingProof (LOWER BOUND(ID)) 332.75/291.53 Sliced the following arguments: 332.75/291.53 equal0[True][Ite]/1 332.75/291.53 equal0[True][Ite]/2 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (26) 332.75/291.53 Obligation: 332.75/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 332.75/291.53 332.75/291.53 332.75/291.53 The TRS R consists of the following rules: 332.75/291.53 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 332.75/291.53 The (relative) TRS S consists of the following rules: 332.75/291.53 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Rewrite Strategy: INNERMOST 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (27) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 332.75/291.53 Infered types. 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (28) 332.75/291.53 Obligation: 332.75/291.53 Innermost TRS: 332.75/291.53 Rules: 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Types: 332.75/291.53 monus :: S:0' -> S:0' -> S:0' 332.75/291.53 S :: S:0' -> S:0' 332.75/291.53 gcd :: S:0' -> S:0' -> S:0' 332.75/291.53 gcd[Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0 :: S:0' -> S:0' -> True:False 332.75/291.53 equal0[Ite] :: True:False -> S:0' -> S:0' -> True:False 332.75/291.53 < :: S:0' -> S:0' -> True:False 332.75/291.53 0' :: S:0' 332.75/291.53 True :: True:False 332.75/291.53 False :: True:False 332.75/291.53 gcd[False][Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0[True][Ite] :: True:False -> True:False 332.75/291.53 hole_S:0'1_1 :: S:0' 332.75/291.53 hole_True:False2_1 :: True:False 332.75/291.53 gen_S:0'3_1 :: Nat -> S:0' 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (29) OrderProof (LOWER BOUND(ID)) 332.75/291.53 Heuristically decided to analyse the following defined symbols: 332.75/291.53 monus, gcd, < 332.75/291.53 332.75/291.53 They will be analysed ascendingly in the following order: 332.75/291.53 monus < gcd 332.75/291.53 < < gcd 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (30) 332.75/291.53 Obligation: 332.75/291.53 Innermost TRS: 332.75/291.53 Rules: 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Types: 332.75/291.53 monus :: S:0' -> S:0' -> S:0' 332.75/291.53 S :: S:0' -> S:0' 332.75/291.53 gcd :: S:0' -> S:0' -> S:0' 332.75/291.53 gcd[Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0 :: S:0' -> S:0' -> True:False 332.75/291.53 equal0[Ite] :: True:False -> S:0' -> S:0' -> True:False 332.75/291.53 < :: S:0' -> S:0' -> True:False 332.75/291.53 0' :: S:0' 332.75/291.53 True :: True:False 332.75/291.53 False :: True:False 332.75/291.53 gcd[False][Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0[True][Ite] :: True:False -> True:False 332.75/291.53 hole_S:0'1_1 :: S:0' 332.75/291.53 hole_True:False2_1 :: True:False 332.75/291.53 gen_S:0'3_1 :: Nat -> S:0' 332.75/291.53 332.75/291.53 332.75/291.53 Generator Equations: 332.75/291.53 gen_S:0'3_1(0) <=> 0' 332.75/291.53 gen_S:0'3_1(+(x, 1)) <=> S(gen_S:0'3_1(x)) 332.75/291.53 332.75/291.53 332.75/291.53 The following defined symbols remain to be analysed: 332.75/291.53 monus, gcd, < 332.75/291.53 332.75/291.53 They will be analysed ascendingly in the following order: 332.75/291.53 monus < gcd 332.75/291.53 < < gcd 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (31) RewriteLemmaProof (LOWER BOUND(ID)) 332.75/291.53 Proved the following rewrite lemma: 332.75/291.53 monus(gen_S:0'3_1(+(1, n5_1)), gen_S:0'3_1(+(1, n5_1))) -> *4_1, rt in Omega(n5_1) 332.75/291.53 332.75/291.53 Induction Base: 332.75/291.53 monus(gen_S:0'3_1(+(1, 0)), gen_S:0'3_1(+(1, 0))) 332.75/291.53 332.75/291.53 Induction Step: 332.75/291.53 monus(gen_S:0'3_1(+(1, +(n5_1, 1))), gen_S:0'3_1(+(1, +(n5_1, 1)))) ->_R^Omega(1) 332.75/291.53 monus(gen_S:0'3_1(+(1, n5_1)), gen_S:0'3_1(+(1, n5_1))) ->_IH 332.75/291.53 *4_1 332.75/291.53 332.75/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (32) 332.75/291.53 Complex Obligation (BEST) 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (33) 332.75/291.53 Obligation: 332.75/291.53 Proved the lower bound n^1 for the following obligation: 332.75/291.53 332.75/291.53 Innermost TRS: 332.75/291.53 Rules: 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Types: 332.75/291.53 monus :: S:0' -> S:0' -> S:0' 332.75/291.53 S :: S:0' -> S:0' 332.75/291.53 gcd :: S:0' -> S:0' -> S:0' 332.75/291.53 gcd[Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0 :: S:0' -> S:0' -> True:False 332.75/291.53 equal0[Ite] :: True:False -> S:0' -> S:0' -> True:False 332.75/291.53 < :: S:0' -> S:0' -> True:False 332.75/291.53 0' :: S:0' 332.75/291.53 True :: True:False 332.75/291.53 False :: True:False 332.75/291.53 gcd[False][Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0[True][Ite] :: True:False -> True:False 332.75/291.53 hole_S:0'1_1 :: S:0' 332.75/291.53 hole_True:False2_1 :: True:False 332.75/291.53 gen_S:0'3_1 :: Nat -> S:0' 332.75/291.53 332.75/291.53 332.75/291.53 Generator Equations: 332.75/291.53 gen_S:0'3_1(0) <=> 0' 332.75/291.53 gen_S:0'3_1(+(x, 1)) <=> S(gen_S:0'3_1(x)) 332.75/291.53 332.75/291.53 332.75/291.53 The following defined symbols remain to be analysed: 332.75/291.53 monus, gcd, < 332.75/291.53 332.75/291.53 They will be analysed ascendingly in the following order: 332.75/291.53 monus < gcd 332.75/291.53 < < gcd 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (34) LowerBoundPropagationProof (FINISHED) 332.75/291.53 Propagated lower bound. 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (35) 332.75/291.53 BOUNDS(n^1, INF) 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (36) 332.75/291.53 Obligation: 332.75/291.53 Innermost TRS: 332.75/291.53 Rules: 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Types: 332.75/291.53 monus :: S:0' -> S:0' -> S:0' 332.75/291.53 S :: S:0' -> S:0' 332.75/291.53 gcd :: S:0' -> S:0' -> S:0' 332.75/291.53 gcd[Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0 :: S:0' -> S:0' -> True:False 332.75/291.53 equal0[Ite] :: True:False -> S:0' -> S:0' -> True:False 332.75/291.53 < :: S:0' -> S:0' -> True:False 332.75/291.53 0' :: S:0' 332.75/291.53 True :: True:False 332.75/291.53 False :: True:False 332.75/291.53 gcd[False][Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0[True][Ite] :: True:False -> True:False 332.75/291.53 hole_S:0'1_1 :: S:0' 332.75/291.53 hole_True:False2_1 :: True:False 332.75/291.53 gen_S:0'3_1 :: Nat -> S:0' 332.75/291.53 332.75/291.53 332.75/291.53 Lemmas: 332.75/291.53 monus(gen_S:0'3_1(+(1, n5_1)), gen_S:0'3_1(+(1, n5_1))) -> *4_1, rt in Omega(n5_1) 332.75/291.53 332.75/291.53 332.75/291.53 Generator Equations: 332.75/291.53 gen_S:0'3_1(0) <=> 0' 332.75/291.53 gen_S:0'3_1(+(x, 1)) <=> S(gen_S:0'3_1(x)) 332.75/291.53 332.75/291.53 332.75/291.53 The following defined symbols remain to be analysed: 332.75/291.53 <, gcd 332.75/291.53 332.75/291.53 They will be analysed ascendingly in the following order: 332.75/291.53 < < gcd 332.75/291.53 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (37) RewriteLemmaProof (LOWER BOUND(ID)) 332.75/291.53 Proved the following rewrite lemma: 332.75/291.53 <(gen_S:0'3_1(n353_1), gen_S:0'3_1(+(1, n353_1))) -> True, rt in Omega(0) 332.75/291.53 332.75/291.53 Induction Base: 332.75/291.53 <(gen_S:0'3_1(0), gen_S:0'3_1(+(1, 0))) ->_R^Omega(0) 332.75/291.53 True 332.75/291.53 332.75/291.53 Induction Step: 332.75/291.53 <(gen_S:0'3_1(+(n353_1, 1)), gen_S:0'3_1(+(1, +(n353_1, 1)))) ->_R^Omega(0) 332.75/291.53 <(gen_S:0'3_1(n353_1), gen_S:0'3_1(+(1, n353_1))) ->_IH 332.75/291.53 True 332.75/291.53 332.75/291.53 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 332.75/291.53 ---------------------------------------- 332.75/291.53 332.75/291.53 (38) 332.75/291.53 Obligation: 332.75/291.53 Innermost TRS: 332.75/291.53 Rules: 332.75/291.53 monus(S(x'), S(x)) -> monus(x', x) 332.75/291.53 gcd(x, y) -> gcd[Ite](equal0(x, y), x, y) 332.75/291.53 equal0(a, b) -> equal0[Ite](<(a, b), a, b) 332.75/291.53 <(S(x), S(y)) -> <(x, y) 332.75/291.53 <(0', S(y)) -> True 332.75/291.53 <(x, 0') -> False 332.75/291.53 gcd[Ite](False, x, y) -> gcd[False][Ite](<(x, y), x, y) 332.75/291.53 gcd[Ite](True, x, y) -> x 332.75/291.53 gcd[False][Ite](False, x, y) -> gcd(y, monus(y, x)) 332.75/291.53 gcd[False][Ite](True, x, y) -> gcd(monus(x, y), y) 332.75/291.53 equal0[Ite](False, a, b) -> False 332.75/291.53 equal0[Ite](True, a, b) -> equal0[True][Ite](<(b, a)) 332.75/291.53 equal0[True][Ite](False) -> False 332.75/291.53 equal0[True][Ite](True) -> True 332.75/291.53 332.75/291.53 Types: 332.75/291.53 monus :: S:0' -> S:0' -> S:0' 332.75/291.53 S :: S:0' -> S:0' 332.75/291.53 gcd :: S:0' -> S:0' -> S:0' 332.75/291.53 gcd[Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0 :: S:0' -> S:0' -> True:False 332.75/291.53 equal0[Ite] :: True:False -> S:0' -> S:0' -> True:False 332.75/291.53 < :: S:0' -> S:0' -> True:False 332.75/291.53 0' :: S:0' 332.75/291.53 True :: True:False 332.75/291.53 False :: True:False 332.75/291.53 gcd[False][Ite] :: True:False -> S:0' -> S:0' -> S:0' 332.75/291.53 equal0[True][Ite] :: True:False -> True:False 332.75/291.53 hole_S:0'1_1 :: S:0' 332.75/291.53 hole_True:False2_1 :: True:False 332.75/291.53 gen_S:0'3_1 :: Nat -> S:0' 332.75/291.53 332.75/291.53 332.75/291.53 Lemmas: 332.75/291.53 monus(gen_S:0'3_1(+(1, n5_1)), gen_S:0'3_1(+(1, n5_1))) -> *4_1, rt in Omega(n5_1) 332.75/291.53 <(gen_S:0'3_1(n353_1), gen_S:0'3_1(+(1, n353_1))) -> True, rt in Omega(0) 332.75/291.53 332.75/291.53 332.75/291.53 Generator Equations: 332.75/291.53 gen_S:0'3_1(0) <=> 0' 332.75/291.53 gen_S:0'3_1(+(x, 1)) <=> S(gen_S:0'3_1(x)) 332.75/291.53 332.75/291.53 332.75/291.53 The following defined symbols remain to be analysed: 332.75/291.53 gcd 332.75/291.58 EOF