Dynamic Programming Ontology

FLOW ALGEBRA
TITLE: Dynamic Programming Ontology
VERSION: 1.0
DATE: 2026-10-11
SOURCE: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/dynamic-programming-ontology-2.html
AUTHORS: Mark Higgins — Sky (Recursive AI)
PROJECT: Kireth Semantic Library
DOMAIN: Discrete Mathematics > Algorithmic Mathematics > Dynamic Programming

1. PURPOSE
Represent dynamic programming as a typed computational method for solving problems with reusable subproblems, explicit state transitions, and verified solution reconstruction.

2. TYPED ENTITIES
Problem: {input, objective, constraints}
State: {identifier, parameters, validity}
Subproblem: {state, restricted_problem}
Decision: {state, action, feasibility}
Transition: {source_state, decision, target_state, cost_or_reward}
Recurrence: {state, base_cases, transition_operator}
MemoTable: Map[State, Value]
EvaluationOrder: Sequence[State]
Policy: Map[State, Decision]
Solution: {objective_value, selected_decisions, witness}
Proof: {invariant, base_case, induction_step}
Complexity: {state_count, transitions_per_state, time, space}

3. RELATIONSHIP TYPES
DECOMPOSES_INTO(Problem, Subproblem)
REPRESENTED_BY(Subproblem, State)
DEPENDS_ON(State, State)
GENERATES(Decision, Transition)
EVALUATED_BY(State, Recurrence)
STORED_IN(State, MemoTable)
ORDERED_BY(State, EvaluationOrder)
RECONSTRUCTED_FROM(Solution, Policy)
JUSTIFIED_BY(Recurrence, Proof)
BOUNDED_BY(Algorithm, Complexity)

4. CORE SEMANTICS
DP_APPLICABLE(P) requires a finite or otherwise terminating state evaluation and a valid recurrence whose subproblem values can be reused.
OVERLAPPING_SUBPROBLEMS(P) := repeated reachable subproblem states occur in a naive recursive evaluation.
OPTIMAL_SUBSTRUCTURE(P) := an optimal solution can be composed from appropriate optimal subproblem solutions, subject to state capturing all relevant constraints.
OVERLAPPING_SUBPROBLEMS improves potential efficiency but is not a universal logical prerequisite for writing a DP recurrence.

5. GENERAL RECURRENCE
For an optimisation problem with states s and feasible decisions A(s):
V(s) = OPT_{a in A(s)} [w(s,a) + V(T(s,a))]
where OPT is min or max, T is the successor-state function, and terminal states have explicitly defined base values.
The recurrence applies only when costs compose additively; other problems require a different combination operator.

6. EXECUTION MODELS
TOP_DOWN_MEMOIZATION:
  solve(s):
    if terminal(s): return base_value(s)
    if s in memo: return memo[s]
    memo[s] = aggregate(combine(s,a,solve(T(s,a))) for a in feasible(s))
    return memo[s]
BOTTOM_UP_TABULATION:
  for s in dependency_respecting_order:
    table[s] = base_value(s) if terminal(s) else recurrence(table, s)
  return table[target]
CYCLIC_DEPENDENCIES require separate fixed-point or graph-algorithm reasoning; ordinary acyclic tabulation is not automatically valid.

7. INFERENCE RULES
R1: VALID_BASE_CASES and WELL_FOUNDED_DEPENDENCIES and VALID_RECURRENCE => TERMINATING_EVALUATION.
R2: CORRECT_BASE_CASES and CORRECT_TRANSITION and INDUCTIVE_DEPENDENCY_ORDER => CORRECT_VALUE_FUNCTION.
R3: STATE_SUFFICIENCY and FEASIBLE_DECISIONS and OPTIMAL_SUBSTRUCTURE => OPTIMAL_RECURRENCE_SOUNDNESS.
R4: MEMOIZED_ONCE_PER_STATE and FINITE_REACHABLE_STATES => NO_REPEATED_FULL_STATE_EVALUATION.
R5: STORED_ARGOPT and VALID_PREDECESSORS => RECONSTRUCTIBLE_OPTIMAL_WITNESS.
R6: INVALID_STATE_COMPRESSION => POSSIBLE_INCORRECT_RESULT.

8. WORKED EXAMPLE: 0/1 KNAPSACK
Inputs: n items, weights w_i, values v_i, capacity W; each item is selected at most once.
State: DP[i,c] = maximum value using the first i items with capacity at most c.
Base: DP[0,c] = 0 for 0 <= c <= W.
If w_i > c: DP[i,c] = DP[i-1,c].
Otherwise: DP[i,c] = max(DP[i-1,c], v_i + DP[i-1,c-w_i]).
Output: DP[n,W].
Time: O(nW); space: O(nW), reducible to O(W) for value-only output with capacities iterated downwards.
Note: O(nW) is pseudo-polynomial in numeric capacity W, not polynomial in its binary input length.

9. WORKED EXAMPLE: LONGEST COMMON SUBSEQUENCE
Inputs: sequences X of length m and Y of length n.
State: L[i,j] = LCS length of prefixes X[1..i], Y[1..j].
Base: L[i,0] = L[0,j] = 0.
If X[i] = Y[j]: L[i,j] = 1 + L[i-1,j-1].
Otherwise: L[i,j] = max(L[i-1,j], L[i,j-1]).
Time: O(mn); table space: O(mn); value-only rolling rows: O(min(m,n)).

10. WORKED EXAMPLE: FIBONACCI
F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2) for n>=2.
Memoization or tabulation uses O(n) additions and O(n) stored values; rolling variables use O(1) auxiliary machine-word slots, ignoring integer bit growth.

11. CORRECTNESS OBLIGATIONS
C1: Every state has a precise semantic meaning.
C2: Base cases agree with the mathematical problem.
C3: Each transition preserves feasibility.
C4: All valid choices are covered without introducing invalid choices.
C5: Dependencies terminate or have a separately justified fixed-point semantics.
C6: The recurrence's aggregation operator matches the objective.
C7: Reconstruction yields a feasible witness attaining the computed value.

12. COMPLEXITY MODEL
Time = O(number_of_evaluated_states * maximum_transition_work_per_state) when transition work is uniformly bounded.
Space = memo/table storage + recursion stack + reconstruction storage.
State compression is valid only if discarded information is not needed by later transitions or witness reconstruction.

13. SEMANTIC EQUIVALENCE
MEMOIZATION ~ TABULATION when both evaluate the same recurrence and base cases over the required states with valid dependency handling.
VALUE_EQUIVALENCE does not imply identical memory consumption, evaluation order, or reconstruction capability.
DP != GREEDY: local-choice optimality is not assumed in DP.
DP != DIVIDE_AND_CONQUER: DP explicitly reuses state results; decomposition alone does not guarantee overlap.

14. VALIDATION TESTS
TEST_A: Fibonacci F(10) = 55.
TEST_B: Knapsack weights=[2,3,4], values=[3,4,5], W=5 => optimum 7.
TEST_C: LCS('ABCBDAB','BDCABA') => length 4.
TEST_D: Knapsack with W=0 and positive weights => optimum 0.
TEST_E: Reject tabulation orders that access unevaluated dependencies.
TEST_F: Confirm reconstructed knapsack selections obey capacity and 0/1 restrictions.

15. CONFIDENCE
Formal recurrence claims: high, conditional on explicit assumptions.
Complexity claims: high under the stated computational cost model.
Applicability to a new problem: requires state-sufficiency and recurrence validation; not inferred from surface similarity alone.

16. FLOW_HASH
FLOW_HASH_METHOD: SHA-256 over canonical UTF-8 representation of the flow body, excluding the computed hash field.
FLOW_HASH_VALUE: NOT_COMPUTED
Canonicalisation must specify newline normalisation and field ordering before hashing.

17. UPDATE_MODEL
On change to state definition, recurrence, base cases, or transitions:
  invalidate dependent correctness claims and affected memo entries;
  rerun validation tests;
  regenerate the canonical hash;
  record version and provenance.

18. AI_CONSUMPTION
ENTITY_EXTRACTION: enabled
TYPED_RELATIONSHIP_REASONING: enabled
RECURSIVE_INFERENCE: enabled_with_well_foundedness_checks
MATHEMATICAL_VALIDATION: conditional
PROOF_OBLIGATION_TRACKING: enabled
SEMANTIC_RETRIEVAL: enabled
UNCERTAINTY_REPORTING: required_when_assumptions_unverified
OUTPUT_CONTRACT: {problem, states, recurrence, base_cases, evaluation_order, result, complexity, proof_status}

END FLOW ALGEBRA