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 Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 55 ms] (4) CpxRelTRS (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (8) CdtProblem (9) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (10) CdtProblem (11) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (14) CdtProblem (15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 198 ms] (18) CdtProblem (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 172 ms] (20) CdtProblem (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 168 ms] (22) CdtProblem (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 120 ms] (24) CdtProblem (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 126 ms] (26) CdtProblem (27) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (28) BOUNDS(1, 1) (29) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (30) TRS for Loop Detection (31) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (32) BEST (33) proven lower bound (34) LowerBoundPropagationProof [FINISHED, 0 ms] (35) BOUNDS(n^1, INF) (36) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (7) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) encode_a__f(z0) -> a__f(encArg(z0)) encode_f(z0) -> f(encArg(z0)) encode_a__c(z0) -> a__c(encArg(z0)) encode_g(z0) -> g(encArg(z0)) encode_d(z0) -> d(encArg(z0)) encode_a__h(z0) -> a__h(encArg(z0)) encode_mark(z0) -> mark(encArg(z0)) encode_c(z0) -> c(encArg(z0)) encode_h(z0) -> h(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) ENCODE_A__F(z0) -> c10(A__F(encArg(z0)), ENCARG(z0)) ENCODE_F(z0) -> c11(ENCARG(z0)) ENCODE_A__C(z0) -> c12(A__C(encArg(z0)), ENCARG(z0)) ENCODE_G(z0) -> c13(ENCARG(z0)) ENCODE_D(z0) -> c14(ENCARG(z0)) ENCODE_A__H(z0) -> c15(A__H(encArg(z0)), ENCARG(z0)) ENCODE_MARK(z0) -> c16(MARK(encArg(z0)), ENCARG(z0)) ENCODE_C(z0) -> c17(ENCARG(z0)) ENCODE_H(z0) -> c18(ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 K tuples:none Defined Rule Symbols: a__f_1, a__c_1, a__h_1, mark_1, encArg_1, encode_a__f_1, encode_f_1, encode_a__c_1, encode_g_1, encode_d_1, encode_a__h_1, encode_mark_1, encode_c_1, encode_h_1 Defined Pair Symbols: ENCARG_1, ENCODE_A__F_1, ENCODE_F_1, ENCODE_A__C_1, ENCODE_G_1, ENCODE_D_1, ENCODE_A__H_1, ENCODE_MARK_1, ENCODE_C_1, ENCODE_H_1, A__F_1, A__C_1, A__H_1, MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c10_2, c11_1, c12_2, c13_1, c14_1, c15_2, c16_2, c17_1, c18_1, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29 ---------------------------------------- (9) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 5 leading nodes: ENCODE_F(z0) -> c11(ENCARG(z0)) ENCODE_G(z0) -> c13(ENCARG(z0)) ENCODE_D(z0) -> c14(ENCARG(z0)) ENCODE_C(z0) -> c17(ENCARG(z0)) ENCODE_H(z0) -> c18(ENCARG(z0)) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) encode_a__f(z0) -> a__f(encArg(z0)) encode_f(z0) -> f(encArg(z0)) encode_a__c(z0) -> a__c(encArg(z0)) encode_g(z0) -> g(encArg(z0)) encode_d(z0) -> d(encArg(z0)) encode_a__h(z0) -> a__h(encArg(z0)) encode_mark(z0) -> mark(encArg(z0)) encode_c(z0) -> c(encArg(z0)) encode_h(z0) -> h(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) ENCODE_A__F(z0) -> c10(A__F(encArg(z0)), ENCARG(z0)) ENCODE_A__C(z0) -> c12(A__C(encArg(z0)), ENCARG(z0)) ENCODE_A__H(z0) -> c15(A__H(encArg(z0)), ENCARG(z0)) ENCODE_MARK(z0) -> c16(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 K tuples:none Defined Rule Symbols: a__f_1, a__c_1, a__h_1, mark_1, encArg_1, encode_a__f_1, encode_f_1, encode_a__c_1, encode_g_1, encode_d_1, encode_a__h_1, encode_mark_1, encode_c_1, encode_h_1 Defined Pair Symbols: ENCARG_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1, A__F_1, A__C_1, A__H_1, MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c10_2, c12_2, c15_2, c16_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29 ---------------------------------------- (11) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) encode_a__f(z0) -> a__f(encArg(z0)) encode_f(z0) -> f(encArg(z0)) encode_a__c(z0) -> a__c(encArg(z0)) encode_g(z0) -> g(encArg(z0)) encode_d(z0) -> d(encArg(z0)) encode_a__h(z0) -> a__h(encArg(z0)) encode_mark(z0) -> mark(encArg(z0)) encode_c(z0) -> c(encArg(z0)) encode_h(z0) -> h(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__F(z0) -> c11(ENCARG(z0)) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__C(z0) -> c11(ENCARG(z0)) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_A__H(z0) -> c11(ENCARG(z0)) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) ENCODE_MARK(z0) -> c11(ENCARG(z0)) S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 K tuples:none Defined Rule Symbols: a__f_1, a__c_1, a__h_1, mark_1, encArg_1, encode_a__f_1, encode_f_1, encode_a__c_1, encode_g_1, encode_d_1, encode_a__h_1, encode_mark_1, encode_c_1, encode_h_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (13) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 4 leading nodes: ENCODE_A__F(z0) -> c11(ENCARG(z0)) ENCODE_A__C(z0) -> c11(ENCARG(z0)) ENCODE_A__H(z0) -> c11(ENCARG(z0)) ENCODE_MARK(z0) -> c11(ENCARG(z0)) ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) encode_a__f(z0) -> a__f(encArg(z0)) encode_f(z0) -> f(encArg(z0)) encode_a__c(z0) -> a__c(encArg(z0)) encode_g(z0) -> g(encArg(z0)) encode_d(z0) -> d(encArg(z0)) encode_a__h(z0) -> a__h(encArg(z0)) encode_mark(z0) -> mark(encArg(z0)) encode_c(z0) -> c(encArg(z0)) encode_h(z0) -> h(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 K tuples:none Defined Rule Symbols: a__f_1, a__c_1, a__h_1, mark_1, encArg_1, encode_a__f_1, encode_f_1, encode_a__c_1, encode_g_1, encode_d_1, encode_a__h_1, encode_mark_1, encode_c_1, encode_h_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: encode_a__f(z0) -> a__f(encArg(z0)) encode_f(z0) -> f(encArg(z0)) encode_a__c(z0) -> a__c(encArg(z0)) encode_g(z0) -> g(encArg(z0)) encode_d(z0) -> d(encArg(z0)) encode_a__h(z0) -> a__h(encArg(z0)) encode_mark(z0) -> mark(encArg(z0)) encode_c(z0) -> c(encArg(z0)) encode_h(z0) -> h(encArg(z0)) ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 K tuples:none Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_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. MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 We considered the (Usable) Rules:none And the Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = 0 POL(A__F(x_1)) = 0 POL(A__H(x_1)) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_A__C(x_1)) = 0 POL(ENCODE_A__F(x_1)) = 0 POL(ENCODE_A__H(x_1)) = 0 POL(ENCODE_MARK(x_1)) = [1] POL(MARK(x_1)) = [1] POL(a__c(x_1)) = [1] + x_1 POL(a__f(x_1)) = [1] POL(a__h(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20) = 0 POL(c21) = 0 POL(c22) = 0 POL(c23(x_1)) = x_1 POL(c24) = 0 POL(c25(x_1, x_2)) = x_1 + x_2 POL(c26(x_1)) = x_1 POL(c27(x_1, x_2)) = x_1 + x_2 POL(c28) = 0 POL(c29) = 0 POL(c3(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1, x_2)) = x_1 + x_2 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = [1] + x_1 POL(cons_a__f(x_1)) = [1] + x_1 POL(cons_a__h(x_1)) = [1] + x_1 POL(cons_mark(x_1)) = [1] + x_1 POL(d(x_1)) = [1] + x_1 POL(encArg(x_1)) = [1] + x_1 POL(f(x_1)) = x_1 POL(g(x_1)) = [1] + x_1 POL(h(x_1)) = x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 We considered the (Usable) Rules: encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) mark(d(z0)) -> d(z0) encArg(h(z0)) -> h(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) mark(h(z0)) -> a__h(mark(z0)) mark(c(z0)) -> a__c(z0) encArg(g(z0)) -> g(encArg(z0)) mark(g(z0)) -> g(z0) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__c(z0) -> c(z0) a__c(z0) -> d(z0) a__f(z0) -> f(z0) a__h(z0) -> a__c(d(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) mark(f(z0)) -> a__f(mark(z0)) a__h(z0) -> h(z0) encArg(f(z0)) -> f(encArg(z0)) And the Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = 0 POL(A__F(x_1)) = [2] POL(A__H(x_1)) = 0 POL(ENCARG(x_1)) = [2]x_1^2 POL(ENCODE_A__C(x_1)) = [2] + [2]x_1^2 POL(ENCODE_A__F(x_1)) = [2] + [2]x_1 + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [1] + x_1 + [2]x_1^2 POL(ENCODE_MARK(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(MARK(x_1)) = x_1 POL(a__c(x_1)) = x_1 POL(a__f(x_1)) = [2] + x_1 POL(a__h(x_1)) = x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20) = 0 POL(c21) = 0 POL(c22) = 0 POL(c23(x_1)) = x_1 POL(c24) = 0 POL(c25(x_1, x_2)) = x_1 + x_2 POL(c26(x_1)) = x_1 POL(c27(x_1, x_2)) = x_1 + x_2 POL(c28) = 0 POL(c29) = 0 POL(c3(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1, x_2)) = x_1 + x_2 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = x_1 POL(cons_a__f(x_1)) = [2] + x_1 POL(cons_a__h(x_1)) = x_1 POL(cons_mark(x_1)) = [2] + x_1 POL(d(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1)) = [2] + x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (20) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) We considered the (Usable) Rules: encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) mark(d(z0)) -> d(z0) encArg(h(z0)) -> h(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) mark(h(z0)) -> a__h(mark(z0)) mark(c(z0)) -> a__c(z0) encArg(g(z0)) -> g(encArg(z0)) mark(g(z0)) -> g(z0) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__c(z0) -> c(z0) a__c(z0) -> d(z0) a__f(z0) -> f(z0) a__h(z0) -> a__c(d(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) mark(f(z0)) -> a__f(mark(z0)) a__h(z0) -> h(z0) encArg(f(z0)) -> f(encArg(z0)) And the Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = 0 POL(A__F(x_1)) = 0 POL(A__H(x_1)) = [1] POL(ENCARG(x_1)) = x_1^2 POL(ENCODE_A__C(x_1)) = [1] + x_1^2 POL(ENCODE_A__F(x_1)) = [2] + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(ENCODE_MARK(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(MARK(x_1)) = [2]x_1 POL(a__c(x_1)) = x_1 POL(a__f(x_1)) = x_1 POL(a__h(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20) = 0 POL(c21) = 0 POL(c22) = 0 POL(c23(x_1)) = x_1 POL(c24) = 0 POL(c25(x_1, x_2)) = x_1 + x_2 POL(c26(x_1)) = x_1 POL(c27(x_1, x_2)) = x_1 + x_2 POL(c28) = 0 POL(c29) = 0 POL(c3(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1, x_2)) = x_1 + x_2 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = x_1 POL(cons_a__f(x_1)) = x_1 POL(cons_a__h(x_1)) = [2] + x_1 POL(cons_mark(x_1)) = [1] + x_1 POL(d(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1)) = x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = [1] + x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (22) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: A__C(z0) -> c21 A__C(z0) -> c22 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. A__C(z0) -> c21 A__C(z0) -> c22 We considered the (Usable) Rules: encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) mark(d(z0)) -> d(z0) encArg(h(z0)) -> h(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) mark(h(z0)) -> a__h(mark(z0)) mark(c(z0)) -> a__c(z0) encArg(g(z0)) -> g(encArg(z0)) mark(g(z0)) -> g(z0) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__c(z0) -> c(z0) a__c(z0) -> d(z0) a__f(z0) -> f(z0) a__h(z0) -> a__c(d(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) mark(f(z0)) -> a__f(mark(z0)) a__h(z0) -> h(z0) encArg(f(z0)) -> f(encArg(z0)) And the Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = [1] POL(A__F(x_1)) = [2] POL(A__H(x_1)) = [1] POL(ENCARG(x_1)) = [2]x_1^2 POL(ENCODE_A__C(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(ENCODE_A__F(x_1)) = [2] + x_1 + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [1] + [2]x_1 + x_1^2 POL(ENCODE_MARK(x_1)) = [1] + [2]x_1 + x_1^2 POL(MARK(x_1)) = [1] + x_1 POL(a__c(x_1)) = x_1 POL(a__f(x_1)) = [2] + x_1 POL(a__h(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20) = 0 POL(c21) = 0 POL(c22) = 0 POL(c23(x_1)) = x_1 POL(c24) = 0 POL(c25(x_1, x_2)) = x_1 + x_2 POL(c26(x_1)) = x_1 POL(c27(x_1, x_2)) = x_1 + x_2 POL(c28) = 0 POL(c29) = 0 POL(c3(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1, x_2)) = x_1 + x_2 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = [1] + x_1 POL(cons_a__f(x_1)) = [2] + x_1 POL(cons_a__h(x_1)) = [2] + x_1 POL(cons_mark(x_1)) = [2] + x_1 POL(d(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1)) = [2] + x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = [1] + x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (24) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples: MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) A__C(z0) -> c21 A__C(z0) -> c22 Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (25) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) We considered the (Usable) Rules: encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) mark(d(z0)) -> d(z0) encArg(h(z0)) -> h(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) mark(h(z0)) -> a__h(mark(z0)) mark(c(z0)) -> a__c(z0) encArg(g(z0)) -> g(encArg(z0)) mark(g(z0)) -> g(z0) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__c(z0) -> c(z0) a__c(z0) -> d(z0) a__f(z0) -> f(z0) a__h(z0) -> a__c(d(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) mark(f(z0)) -> a__f(mark(z0)) a__h(z0) -> h(z0) encArg(f(z0)) -> f(encArg(z0)) And the Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = 0 POL(A__F(x_1)) = 0 POL(A__H(x_1)) = 0 POL(ENCARG(x_1)) = [2]x_1^2 POL(ENCODE_A__C(x_1)) = [2] + [2]x_1 + [2]x_1^2 POL(ENCODE_A__F(x_1)) = [2] + [2]x_1 + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(ENCODE_MARK(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(MARK(x_1)) = x_1 POL(a__c(x_1)) = x_1 POL(a__f(x_1)) = [1] + x_1 POL(a__h(x_1)) = x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20) = 0 POL(c21) = 0 POL(c22) = 0 POL(c23(x_1)) = x_1 POL(c24) = 0 POL(c25(x_1, x_2)) = x_1 + x_2 POL(c26(x_1)) = x_1 POL(c27(x_1, x_2)) = x_1 + x_2 POL(c28) = 0 POL(c29) = 0 POL(c3(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1, x_2)) = x_1 + x_2 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = [1] + x_1 POL(cons_a__f(x_1)) = [2] + x_1 POL(cons_a__h(x_1)) = x_1 POL(cons_mark(x_1)) = [2] + x_1 POL(d(x_1)) = x_1 POL(encArg(x_1)) = [1] + x_1 POL(f(x_1)) = [1] + x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (26) Obligation: Complexity Dependency Tuples Problem Rules: encArg(f(z0)) -> f(encArg(z0)) encArg(g(z0)) -> g(encArg(z0)) encArg(d(z0)) -> d(encArg(z0)) encArg(c(z0)) -> c(encArg(z0)) encArg(h(z0)) -> h(encArg(z0)) encArg(cons_a__f(z0)) -> a__f(encArg(z0)) encArg(cons_a__c(z0)) -> a__c(encArg(z0)) encArg(cons_a__h(z0)) -> a__h(encArg(z0)) encArg(cons_mark(z0)) -> mark(encArg(z0)) a__f(f(z0)) -> a__c(f(g(f(z0)))) a__f(z0) -> f(z0) a__c(z0) -> d(z0) a__c(z0) -> c(z0) a__h(z0) -> a__c(d(z0)) a__h(z0) -> h(z0) mark(f(z0)) -> a__f(mark(z0)) mark(c(z0)) -> a__c(z0) mark(h(z0)) -> a__h(mark(z0)) mark(g(z0)) -> g(z0) mark(d(z0)) -> d(z0) Tuples: ENCARG(f(z0)) -> c1(ENCARG(z0)) ENCARG(g(z0)) -> c2(ENCARG(z0)) ENCARG(d(z0)) -> c3(ENCARG(z0)) ENCARG(c(z0)) -> c4(ENCARG(z0)) ENCARG(h(z0)) -> c5(ENCARG(z0)) ENCARG(cons_a__f(z0)) -> c6(A__F(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__c(z0)) -> c7(A__C(encArg(z0)), ENCARG(z0)) ENCARG(cons_a__h(z0)) -> c8(A__H(encArg(z0)), ENCARG(z0)) ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ENCODE_A__F(z0) -> c11(A__F(encArg(z0))) ENCODE_A__C(z0) -> c11(A__C(encArg(z0))) ENCODE_A__H(z0) -> c11(A__H(encArg(z0))) ENCODE_MARK(z0) -> c11(MARK(encArg(z0))) S tuples:none K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 A__F(f(z0)) -> c19(A__C(f(g(f(z0))))) A__F(z0) -> c20 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) A__C(z0) -> c21 A__C(z0) -> c22 MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) Defined Rule Symbols: encArg_1, a__f_1, a__c_1, a__h_1, mark_1 Defined Pair Symbols: ENCARG_1, A__F_1, A__C_1, A__H_1, MARK_1, ENCODE_A__F_1, ENCODE_A__C_1, ENCODE_A__H_1, ENCODE_MARK_1 Compound Symbols: c1_1, c2_1, c3_1, c4_1, c5_1, c6_2, c7_2, c8_2, c9_2, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1 ---------------------------------------- (27) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (28) BOUNDS(1, 1) ---------------------------------------- (29) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (30) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (31) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence mark(f(X)) ->^+ a__f(mark(X)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [X / f(X)]. The result substitution is [ ]. ---------------------------------------- (32) Complex Obligation (BEST) ---------------------------------------- (33) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (34) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (35) BOUNDS(n^1, INF) ---------------------------------------- (36) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: a__f(f(X)) -> a__c(f(g(f(X)))) a__c(X) -> d(X) a__h(X) -> a__c(d(X)) mark(f(X)) -> a__f(mark(X)) mark(c(X)) -> a__c(X) mark(h(X)) -> a__h(mark(X)) mark(g(X)) -> g(X) mark(d(X)) -> d(X) a__f(X) -> f(X) a__c(X) -> c(X) a__h(X) -> h(X) The (relative) TRS S consists of the following rules: encArg(f(x_1)) -> f(encArg(x_1)) encArg(g(x_1)) -> g(encArg(x_1)) encArg(d(x_1)) -> d(encArg(x_1)) encArg(c(x_1)) -> c(encArg(x_1)) encArg(h(x_1)) -> h(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__c(x_1)) -> a__c(encArg(x_1)) encArg(cons_a__h(x_1)) -> a__h(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_a__c(x_1) -> a__c(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_d(x_1) -> d(encArg(x_1)) encode_a__h(x_1) -> a__h(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_c(x_1) -> c(encArg(x_1)) encode_h(x_1) -> h(encArg(x_1)) Rewrite Strategy: FULL