/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- 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 (innermost) 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), 57 ms] (4) CpxRelTRS (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (6) CdtProblem (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (8) CdtProblem (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (12) CdtProblem (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 172 ms] (16) CdtProblem (17) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CdtProblem (19) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (20) CdtProblem (21) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (22) CdtProblem (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 336 ms] (24) CdtProblem (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 316 ms] (26) CdtProblem (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 342 ms] (28) CdtProblem (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 278 ms] (30) CdtProblem (31) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 289 ms] (32) CdtProblem (33) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (34) BOUNDS(1, 1) (35) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (36) TRS for Loop Detection (37) DecreasingLoopProof [LOWER BOUND(ID), 4 ms] (38) BEST (39) proven lower bound (40) LowerBoundPropagationProof [FINISHED, 0 ms] (41) BOUNDS(n^1, INF) (42) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) 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: INNERMOST ---------------------------------------- (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 (innermost) 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: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) 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: INNERMOST ---------------------------------------- (5) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (6) 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 ---------------------------------------- (7) 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)) ---------------------------------------- (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_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 ---------------------------------------- (9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (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)) 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 ---------------------------------------- (11) 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)) ---------------------------------------- (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__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 ---------------------------------------- (13) 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)) ---------------------------------------- (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)) 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 ---------------------------------------- (15) 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 ---------------------------------------- (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(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 ---------------------------------------- (17) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace ENCARG(cons_mark(z0)) -> c9(MARK(encArg(z0)), ENCARG(z0)) by ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(g(z0))) -> c9(MARK(g(encArg(z0))), ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(MARK(d(encArg(z0))), ENCARG(d(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ---------------------------------------- (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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(g(z0))) -> c9(MARK(g(encArg(z0))), ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(MARK(d(encArg(z0))), ENCARG(d(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c28, c29, c11_1, c9_2 ---------------------------------------- (19) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing nodes: MARK(g(z0)) -> c28 MARK(d(z0)) -> c29 ---------------------------------------- (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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(g(z0))) -> c9(MARK(g(encArg(z0))), ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(MARK(d(encArg(z0))), ENCARG(d(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(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)) 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2 ---------------------------------------- (21) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing tuple parts ---------------------------------------- (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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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)) 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_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. 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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^2 POL(ENCODE_A__C(x_1)) = [1] + [2]x_1 + x_1^2 POL(ENCODE_A__F(x_1)) = [1] + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [1] + [2]x_1^2 POL(ENCODE_MARK(x_1)) = [2] + [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)) = [2] + 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(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_1 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)) = [2] + 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)) = [2] + 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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)) K tuples: MARK(c(z0)) -> c26(A__C(z0)) 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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] + 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)) = [2] + [2]x_1 + [2]x_1^2 POL(ENCODE_MARK(x_1)) = [2] + [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(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_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = x_1 POL(cons_a__f(x_1)) = [1] + 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)) = [2]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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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 K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_1 ---------------------------------------- (27) 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = 0 POL(A__F(x_1)) = [1] POL(A__H(x_1)) = 0 POL(ENCARG(x_1)) = 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)) = [2] + [2]x_1 + x_1^2 POL(ENCODE_MARK(x_1)) = [2] + [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(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_1 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)) = [2] + [2]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 ---------------------------------------- (28) 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(z0))) S tuples: A__C(z0) -> c21 A__C(z0) -> c22 A__H(z0) -> c23(A__C(d(z0))) A__H(z0) -> c24 K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_1 ---------------------------------------- (29) 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 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(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] + [2]x_1 + [2]x_1^2 POL(ENCODE_A__F(x_1)) = [2] + [2]x_1^2 POL(ENCODE_A__H(x_1)) = [2] + [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)) = 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(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_1 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)) = [2] + 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 ---------------------------------------- (30) 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(z0))) S tuples: A__C(z0) -> c21 A__C(z0) -> c22 K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) 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 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_1 ---------------------------------------- (31) 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(A__C(x_1)) = [1] POL(A__F(x_1)) = [1] 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 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 + x_1^2 POL(MARK(x_1)) = [1] + x_1 POL(a__c(x_1)) = x_1 POL(a__f(x_1)) = [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(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_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons_a__c(x_1)) = [2] + 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)) = [2] + x_1 POL(d(x_1)) = x_1 POL(encArg(x_1)) = [2]x_1 POL(f(x_1)) = [1] + x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = [1] + x_1 POL(mark(x_1)) = x_1 ---------------------------------------- (32) 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)) 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)) 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))) ENCARG(cons_mark(f(z0))) -> c9(MARK(f(encArg(z0))), ENCARG(f(z0))) ENCARG(cons_mark(c(z0))) -> c9(MARK(c(encArg(z0))), ENCARG(c(z0))) ENCARG(cons_mark(h(z0))) -> c9(MARK(h(encArg(z0))), ENCARG(h(z0))) ENCARG(cons_mark(cons_a__f(z0))) -> c9(MARK(a__f(encArg(z0))), ENCARG(cons_a__f(z0))) ENCARG(cons_mark(cons_a__c(z0))) -> c9(MARK(a__c(encArg(z0))), ENCARG(cons_a__c(z0))) ENCARG(cons_mark(cons_a__h(z0))) -> c9(MARK(a__h(encArg(z0))), ENCARG(cons_a__h(z0))) ENCARG(cons_mark(cons_mark(z0))) -> c9(MARK(mark(encArg(z0))), ENCARG(cons_mark(z0))) ENCARG(cons_mark(g(z0))) -> c9(ENCARG(g(z0))) ENCARG(cons_mark(d(z0))) -> c9(ENCARG(d(z0))) S tuples:none K tuples: MARK(c(z0)) -> c26(A__C(z0)) MARK(h(z0)) -> c27(A__H(mark(z0)), MARK(z0)) MARK(f(z0)) -> c25(A__F(mark(z0)), MARK(z0)) 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 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, c19_1, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_2, c11_1, c9_2, c9_1 ---------------------------------------- (33) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (34) BOUNDS(1, 1) ---------------------------------------- (35) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (36) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) 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: INNERMOST ---------------------------------------- (37) 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 [ ]. ---------------------------------------- (38) Complex Obligation (BEST) ---------------------------------------- (39) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) 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: INNERMOST ---------------------------------------- (40) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (41) BOUNDS(n^1, INF) ---------------------------------------- (42) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) 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: INNERMOST