Dynamic Programming Ontology

AI SEARCH

FLOW ALGEBRA — DYNAMIC PROGRAMMING ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms/dynamic-programming-ontology.html

FLOW DYNAMIC_PROGRAMMING_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Dynamic Programming Ontology"
    PURPOSE = "Formalise dynamic programming problems, states, overlapping subproblems, optimal substructure, recurrences, memoisation, tabulation, transitions, solutions, correctness and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    DYNAMIC_PROGRAMMING
    DYNAMIC_PROGRAMMING_ALGORITHM
    PROBLEM
    PROBLEM_INSTANCE
    SUBPROBLEM
    OVERLAPPING_SUBPROBLEM
    OPTIMAL_SUBSTRUCTURE
    STATE
    STATE_SPACE
    STATE_VARIABLE
    STATE_KEY
    INITIAL_STATE
    TERMINAL_STATE
    BASE_CASE
    RECURRENCE_RELATION
    TRANSITION
    TRANSITION_FUNCTION
    DECISION
    CHOICE
    CANDIDATE_SOLUTION
    OPTIMAL_SOLUTION
    OBJECTIVE_FUNCTION
    COST
    VALUE
    SCORE
    MINIMISATION
    MAXIMISATION
    MEMOISATION
    MEMO_TABLE
    CACHE
    TOP_DOWN_DYNAMIC_PROGRAMMING
    BOTTOM_UP_DYNAMIC_PROGRAMMING
    TABULATION
    DP_TABLE
    TABLE_CELL
    TABLE_DIMENSION
    COMPUTATION_ORDER
    DEPENDENCY
    SUBPROBLEM_DEPENDENCY
    RECONSTRUCTION
    PREDECESSOR
    BACKPOINTER
    SOLUTION_PATH
    SEQUENCE
    ARRAY
    MATRIX
    GRAPH
    DAG
    STRING
    TREE
    KNAPSACK_PROBLEM
    LONGEST_COMMON_SUBSEQUENCE
    LONGEST_INCREASING_SUBSEQUENCE
    EDIT_DISTANCE
    MATRIX_CHAIN_MULTIPLICATION
    SHORTEST_PATH_PROBLEM
    COIN_CHANGE_PROBLEM
    PARTITION_PROBLEM
    INTERVAL_DYNAMIC_PROGRAMMING
    TREE_DYNAMIC_PROGRAMMING
    BITMASK_DYNAMIC_PROGRAMMING
    DIGIT_DYNAMIC_PROGRAMMING
    STOCHASTIC_DYNAMIC_PROGRAMMING
    BELLMAN_EQUATION
    PRINCIPLE_OF_OPTIMALITY
    PRECONDITION
    POSTCONDITION
    INVARIANT
    CORRECTNESS
    TERMINATION
    INPUT_SIZE
    STATE_COUNT
    TRANSITION_COUNT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    SPACE_OPTIMISATION
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    BENCHMARK
    PERFORMANCE_METRIC
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    SOLVES
    DECOMPOSES_INTO
    HAS_SUBPROBLEM
    OVERLAPS_WITH
    HAS_STATE
    HAS_STATE_VARIABLE
    HAS_STATE_KEY
    TRANSITIONS_TO
    DEPENDS_ON
    HAS_BASE_CASE
    HAS_RECURRENCE
    HAS_TRANSITION
    HAS_DECISION
    HAS_CHOICE
    HAS_OBJECTIVE
    HAS_COST
    HAS_VALUE
    MINIMISES
    MAXIMISES
    MEMOISES
    CACHES
    TABULATES
    STORES_IN
    LOOKS_UP
    COMPUTES
    PRECEDES
    FOLLOWS
    RECONSTRUCTS
    HAS_PREDECESSOR
    HAS_BACKPOINTER
    PRODUCES
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    OPTIMISES_SPACE
    IMPLEMENTED_BY
    EXECUTED_BY
    BENCHMARKED_BY
    HAS_CONFIGURATION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    DYNAMIC_PROGRAMMING_SPECIFICATIONS
    PROBLEM_DEFINITIONS
    PSEUDOCODE
    SOURCE_CODE
    STATE_DEFINITIONS
    BASE_CASE_DEFINITIONS
    RECURRENCE_RELATIONS
    TRANSITION_DEFINITIONS
    OBJECTIVE_FUNCTIONS
    SUBPROBLEM_DEPENDENCY_DATA
    MEMO_TABLE_DATA
    DP_TABLE_DATA
    COMPUTATION_ORDER_DATA
    RECONSTRUCTION_DATA
    EXECUTION_TRACES
    CORRECTNESS_PROOFS
    COMPLEXITY_ANALYSES
    BENCHMARK_DATA
    IMPLEMENTATION_DATA
    LANGUAGE_AND_RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_DYNAMIC_PROGRAMMING_IDENTIFIERS
    NORMALISE_PROBLEM_IDENTIFIERS
    NORMALISE_STATE_DEFINITIONS
    NORMALISE_STATE_KEYS
    NORMALISE_BASE_CASES
    NORMALISE_RECURRENCE_RELATIONS
    NORMALISE_TRANSITION_DEFINITIONS
    NORMALISE_OBJECTIVE_FUNCTIONS
    NORMALISE_MEMO_AND_TABLE_IDENTIFIERS
    NORMALISE_COMPUTATION_ORDER
    NORMALISE_PREDECESSOR_AND_BACKPOINTER_DATA
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_BENCHMARK_UNITS
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_PROBLEM_STATE_AND_SUBPROBLEM_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS DYNAMIC_PROGRAMMING_PIPELINE {
    PROBLEM
      -> SUBPROBLEM_DECOMPOSITION
      -> STATE_DEFINITION
      -> BASE_CASE_DEFINITION
      -> RECURRENCE_DEFINITION
      -> DEPENDENCY_ANALYSIS
      -> MEMOISATION_OR_TABULATION
      -> STATE_EVALUATION
      -> FINAL_VALUE_OR_SOLUTION
      -> SOLUTION_RECONSTRUCTION_IF_REQUIRED
      -> VALIDATION
  }

  PROCESS SUBPROBLEM_REASONING {
    PROBLEM_INSTANCE
      -> CANDIDATE_SUBPROBLEMS

    CANDIDATE_SUBPROBLEMS
      -> STATE_REPRESENTATIONS

    STATE_REPRESENTATIONS
      -> EQUIVALENT_SUBPROBLEM_DETECTION

    REPEATED_EQUIVALENT_STATES
      -> OVERLAPPING_SUBPROBLEMS
  }

  PROCESS OPTIMAL_SUBSTRUCTURE_REASONING {
    PROBLEM_SOLUTION
      -> COMPONENT_SUBPROBLEM_SOLUTIONS

    OPTIMAL_GLOBAL_SOLUTION
      -> REQUIRED_SUBPROBLEM_SOLUTIONS

    SUBPROBLEM_OPTIMALITY
      -> GLOBAL_COMBINATION

    VALID_DECOMPOSITION
      -> OPTIMAL_SUBSTRUCTURE_EVIDENCE
  }

  PROCESS RECURRENCE_REASONING {
    STATE
      -> AVAILABLE_TRANSITIONS

    EACH_TRANSITION
      -> DEPENDENT_SUBPROBLEM_STATE

    DEPENDENT_STATE_VALUES
      -> COMBINATION_FUNCTION

    COMBINATION_FUNCTION
      -> MIN_MAX_SUM_OR_OTHER_OBJECTIVE

    RESULT
      -> STATE_VALUE
  }

  PROCESS TOP_DOWN_REASONING {
    QUERY_STATE
      -> MEMO_LOOKUP

    MEMO_HIT
      -> RETURN_STORED_VALUE

    MEMO_MISS
      -> BASE_CASE_CHECK

    NON_BASE_STATE
      -> RECURSIVELY_COMPUTE_DEPENDENCIES

    COMPUTED_VALUE
      -> STORE_IN_MEMO
      -> RETURN_VALUE
  }

  PROCESS BOTTOM_UP_REASONING {
    BASE_CASES
      -> INITIALISE_DP_TABLE

    DEPENDENCY_GRAPH
      -> VALID_COMPUTATION_ORDER

    FOR EACH_STATE_IN_ORDER
      -> READ_DEPENDENT_STATES
      -> APPLY_RECURRENCE
      -> STORE_STATE_VALUE

    TARGET_STATE
      -> FINAL_VALUE
  }

  PROCESS TABLE_REASONING {
    STATE_VARIABLES
      -> TABLE_DIMENSIONS

    STATE_KEY
      -> TABLE_CELL

    TABLE_CELL
      -> STATE_VALUE

    TRANSITION
      -> CELL_DEPENDENCIES

    CELL_DEPENDENCIES
      -> COMPUTATION_ORDER_CONSTRAINTS
  }

  PROCESS RECONSTRUCTION_REASONING {
    OPTIMAL_STATE_VALUE
      -> PREDECESSOR_OR_DECISION_INFORMATION

    TARGET_STATE
      -> FOLLOW_BACKPOINTERS_OR_RECOMPUTE_CHOICES

    STATE_SEQUENCE
      -> SOLUTION_PATH_OR_STRUCTURE

    RECONSTRUCTED_SOLUTION
      -> OBJECTIVE_VALUE_VALIDATION
  }

  PROCESS SPACE_OPTIMISATION_REASONING {
    FULL_DP_STATE
      -> DEPENDENCY_WINDOW_ANALYSIS

    ONLY_RECENT_OR_SUBSET_STATES_REQUIRED
      -> REDUCED_STORAGE_REPRESENTATION

    REDUCED_STORAGE
      -> VERIFY_RECURRENCE_DEPENDENCIES_REMAIN_AVAILABLE

    VALID_REDUCTION
      -> SPACE_OPTIMISED_DP
  }

  PROCESS CORRECTNESS_REASONING {
    BASE_CASES
      -> CORRECT_INITIAL_VALUES

    ASSUME_DEPENDENT_SUBPROBLEMS_CORRECT
      -> APPLY_RECURRENCE

    RECURRENCE
      -> CORRECT_CURRENT_STATE

    VALID_COMPUTATION_ORDER_OR_MEMO_RECURSION
      -> ALL_REQUIRED_STATES_CORRECT

    TARGET_STATE
      -> POSTCONDITION
  }

  PROCESS COMPLEXITY_REASONING {
    REACHABLE_STATE_SET
      -> STATE_COUNT

    EACH_STATE
      -> TRANSITIONS_PER_STATE

    STATE_COUNT * TRANSITION_COST
      -> TIME_COMPLEXITY_MODEL

    STORED_STATES + RECONSTRUCTION_METADATA
      -> SPACE_COMPLEXITY_MODEL

    SPACE_OPTIMISATION
      -> REDUCED_SPACE_MODEL
  }

  RULES {
    IF DYNAMIC_PROGRAMMING_IS_ASSERTED
    THEN IDENTIFY STATE_RECURRENCE_AND_REUSE_OR_ORDERING_STRUCTURE

    IF MEMOISATION_IS_USED
    THEN REQUIRE STABLE_STATE_KEY_SEMANTICS

    IF TABULATION_IS_USED
    THEN REQUIRE COMPUTATION_ORDER_SATISFIES_STATE_DEPENDENCIES

    IF OPTIMAL_SOLUTION_IS_ASSERTED
    THEN REQUIRE OBJECTIVE_AND_OPTIMAL_SUBSTRUCTURE_CONTEXT

    IF SPACE_OPTIMISATION_IS_APPLIED
    THEN PRESERVE ALL_RECURRENCE_DEPENDENCIES_REQUIRED_FOR_CORRECTNESS

    IF RECONSTRUCTED_SOLUTION_IS_ASSERTED
    THEN VALIDATE ITS_OBJECTIVE_VALUE_AGAINST_COMPUTED_OPTIMUM

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE STATE_COUNT_TRANSITION_COST_AND_REACHABILITY_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND DYNAMIC_PROGRAMMING_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        PROBLEM_IDENTITY_CERTAINTY,
        STATE_DEFINITION_COMPLETENESS,
        BASE_CASE_CERTAINTY,
        RECURRENCE_CERTAINTY,
        DEPENDENCY_GRAPH_COMPLETENESS,
        OBJECTIVE_FUNCTION_CERTAINTY,
        CORRECTNESS_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF BASE_CASE_OR_RECURRENCE_IS_INCOMPLETE
    THEN REDUCE_RESULT_CONFIDENCE

    IF COMPUTATION_ORDER_VIOLATES_DEPENDENCIES
    THEN REDUCE_OR_INVALIDATE_TABULATION_CONFIDENCE

    IF FORMAL_RECURRENCE_AND_EXECUTION_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        PROBLEM_IDENTIFIER,
        STATE_DEFINITION,
        RECURRENCE_RELATION,
        OBJECTIVE_FUNCTION,
        DP_STRATEGY,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    DYNAMIC_PROGRAMMING != RECURSION
    DYNAMIC_PROGRAMMING != MEMOISATION_AS_IDENTICAL_CONCEPT
    MEMOISATION != TABULATION
    STATE != SUBPROBLEM_RESULT
    STATE_KEY != STATE_VALUE
    BASE_CASE != TERMINAL_SOLUTION_IN_ALL_PROBLEMS
    RECURRENCE != IMPLEMENTATION
    OVERLAPPING_SUBPROBLEMS != OPTIMAL_SUBSTRUCTURE
    OPTIMAL_SUBSTRUCTURE != GREEDY_CHOICE_PROPERTY
    DP_TABLE != ALGORITHM_AS_IDENTICAL_ENTITY
    COMPUTATION_ORDER != SORT_ORDER_IN_GENERAL
    SPACE_OPTIMISATION != LOSS_OF_REQUIRED_DEPENDENCIES
    RECONSTRUCTED_SOLUTION != OBJECTIVE_VALUE
    TIME_COMPLEXITY != NUMBER_OF_TABLE_CELLS_ALONE_WHEN_TRANSITION_COST_EXCEEDS_CONSTANT_TIME
    UNREACHABLE_STATES_NEED_NOT_BE_COMPUTED_IN_ALL_IMPLEMENTATIONS
    COMPLEXITY_DEPENDS_ON_REACHABLE_STATES_TRANSITIONS_AND_IMPLEMENTATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_DYNAMIC_PROGRAMMING_IDENTIFIER
    CHECK_PROBLEM_DEFINITION
    CHECK_STATE_DEFINITION
    CHECK_STATE_KEYS
    CHECK_BASE_CASES
    CHECK_RECURRENCE
    CHECK_TRANSITIONS
    CHECK_OBJECTIVE_FUNCTION
    CHECK_SUBPROBLEM_DEPENDENCIES
    CHECK_MEMOISATION_IF_APPLICABLE
    CHECK_TABULATION_IF_APPLICABLE
    CHECK_COMPUTATION_ORDER
    CHECK_TARGET_STATE
    CHECK_RECONSTRUCTION_IF_APPLICABLE
    CHECK_SPACE_OPTIMISATION_IF_APPLICABLE
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_COMPLEXITY_CONTEXT
    CHECK_IMPLEMENTATION
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_DYNAMIC_PROGRAMMING_ENTITIES
    PROBLEM_AND_SUBPROBLEM_RELATIONS
    STATE_RELATIONS
    BASE_CASE_RELATIONS
    RECURRENCE_RELATIONS
    TRANSITION_RELATIONS
    DEPENDENCY_GRAPH_RELATIONS
    MEMOISATION_RELATIONS
    TABULATION_RELATIONS
    DP_TABLE_RELATIONS
    COMPUTATION_ORDER_RELATIONS
    OBJECTIVE_AND_OPTIMALITY_RELATIONS
    RECONSTRUCTION_RELATIONS
    SPACE_OPTIMISATION_RELATIONS
    CORRECTNESS_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    IMPLEMENTATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON PROBLEM_STATE_OR_RECURRENCE_CHANGE {
      NORMALISE
      RESOLVE_PROBLEM_STATE_AND_SUBPROBLEM_IDENTITIES
      UPDATE_BASE_CASES
      UPDATE_RECURRENCE_AND_TRANSITIONS
      UPDATE_DEPENDENCY_GRAPH
      RECOMPUTE_AFFECTED_STATES
      REASSESS_CORRECTNESS_AND_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_OR_BENCHMARK_DATA {
      LINK_EVIDENCE
      UPDATE_MEMO_OR_TABLE_STATE
      UPDATE_EXECUTION_TRACE
      VALIDATE_TARGET_VALUE_AND_RECONSTRUCTION
      UPDATE_EMPIRICAL_PERFORMANCE
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_DYNAMIC_PROGRAMMING_ALGORITHM
      BY_PROBLEM
      BY_SUBPROBLEM
      BY_STATE
      BY_BASE_CASE
      BY_RECURRENCE
      BY_TRANSITION
      BY_MEMO_TABLE
      BY_DP_TABLE
      BY_OBJECTIVE
      BY_SOLUTION
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_SUBPROBLEM_DECOMPOSITION
      ANALYSE_OPTIMAL_SUBSTRUCTURE
      ANALYSE_RECURRENCES
      TRACE_TOP_DOWN_MEMOISATION
      TRACE_BOTTOM_UP_TABULATION
      ANALYSE_DP_TABLE_DEPENDENCIES
      RECONSTRUCT_SOLUTIONS
      ANALYSE_SPACE_OPTIMISATION
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLEXITY
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_DYNAMIC_PROGRAMMING_FROM_RECURSION_MEMOISATION_AND_TABULATION
      DISTINGUISH_STATE_STATE_KEY_AND_STATE_VALUE
      PRESERVE_PROBLEM_STATE_RECURRENCE_OBJECTIVE_STRATEGY_IMPLEMENTATION_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_OPTIMAL_SUBSTRUCTURE_FROM_GREEDY_CHOICE_PROPERTY
      PRESERVE_DEPENDENCY_ORDER_AND_RECONSTRUCTION_EVIDENCE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_DYNAMIC_PROGRAMMING_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              DYNAMIC_PROGRAMMING_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW