WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CdtProblem (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CdtProblem (15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 20 ms] (18) CdtProblem (19) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (20) CdtProblem (21) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (22) CdtProblem (23) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (24) CdtProblem (25) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (26) CdtProblem (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 12 ms] (28) CdtProblem (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 15 ms] (30) CdtProblem (31) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (32) CdtProblem (33) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (34) CdtProblem (35) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 8 ms] (36) CdtProblem (37) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (38) CdtProblem (39) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (40) CdtProblem (41) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (42) CdtProblem (43) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (44) CdtProblem (45) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (46) CdtProblem (47) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (48) CdtProblem (49) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (50) CdtProblem (51) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (52) CdtProblem (53) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (54) CdtProblem (55) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 7 ms] (56) CdtProblem (57) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 9 ms] (58) CdtProblem (59) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (60) CdtProblem (61) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (62) CdtProblem (63) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 10 ms] (64) CdtProblem (65) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms] (66) CdtProblem (67) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms] (68) CdtProblem (69) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 9 ms] (70) CdtProblem (71) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms] (72) CdtProblem (73) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (74) CdtProblem (75) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 9 ms] (76) CdtProblem (77) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 30 ms] (78) CdtProblem (79) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (80) BOUNDS(1, 1) (81) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (82) CpxTRS (83) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (84) typed CpxTrs (85) OrderProof [LOWER BOUND(ID), 0 ms] (86) typed CpxTrs (87) RewriteLemmaProof [LOWER BOUND(ID), 248 ms] (88) BEST (89) proven lower bound (90) LowerBoundPropagationProof [FINISHED, 0 ms] (91) BOUNDS(n^1, INF) (92) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: cond(true, x) -> cond(odd(x), p(x)) odd(0) -> false odd(s(0)) -> true odd(s(s(x))) -> odd(x) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: cond(true, z0) -> cond(odd(z0), p(z0)) odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0), P(z0)) ODD(0) -> c1 ODD(s(0)) -> c2 ODD(s(s(z0))) -> c3(ODD(z0)) P(0) -> c4 P(s(z0)) -> c5 S tuples: COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0), P(z0)) ODD(0) -> c1 ODD(s(0)) -> c2 ODD(s(s(z0))) -> c3(ODD(z0)) P(0) -> c4 P(s(z0)) -> c5 K tuples:none Defined Rule Symbols: cond_2, odd_1, p_1 Defined Pair Symbols: COND_2, ODD_1, P_1 Compound Symbols: c_3, c1, c2, c3_1, c4, c5 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 4 trailing nodes: ODD(0) -> c1 P(s(z0)) -> c5 ODD(s(0)) -> c2 P(0) -> c4 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: cond(true, z0) -> cond(odd(z0), p(z0)) odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0), P(z0)) ODD(s(s(z0))) -> c3(ODD(z0)) S tuples: COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0), P(z0)) ODD(s(s(z0))) -> c3(ODD(z0)) K tuples:none Defined Rule Symbols: cond_2, odd_1, p_1 Defined Pair Symbols: COND_2, ODD_1 Compound Symbols: c_3, c3_1 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: cond(true, z0) -> cond(odd(z0), p(z0)) odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0)) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0)) K tuples:none Defined Rule Symbols: cond_2, odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2 ---------------------------------------- (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: cond(true, z0) -> cond(odd(z0), p(z0)) ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0)) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0)) K tuples:none Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2 ---------------------------------------- (9) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, z0) -> c(COND(odd(z0), p(z0)), ODD(z0)) by COND(true, 0) -> c(COND(odd(0), 0), ODD(0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, 0) -> c(COND(false, p(0)), ODD(0)) COND(true, s(0)) -> c(COND(true, p(s(0))), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0), ODD(0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, 0) -> c(COND(false, p(0)), ODD(0)) COND(true, s(0)) -> c(COND(true, p(s(0))), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0), ODD(0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, 0) -> c(COND(false, p(0)), ODD(0)) COND(true, s(0)) -> c(COND(true, p(s(0))), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) K tuples:none Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2 ---------------------------------------- (11) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing nodes: COND(true, 0) -> c(COND(false, p(0)), ODD(0)) ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0), ODD(0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(0)) -> c(COND(true, p(s(0))), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0), ODD(0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(0)) -> c(COND(true, p(s(0))), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) K tuples:none Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2 ---------------------------------------- (13) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing tuple parts ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: odd(0) -> false odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) p(0) -> 0 p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) K tuples:none Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: p(0) -> 0 ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) K tuples:none Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) We considered the (Usable) Rules: odd(0) -> false odd(s(0)) -> true p(s(z0)) -> z0 odd(s(s(z0))) -> odd(z0) And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = x_1 + x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = [1] POL(p(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (19) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) by COND(true, s(0)) -> c(COND(true, 0), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) ---------------------------------------- (20) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(0)) -> c(COND(true, 0), ODD(s(0))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (21) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (22) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (23) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(s(z0))) -> c(COND(odd(z0), p(s(s(z0)))), ODD(s(s(z0)))) by COND(true, s(s(x0))) -> c(COND(odd(x0), s(x0)), ODD(s(s(x0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, p(s(s(0)))), ODD(s(s(0)))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) ---------------------------------------- (24) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, p(s(s(0)))), ODD(s(s(0)))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(x0))) -> c(COND(odd(x0), s(x0)), ODD(s(s(x0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, p(s(s(0)))), ODD(s(s(0)))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2 ---------------------------------------- (25) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (26) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(x0))) -> c(COND(odd(x0), s(x0)), ODD(s(s(x0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2 ---------------------------------------- (27) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = [1] POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c3(x_1)) = x_1 POL(false) = 0 POL(odd(x_1)) = [1] + x_1 POL(p(x_1)) = [1] + x_1 POL(s(x_1)) = x_1 POL(true) = [1] ---------------------------------------- (28) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(x0))) -> c(COND(odd(x0), s(x0)), ODD(s(s(x0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2 ---------------------------------------- (29) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) We considered the (Usable) Rules: p(s(z0)) -> z0 And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(COND(x_1, x_2)) = [2]x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c3(x_1)) = x_1 POL(false) = [2] POL(odd(x_1)) = [3] POL(p(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 POL(true) = [3] ---------------------------------------- (30) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, 0) -> c(COND(odd(0), 0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2 ---------------------------------------- (31) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, 0) -> c(COND(odd(0), 0)) by COND(true, 0) -> c(COND(false, 0)) ---------------------------------------- (32) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, 0) -> c(COND(false, 0)) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, 0) -> c(COND(false, 0)) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2 ---------------------------------------- (33) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (34) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, 0) -> c S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, 0) -> c K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c ---------------------------------------- (35) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, 0) -> c We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, 0) -> c The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(COND(x_1, x_2)) = [1] POL(ODD(x_1)) = 0 POL(c) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = [1] + x_1 POL(p(x_1)) = [1] + x_1 POL(s(x_1)) = x_1 POL(true) = [1] ---------------------------------------- (36) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, 0) -> c S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(0)) -> c(COND(true, p(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, 0) -> c Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c ---------------------------------------- (37) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(0)) -> c(COND(true, p(s(0)))) by COND(true, s(0)) -> c(COND(true, 0)) ---------------------------------------- (38) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(0)) -> c(COND(true, 0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, 0) -> c S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(0)) -> c(COND(true, 0)) K tuples: COND(true, s(z0)) -> c(COND(odd(s(z0)), z0), ODD(s(z0))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, 0) -> c Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c ---------------------------------------- (39) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing nodes: COND(true, s(0)) -> c(COND(true, 0)) COND(true, 0) -> c ---------------------------------------- (40) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (41) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) by COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, s(0)), ODD(s(s(0)))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) ---------------------------------------- (42) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, s(0)), ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (43) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (44) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (45) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(s(x0))) -> c(COND(odd(x0), s(x0)), ODD(s(s(x0)))) by COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, s(0)), ODD(s(s(0)))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) ---------------------------------------- (46) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(0))) -> c(COND(false, s(0)), ODD(s(s(0)))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (47) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (48) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1 ---------------------------------------- (49) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (50) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c1_1 ---------------------------------------- (51) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(s(s(0)))) -> c(COND(true, p(s(s(s(0))))), ODD(s(s(s(0))))) by COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) ---------------------------------------- (52) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c(COND(true, s(s(0))), ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c1_1 ---------------------------------------- (53) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (54) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c1_1, c2_1 ---------------------------------------- (55) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = [1] POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = 0 POL(odd(x_1)) = [1] + x_1 POL(p(x_1)) = [1] + x_1 POL(s(x_1)) = x_1 POL(true) = [1] ---------------------------------------- (56) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c1_1, c2_1 ---------------------------------------- (57) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) We considered the (Usable) Rules: odd(0) -> false odd(s(0)) -> true p(s(z0)) -> z0 odd(s(s(z0))) -> odd(z0) And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = x_1 + x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = [1] POL(p(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (58) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_2, c_1, c1_1, c2_1 ---------------------------------------- (59) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), p(s(s(s(s(z0)))))), ODD(s(s(s(s(z0)))))) by COND(true, s(s(s(s(x0))))) -> c(COND(odd(x0), s(s(s(x0)))), ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(0))))) -> c(COND(false, p(s(s(s(s(0)))))), ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) ---------------------------------------- (60) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(0))))) -> c(COND(false, p(s(s(s(s(0)))))), ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(x0))))) -> c(COND(odd(x0), s(s(s(x0)))), ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(0))))) -> c(COND(false, p(s(s(s(s(0)))))), ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (61) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (62) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(x0))))) -> c(COND(odd(x0), s(s(s(x0)))), ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (63) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = [1] POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = 0 POL(odd(x_1)) = [1] + x_1 POL(p(x_1)) = [1] + x_1 POL(s(x_1)) = x_1 POL(true) = [1] ---------------------------------------- (64) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(x0))))) -> c(COND(odd(x0), s(s(s(x0)))), ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (65) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) We considered the (Usable) Rules: p(s(z0)) -> z0 And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(COND(x_1, x_2)) = x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = [1] + x_1 POL(p(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (66) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (67) CdtRewritingProof (BOTH BOUNDS(ID, ID)) Used rewriting to replace COND(true, s(s(s(s(s(0)))))) -> c(COND(true, p(s(s(s(s(s(0))))))), ODD(s(s(s(s(s(0))))))) by COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) ---------------------------------------- (68) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (69) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) We considered the (Usable) Rules: odd(0) -> false odd(s(0)) -> true p(s(z0)) -> z0 odd(s(s(z0))) -> odd(z0) And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = [1] + x_1 + x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = [1] POL(p(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (70) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (71) CdtRewritingProof (BOTH BOUNDS(ID, ID)) Used rewriting to replace COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), p(s(s(s(s(s(s(z0)))))))), ODD(s(s(s(s(s(s(z0)))))))) by COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) ---------------------------------------- (72) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false p(s(z0)) -> z0 Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) Defined Rule Symbols: odd_1, p_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (73) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: p(s(z0)) -> z0 ---------------------------------------- (74) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) Defined Rule Symbols: odd_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (75) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(COND(x_1, x_2)) = [2] + [2]x_2 POL(ODD(x_1)) = 0 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = [3] POL(odd(x_1)) = [3] POL(s(x_1)) = [1] + x_1 POL(true) = [3] ---------------------------------------- (76) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) S tuples: ODD(s(s(z0))) -> c3(ODD(z0)) K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) Defined Rule Symbols: odd_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (77) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. ODD(s(s(z0))) -> c3(ODD(z0)) We considered the (Usable) Rules:none And the Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(COND(x_1, x_2)) = [2]x_2^2 POL(ODD(x_1)) = [2] + [2]x_1 POL(c(x_1)) = x_1 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(false) = [1] POL(odd(x_1)) = 0 POL(s(x_1)) = [2] + x_1 POL(true) = 0 ---------------------------------------- (78) Obligation: Complexity Dependency Tuples Problem Rules: odd(s(0)) -> true odd(s(s(z0))) -> odd(z0) odd(0) -> false Tuples: ODD(s(s(z0))) -> c3(ODD(z0)) COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(0)))) -> c1(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c1(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) S tuples:none K tuples: COND(true, s(s(x0))) -> c(ODD(s(s(x0)))) COND(true, s(s(0))) -> c(ODD(s(s(0)))) COND(true, s(s(z0))) -> c(COND(odd(z0), s(z0)), ODD(s(s(z0)))) COND(true, s(s(s(0)))) -> c(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(ODD(s(s(s(0))))) COND(true, s(s(s(0)))) -> c2(COND(true, s(s(0)))) COND(true, s(s(s(s(x0))))) -> c(ODD(s(s(s(s(x0)))))) COND(true, s(s(s(s(0))))) -> c(ODD(s(s(s(s(0)))))) COND(true, s(s(s(s(z0))))) -> c(COND(odd(z0), s(s(s(z0)))), ODD(s(s(s(s(z0)))))) COND(true, s(s(s(s(s(0)))))) -> c(COND(true, s(s(s(s(0))))), ODD(s(s(s(s(s(0))))))) COND(true, s(s(s(s(s(s(z0))))))) -> c(COND(odd(z0), s(s(s(s(s(z0)))))), ODD(s(s(s(s(s(s(z0)))))))) ODD(s(s(z0))) -> c3(ODD(z0)) Defined Rule Symbols: odd_1 Defined Pair Symbols: ODD_1, COND_2 Compound Symbols: c3_1, c_1, c_2, c1_1, c2_1 ---------------------------------------- (79) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (80) BOUNDS(1, 1) ---------------------------------------- (81) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (82) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: cond(true, x) -> cond(odd(x), p(x)) odd(0') -> false odd(s(0')) -> true odd(s(s(x))) -> odd(x) p(0') -> 0' p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (83) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (84) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(odd(x), p(x)) odd(0') -> false odd(s(0')) -> true odd(s(s(x))) -> odd(x) p(0') -> 0' p(s(x)) -> x Types: cond :: true:false -> 0':s -> cond true :: true:false odd :: 0':s -> true:false p :: 0':s -> 0':s 0' :: 0':s false :: true:false s :: 0':s -> 0':s hole_cond1_0 :: cond hole_true:false2_0 :: true:false hole_0':s3_0 :: 0':s gen_0':s4_0 :: Nat -> 0':s ---------------------------------------- (85) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: cond, odd They will be analysed ascendingly in the following order: odd < cond ---------------------------------------- (86) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(odd(x), p(x)) odd(0') -> false odd(s(0')) -> true odd(s(s(x))) -> odd(x) p(0') -> 0' p(s(x)) -> x Types: cond :: true:false -> 0':s -> cond true :: true:false odd :: 0':s -> true:false p :: 0':s -> 0':s 0' :: 0':s false :: true:false s :: 0':s -> 0':s hole_cond1_0 :: cond hole_true:false2_0 :: true:false hole_0':s3_0 :: 0':s gen_0':s4_0 :: Nat -> 0':s Generator Equations: gen_0':s4_0(0) <=> 0' gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) The following defined symbols remain to be analysed: odd, cond They will be analysed ascendingly in the following order: odd < cond ---------------------------------------- (87) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: odd(gen_0':s4_0(*(2, n6_0))) -> false, rt in Omega(1 + n6_0) Induction Base: odd(gen_0':s4_0(*(2, 0))) ->_R^Omega(1) false Induction Step: odd(gen_0':s4_0(*(2, +(n6_0, 1)))) ->_R^Omega(1) odd(gen_0':s4_0(*(2, n6_0))) ->_IH false We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (88) Complex Obligation (BEST) ---------------------------------------- (89) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: cond(true, x) -> cond(odd(x), p(x)) odd(0') -> false odd(s(0')) -> true odd(s(s(x))) -> odd(x) p(0') -> 0' p(s(x)) -> x Types: cond :: true:false -> 0':s -> cond true :: true:false odd :: 0':s -> true:false p :: 0':s -> 0':s 0' :: 0':s false :: true:false s :: 0':s -> 0':s hole_cond1_0 :: cond hole_true:false2_0 :: true:false hole_0':s3_0 :: 0':s gen_0':s4_0 :: Nat -> 0':s Generator Equations: gen_0':s4_0(0) <=> 0' gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) The following defined symbols remain to be analysed: odd, cond They will be analysed ascendingly in the following order: odd < cond ---------------------------------------- (90) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (91) BOUNDS(n^1, INF) ---------------------------------------- (92) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(odd(x), p(x)) odd(0') -> false odd(s(0')) -> true odd(s(s(x))) -> odd(x) p(0') -> 0' p(s(x)) -> x Types: cond :: true:false -> 0':s -> cond true :: true:false odd :: 0':s -> true:false p :: 0':s -> 0':s 0' :: 0':s false :: true:false s :: 0':s -> 0':s hole_cond1_0 :: cond hole_true:false2_0 :: true:false hole_0':s3_0 :: 0':s gen_0':s4_0 :: Nat -> 0':s Lemmas: odd(gen_0':s4_0(*(2, n6_0))) -> false, rt in Omega(1 + n6_0) Generator Equations: gen_0':s4_0(0) <=> 0' gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) The following defined symbols remain to be analysed: cond