/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), 195 ms] (4) CpxRelTRS (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (6) CdtProblem (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (8) CdtProblem (9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 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), 16 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 483 ms] (18) CdtProblem (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 373 ms] (20) CdtProblem (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 412 ms] (22) CdtProblem (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 319 ms] (24) CdtProblem (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 215 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), 37 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 (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) 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(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) ---------------------------------------- (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: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) The (relative) TRS S consists of the following rules: encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) 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: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) The (relative) TRS S consists of the following rules: encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(true) -> c1 ENCARG(false) -> c2 ENCARG(nil) -> c3 ENCARG(u) -> c4 ENCARG(v) -> c5 ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_DEL(z0) -> c10(DEL(encArg(z0)), ENCARG(z0)) ENCODE_.(z0, z1) -> c11(ENCARG(z0), ENCARG(z1)) ENCODE_F(z0, z1, z2, z3) -> c12(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCODE_=(z0, z1) -> c13(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_TRUE -> c14 ENCODE_FALSE -> c15 ENCODE_NIL -> c16 ENCODE_U -> c17 ENCODE_V -> c18 ENCODE_AND(z0, z1) -> c19(ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26(='(z0, u), ='(z1, v)) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26(='(z0, u), ='(z1, v)) K tuples:none Defined Rule Symbols: del_1, f_4, =_2, encArg_1, encode_del_1, encode_._2, encode_f_4, encode_=_2, encode_true, encode_false, encode_nil, encode_u, encode_v, encode_and_2 Defined Pair Symbols: ENCARG_1, ENCODE_DEL_1, ENCODE_._2, ENCODE_F_4, ENCODE_=_2, ENCODE_TRUE, ENCODE_FALSE, ENCODE_NIL, ENCODE_U, ENCODE_V, ENCODE_AND_2, DEL_1, F_4, ='_2 Compound Symbols: c_2, c1, c2, c3, c4, c5, c6_2, c7_2, c8_5, c9_3, c10_2, c11_2, c12_5, c13_3, c14, c15, c16, c17, c18, c19_2, c20_2, c21_1, c22_1, c23, c24, c25, c26_2 ---------------------------------------- (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 2 leading nodes: ENCODE_.(z0, z1) -> c11(ENCARG(z0), ENCARG(z1)) ENCODE_AND(z0, z1) -> c19(ENCARG(z0), ENCARG(z1)) Removed 10 trailing nodes: ENCARG(v) -> c5 ENCARG(u) -> c4 ENCARG(false) -> c2 ENCODE_TRUE -> c14 ENCARG(nil) -> c3 ENCODE_U -> c17 ENCODE_V -> c18 ENCODE_NIL -> c16 ENCODE_FALSE -> c15 ENCARG(true) -> c1 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_DEL(z0) -> c10(DEL(encArg(z0)), ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c12(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCODE_=(z0, z1) -> c13(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26(='(z0, u), ='(z1, v)) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26(='(z0, u), ='(z1, v)) K tuples:none Defined Rule Symbols: del_1, f_4, =_2, encArg_1, encode_del_1, encode_._2, encode_f_4, encode_=_2, encode_true, encode_false, encode_nil, encode_u, encode_v, encode_and_2 Defined Pair Symbols: ENCARG_1, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2, DEL_1, F_4, ='_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c10_2, c12_5, c13_3, c20_2, c21_1, c22_1, c23, c24, c25, c26_2 ---------------------------------------- (9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing tuple parts ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_DEL(z0) -> c10(DEL(encArg(z0)), ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c12(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCODE_=(z0, z1) -> c13(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 K tuples:none Defined Rule Symbols: del_1, f_4, =_2, encArg_1, encode_del_1, encode_._2, encode_f_4, encode_=_2, encode_true, encode_false, encode_nil, encode_u, encode_v, encode_and_2 Defined Pair Symbols: ENCARG_1, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2, DEL_1, F_4, ='_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c10_2, c12_5, c13_3, c20_2, c21_1, c22_1, c23, c24, c25, c26 ---------------------------------------- (11) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_DEL(z0) -> c1(ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z1)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z2)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z3)) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) ENCODE_=(z0, z1) -> c1(ENCARG(z0)) ENCODE_=(z0, z1) -> c1(ENCARG(z1)) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 K tuples:none Defined Rule Symbols: del_1, f_4, =_2, encArg_1, encode_del_1, encode_._2, encode_f_4, encode_=_2, encode_true, encode_false, encode_nil, encode_u, encode_v, encode_and_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_1 ---------------------------------------- (13) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 7 leading nodes: ENCODE_DEL(z0) -> c1(ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z0)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z1)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z2)) ENCODE_F(z0, z1, z2, z3) -> c1(ENCARG(z3)) ENCODE_=(z0, z1) -> c1(ENCARG(z0)) ENCODE_=(z0, z1) -> c1(ENCARG(z1)) ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 K tuples:none Defined Rule Symbols: del_1, f_4, =_2, encArg_1, encode_del_1, encode_._2, encode_f_4, encode_=_2, encode_true, encode_false, encode_nil, encode_u, encode_v, encode_and_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_1 ---------------------------------------- (15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: encode_del(z0) -> del(encArg(z0)) encode_.(z0, z1) -> .(encArg(z0), encArg(z1)) encode_f(z0, z1, z2, z3) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encode_=(z0, z1) -> =(encArg(z0), encArg(z1)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(z0, z1) -> and(encArg(z0), encArg(z1)) ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 K tuples:none Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_1 ---------------------------------------- (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 We considered the (Usable) Rules: encArg(nil) -> nil =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(true) -> true encArg(v) -> v =(nil, nil) -> true encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) encArg(false) -> false encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(u) -> u encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) f(true, z0, z1, z2) -> del(.(z1, z2)) And the Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = x_1 + x_2 POL(=(x_1, x_2)) = 0 POL(='(x_1, x_2)) = x_1 POL(DEL(x_1)) = x_1 POL(ENCARG(x_1)) = [2]x_1^2 POL(ENCODE_=(x_1, x_2)) = [2] + [2]x_1 + x_2^2 + [2]x_1*x_2 + [2]x_1^2 POL(ENCODE_DEL(x_1)) = [1] + [2]x_1 + x_1^2 POL(ENCODE_F(x_1, x_2, x_3, x_4)) = [2] + x_1 + [2]x_2 + [2]x_3 + [2]x_4 + [2]x_4^2 + [2]x_3*x_4 + [2]x_2*x_4 + [2]x_1*x_4 + [2]x_1^2 + [2]x_1*x_2 + [2]x_1*x_3 + [2]x_3^2 + [2]x_2*x_3 + [2]x_2^2 POL(F(x_1, x_2, x_3, x_4)) = x_3 + x_4 POL(and(x_1, x_2)) = x_1 + x_2 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c20(x_1, x_2)) = x_1 + x_2 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23) = 0 POL(c24) = 0 POL(c25) = 0 POL(c26) = 0 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_3, x_4, x_5)) = x_1 + x_2 + x_3 + x_4 + x_5 POL(c9(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_=(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_del(x_1)) = [2] + x_1 POL(cons_f(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4 POL(del(x_1)) = x_1 POL(encArg(x_1)) = [2]x_1 POL(f(x_1, x_2, x_3, x_4)) = x_2 + x_3 + x_4 POL(false) = 0 POL(nil) = [2] POL(true) = 0 POL(u) = 0 POL(v) = 0 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 K tuples: ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_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. F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) We considered the (Usable) Rules: encArg(nil) -> nil =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(true) -> true encArg(v) -> v =(nil, nil) -> true encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) encArg(false) -> false encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(u) -> u encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) f(true, z0, z1, z2) -> del(.(z1, z2)) And the Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = x_1 + x_2 POL(=(x_1, x_2)) = x_1 POL(='(x_1, x_2)) = 0 POL(DEL(x_1)) = x_1 POL(ENCARG(x_1)) = x_1^2 POL(ENCODE_=(x_1, x_2)) = [2] + [2]x_2 + x_2^2 + [2]x_1*x_2 + [2]x_1^2 POL(ENCODE_DEL(x_1)) = [2] + x_1 + [2]x_1^2 POL(ENCODE_F(x_1, x_2, x_3, x_4)) = [1] + [2]x_1 + x_2 + [2]x_3 + [2]x_4 + x_4^2 + [2]x_3*x_4 + [2]x_2*x_4 + x_1*x_4 + [2]x_1^2 + x_1*x_2 + [2]x_1*x_3 + [2]x_3^2 + [2]x_2*x_3 + [2]x_2^2 POL(F(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4 POL(and(x_1, x_2)) = x_1 + x_2 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c20(x_1, x_2)) = x_1 + x_2 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23) = 0 POL(c24) = 0 POL(c25) = 0 POL(c26) = 0 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_3, x_4, x_5)) = x_1 + x_2 + x_3 + x_4 + x_5 POL(c9(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_=(x_1, x_2)) = x_1 + x_2 POL(cons_del(x_1)) = [2] + x_1 POL(cons_f(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4 POL(del(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1, x_2, x_3, x_4)) = x_2 + x_3 + x_4 POL(false) = 0 POL(nil) = [2] POL(true) = [1] POL(u) = 0 POL(v) = 0 ---------------------------------------- (20) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 K tuples: ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_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. DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) We considered the (Usable) Rules: encArg(nil) -> nil =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(true) -> true encArg(v) -> v =(nil, nil) -> true encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) encArg(false) -> false encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(u) -> u encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) f(true, z0, z1, z2) -> del(.(z1, z2)) And the Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = [1] + x_1 + x_2 POL(=(x_1, x_2)) = 0 POL(='(x_1, x_2)) = 0 POL(DEL(x_1)) = [2]x_1 POL(ENCARG(x_1)) = [2]x_1^2 POL(ENCODE_=(x_1, x_2)) = [1] + [2]x_1 + [2]x_2 + [2]x_2^2 + [2]x_1*x_2 + [2]x_1^2 POL(ENCODE_DEL(x_1)) = [1] + [2]x_1 + [2]x_1^2 POL(ENCODE_F(x_1, x_2, x_3, x_4)) = [2] + [2]x_1 + [2]x_2 + [2]x_3 + [2]x_4 + [2]x_4^2 + [2]x_3*x_4 + [2]x_2*x_4 + [2]x_1*x_4 + [2]x_1^2 + [2]x_1*x_2 + [2]x_1*x_3 + [2]x_3^2 + x_2*x_3 + [2]x_2^2 POL(F(x_1, x_2, x_3, x_4)) = [2] + [2]x_3 + [2]x_4 POL(and(x_1, x_2)) = x_1 + x_2 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c20(x_1, x_2)) = x_1 + x_2 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23) = 0 POL(c24) = 0 POL(c25) = 0 POL(c26) = 0 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_3, x_4, x_5)) = x_1 + x_2 + x_3 + x_4 + x_5 POL(c9(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_=(x_1, x_2)) = x_1 + x_2 POL(cons_del(x_1)) = [2] + x_1 POL(cons_f(x_1, x_2, x_3, x_4)) = [2] + x_1 + x_2 + x_3 + x_4 POL(del(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1, x_2, x_3, x_4)) = [2] + x_2 + x_3 + x_4 POL(false) = 0 POL(nil) = 0 POL(true) = 0 POL(u) = 0 POL(v) = 0 ---------------------------------------- (22) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 K tuples: ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_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. ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 We considered the (Usable) Rules: encArg(nil) -> nil =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(true) -> true encArg(v) -> v =(nil, nil) -> true encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) encArg(false) -> false encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(u) -> u encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) f(true, z0, z1, z2) -> del(.(z1, z2)) And the Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = [1] + x_1 + x_2 POL(=(x_1, x_2)) = 0 POL(='(x_1, x_2)) = [1] POL(DEL(x_1)) = x_1 POL(ENCARG(x_1)) = x_1^2 POL(ENCODE_=(x_1, x_2)) = [2] + [2]x_1 + [2]x_2 + [2]x_2^2 + [2]x_1*x_2 + [2]x_1^2 POL(ENCODE_DEL(x_1)) = [1] + [2]x_1 + x_1^2 POL(ENCODE_F(x_1, x_2, x_3, x_4)) = [1] + x_1 + [2]x_2 + [2]x_3 + [2]x_4 + [2]x_4^2 + [2]x_3*x_4 + [2]x_2*x_4 + [2]x_1*x_4 + [2]x_1^2 + [2]x_1*x_2 + [2]x_1*x_3 + [2]x_3^2 + [2]x_2*x_3 + [2]x_2^2 POL(F(x_1, x_2, x_3, x_4)) = [1] + x_2 + x_3 + x_4 POL(and(x_1, x_2)) = x_1 + x_2 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c20(x_1, x_2)) = x_1 + x_2 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23) = 0 POL(c24) = 0 POL(c25) = 0 POL(c26) = 0 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_3, x_4, x_5)) = x_1 + x_2 + x_3 + x_4 + x_5 POL(c9(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_=(x_1, x_2)) = [2] + x_1 + x_2 POL(cons_del(x_1)) = [2] + x_1 POL(cons_f(x_1, x_2, x_3, x_4)) = [2] + x_1 + x_2 + x_3 + x_4 POL(del(x_1)) = x_1 POL(encArg(x_1)) = x_1 POL(f(x_1, x_2, x_3, x_4)) = [2] + x_2 + x_3 + x_4 POL(false) = 0 POL(nil) = 0 POL(true) = 0 POL(u) = 0 POL(v) = 0 ---------------------------------------- (24) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples: F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) K tuples: ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_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. F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) We considered the (Usable) Rules: encArg(nil) -> nil =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(true) -> true encArg(v) -> v =(nil, nil) -> true encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) encArg(false) -> false encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(u) -> u encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) f(true, z0, z1, z2) -> del(.(z1, z2)) And the Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = [1] + x_1 + x_2 POL(=(x_1, x_2)) = 0 POL(='(x_1, x_2)) = 0 POL(DEL(x_1)) = x_1 POL(ENCARG(x_1)) = x_1^2 POL(ENCODE_=(x_1, x_2)) = [2] + [2]x_2 + [2]x_2^2 + [2]x_1*x_2 + [2]x_1^2 POL(ENCODE_DEL(x_1)) = [2] + [2]x_1 + [2]x_1^2 POL(ENCODE_F(x_1, x_2, x_3, x_4)) = [2] + [2]x_1 + [2]x_2 + [2]x_3 + [2]x_4 + x_4^2 + [2]x_3*x_4 + [2]x_2*x_4 + [2]x_1*x_4 + x_1^2 + x_1*x_2 + [2]x_1*x_3 + [2]x_3^2 + x_2*x_3 + x_2^2 POL(F(x_1, x_2, x_3, x_4)) = [2] + x_3 + x_4 POL(and(x_1, x_2)) = x_1 + x_2 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c20(x_1, x_2)) = x_1 + x_2 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23) = 0 POL(c24) = 0 POL(c25) = 0 POL(c26) = 0 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_3, x_4, x_5)) = x_1 + x_2 + x_3 + x_4 + x_5 POL(c9(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_=(x_1, x_2)) = x_1 + x_2 POL(cons_del(x_1)) = [2] + x_1 POL(cons_f(x_1, x_2, x_3, x_4)) = [2] + x_1 + x_2 + x_3 + x_4 POL(del(x_1)) = x_1 POL(encArg(x_1)) = [2]x_1 POL(f(x_1, x_2, x_3, x_4)) = [2] + x_2 + x_3 + x_4 POL(false) = 0 POL(nil) = 0 POL(true) = 0 POL(u) = 0 POL(v) = 0 ---------------------------------------- (26) Obligation: Complexity Dependency Tuples Problem Rules: encArg(.(z0, z1)) -> .(encArg(z0), encArg(z1)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(z0, z1)) -> and(encArg(z0), encArg(z1)) encArg(cons_del(z0)) -> del(encArg(z0)) encArg(cons_f(z0, z1, z2, z3)) -> f(encArg(z0), encArg(z1), encArg(z2), encArg(z3)) encArg(cons_=(z0, z1)) -> =(encArg(z0), encArg(z1)) del(.(z0, .(z1, z2))) -> f(=(z0, z1), z0, z1, z2) f(true, z0, z1, z2) -> del(.(z1, z2)) f(false, z0, z1, z2) -> .(z0, del(.(z1, z2))) =(nil, nil) -> true =(.(z0, z1), nil) -> false =(nil, .(z0, z1)) -> false =(.(z0, z1), .(u, v)) -> and(=(z0, u), =(z1, v)) Tuples: ENCARG(.(z0, z1)) -> c(ENCARG(z0), ENCARG(z1)) ENCARG(and(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(cons_del(z0)) -> c7(DEL(encArg(z0)), ENCARG(z0)) ENCARG(cons_f(z0, z1, z2, z3)) -> c8(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3)), ENCARG(z0), ENCARG(z1), ENCARG(z2), ENCARG(z3)) ENCARG(cons_=(z0, z1)) -> c9(='(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) ='(nil, nil) -> c23 ='(.(z0, z1), nil) -> c24 ='(nil, .(z0, z1)) -> c25 ='(.(z0, z1), .(u, v)) -> c26 ENCODE_DEL(z0) -> c1(DEL(encArg(z0))) ENCODE_F(z0, z1, z2, z3) -> c1(F(encArg(z0), encArg(z1), encArg(z2), encArg(z3))) ENCODE_=(z0, z1) -> c1(='(encArg(z0), encArg(z1))) S tuples:none K tuples: ='(nil, nil) -> c23 ='(nil, .(z0, z1)) -> c25 F(true, z0, z1, z2) -> c21(DEL(.(z1, z2))) DEL(.(z0, .(z1, z2))) -> c20(F(=(z0, z1), z0, z1, z2), ='(z0, z1)) ='(.(z0, z1), nil) -> c24 ='(.(z0, z1), .(u, v)) -> c26 F(false, z0, z1, z2) -> c22(DEL(.(z1, z2))) Defined Rule Symbols: encArg_1, del_1, f_4, =_2 Defined Pair Symbols: ENCARG_1, DEL_1, F_4, ='_2, ENCODE_DEL_1, ENCODE_F_4, ENCODE_=_2 Compound Symbols: c_2, c6_2, c7_2, c8_5, c9_3, c20_2, c21_1, c22_1, c23, c24, c25, c26, c1_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 (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) The (relative) TRS S consists of the following rules: encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (31) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence f(true, x, nil, .(nil, z3_0)) ->^+ f(true, nil, nil, z3_0) gives rise to a decreasing loop by considering the right hand sides subterm at position []. The pumping substitution is [z3_0 / .(nil, z3_0)]. The result substitution is [x / nil]. ---------------------------------------- (32) Complex Obligation (BEST) ---------------------------------------- (33) 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: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) The (relative) TRS S consists of the following rules: encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (34) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (35) BOUNDS(n^1, INF) ---------------------------------------- (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: del(.(x, .(y, z))) -> f(=(x, y), x, y, z) f(true, x, y, z) -> del(.(y, z)) f(false, x, y, z) -> .(x, del(.(y, z))) =(nil, nil) -> true =(.(x, y), nil) -> false =(nil, .(y, z)) -> false =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) The (relative) TRS S consists of the following rules: encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(nil) -> nil encArg(u) -> u encArg(v) -> v encArg(and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_del(x_1)) -> del(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3, x_4)) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encArg(cons_=(x_1, x_2)) -> =(encArg(x_1), encArg(x_2)) encode_del(x_1) -> del(encArg(x_1)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3, x_4) -> f(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_=(x_1, x_2) -> =(encArg(x_1), encArg(x_2)) encode_true -> true encode_false -> false encode_nil -> nil encode_u -> u encode_v -> v encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST