Divide and Conquer Ontology

AI SEARCH

FLOW ALGEBRA — DIVIDE AND CONQUER ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms/divide-and-conquer-ontology.html

FLOW DIVIDE_AND_CONQUER_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Divide and Conquer Ontology"
    PURPOSE = "Formalise divide-and-conquer algorithms, recursive problem decomposition, subproblems, base cases, combination, recurrences, correctness and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    DIVIDE_AND_CONQUER
    DIVIDE_AND_CONQUER_ALGORITHM
    PROBLEM
    PROBLEM_INSTANCE
    SUBPROBLEM
    INDEPENDENT_SUBPROBLEM
    OVERLAPPING_SUBPROBLEM
    DIVIDE_PHASE
    CONQUER_PHASE
    COMBINE_PHASE
    BASE_CASE
    RECURSIVE_CASE
    RECURSIVE_CALL
    RECURSION_TREE
    RECURSION_LEVEL
    BRANCHING_FACTOR
    PROBLEM_SIZE
    SUBPROBLEM_SIZE
    PARTITION
    SPLIT
    PIVOT
    MIDPOINT
    MERGE
    COMBINATION_FUNCTION
    PARTIAL_RESULT
    FINAL_RESULT
    INPUT
    OUTPUT
    PRECONDITION
    POSTCONDITION
    INVARIANT
    CORRECTNESS
    TERMINATION
    RECURRENCE_RELATION
    MASTER_THEOREM
    RECURSION_DEPTH
    WORK_PER_LEVEL
    TOTAL_WORK
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    AUXILIARY_SPACE
    CALL_STACK
    MERGE_SORT
    QUICK_SORT
    BINARY_SEARCH
    KARATSUBA_MULTIPLICATION
    STRASSEN_ALGORITHM
    FAST_FOURIER_TRANSFORM
    PARALLEL_DIVIDE_AND_CONQUER
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    SOLVES
    ACCEPTS
    PRODUCES
    DIVIDES
    DECOMPOSES_INTO
    HAS_SUBPROBLEM
    PARTITIONS
    SPLITS
    SELECTS_PIVOT
    HAS_BASE_CASE
    HAS_RECURSIVE_CASE
    RECURSES_ON
    CONQUERS
    COMBINES
    MERGES
    HAS_PARTIAL_RESULT
    HAS_FINAL_RESULT
    PRECEDES
    FOLLOWS
    HAS_RECURSION_LEVEL
    HAS_BRANCHING_FACTOR
    HAS_PROBLEM_SIZE
    HAS_SUBPROBLEM_SIZE
    HAS_RECURRENCE
    HAS_RECURSION_DEPTH
    HAS_WORK_PER_LEVEL
    HAS_TOTAL_WORK
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    USES_AUXILIARY_SPACE
    IMPLEMENTED_BY
    EXECUTED_BY
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    DIVIDE_AND_CONQUER_SPECIFICATIONS
    PROBLEM_DEFINITIONS
    PSEUDOCODE
    SOURCE_CODE
    INPUT_OUTPUT_CONTRACTS
    PARTITION_DEFINITIONS
    BASE_CASE_DEFINITIONS
    RECURSIVE_CALL_DATA
    COMBINATION_DEFINITIONS
    RECURRENCE_RELATIONS
    RECURSION_TREE_DATA
    EXECUTION_TRACES
    CORRECTNESS_PROOFS
    COMPLEXITY_ANALYSES
    IMPLEMENTATION_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_DIVIDE_AND_CONQUER_IDENTIFIERS
    NORMALISE_PROBLEM_IDENTIFIERS
    NORMALISE_INPUT_AND_OUTPUT_TYPES
    NORMALISE_PROBLEM_SIZE_MEASURES
    NORMALISE_PARTITION_AND_SPLIT_TERMS
    NORMALISE_BASE_CASES
    NORMALISE_RECURSIVE_CALLS
    NORMALISE_COMBINATION_FUNCTIONS
    NORMALISE_RECURRENCE_RELATIONS
    NORMALISE_RECURSION_TREE_LEVELS
    NORMALISE_COMPLEXITY_NOTATION
    RESOLVE_PROBLEM_SUBPROBLEM_AND_EXECUTION_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS DIVIDE_AND_CONQUER_PIPELINE {
    PROBLEM_INSTANCE
      -> PRECONDITION_CHECK
      -> BASE_CASE_CHECK
      -> DIVIDE
      -> SUBPROBLEM_GENERATION
      -> CONQUER
      -> RECURSIVE_SOLVING
      -> COMBINE
      -> FINAL_RESULT
      -> POSTCONDITION_CHECK
  }

  PROCESS DIVIDE_REASONING {
    PROBLEM_INSTANCE
      -> PROBLEM_SIZE

    NON_BASE_PROBLEM
      -> PARTITION_OR_SPLIT_RULE
      -> SUBPROBLEM_SET
      -> SUBPROBLEM_SIZES
      -> PROGRESS_TOWARD_BASE_CASE_CHECK
  }

  PROCESS BASE_CASE_REASONING {
    PROBLEM_INSTANCE
      -> BASE_CASE_PREDICATE

    BASE_CASE_TRUE
      -> DIRECT_SOLUTION

    BASE_CASE_FALSE
      -> DIVIDE_PHASE
  }

  PROCESS CONQUER_REASONING {
    EACH_SUBPROBLEM
      -> BASE_CASE_CHECK

    NON_BASE_SUBPROBLEM
      -> RECURSIVE_CALL
      -> SUBPROBLEM_RESULT

    ALL_REQUIRED_SUBPROBLEM_RESULTS
      -> COMBINE_PHASE
  }

  PROCESS COMBINE_REASONING {
    SUBPROBLEM_RESULTS
      -> COMBINATION_FUNCTION
      -> MERGE_OR_AGGREGATE_OR_SELECT
      -> PARENT_PROBLEM_RESULT
  }

  PROCESS RECURSION_TREE_REASONING {
    ROOT
      -> ORIGINAL_PROBLEM

    EACH_NONLEAF_NODE
      -> SUBPROBLEM_CHILDREN

    EACH_LEVEL
      -> LEVEL_SUBPROBLEM_COUNT
      -> LEVEL_PROBLEM_SIZES
      -> WORK_PER_LEVEL

    LEAVES
      -> BASE_CASES

    TREE
      -> RECURSION_DEPTH
      -> TOTAL_WORK
  }

  PROCESS RECURRENCE_REASONING {
    PROBLEM_SIZE_N
      -> NUMBER_OF_SUBPROBLEMS_A

    SUBPROBLEM_SIZE
      -> N_DIVIDED_BY_B_OR_OTHER_SIZE_FUNCTION

    DIVIDE_AND_COMBINE_WORK
      -> F(N)

    RECURRENCE
      -> T(N) = A*T(N/B) + F(N)
      OR -> GENERAL_RECURSIVE_COST_RELATION

    RECURRENCE
      -> ASYMPTOTIC_ANALYSIS
  }

  PROCESS MASTER_THEOREM_REASONING {
    RECURRENCE
      -> MATCH_STANDARD_FORM

    MATCHED_FORM
      -> COMPARE_F_N_WITH_CRITICAL_GROWTH

    COMPARISON
      -> APPLICABLE_MASTER_THEOREM_CASE

    APPLICABLE_CASE
      -> ASYMPTOTIC_BOUND

    NONMATCHING_RECURRENCE
      -> USE_OTHER_ANALYSIS_METHOD
  }

  PROCESS CORRECTNESS_REASONING {
    BASE_CASE
      -> DIRECT_CORRECTNESS

    ASSUME_SUBPROBLEM_SOLUTIONS_CORRECT
      -> COMBINATION_CORRECTNESS

    DIVIDE_VALIDITY
      + SUBPROBLEM_CORRECTNESS
      + COMBINATION_CORRECTNESS
      -> PARENT_PROBLEM_CORRECTNESS

    INDUCTION_OVER_PROBLEM_SIZE
      -> ALGORITHM_CORRECTNESS_EVIDENCE
  }

  PROCESS TERMINATION_REASONING {
    NON_BASE_PROBLEM
      -> SUBPROBLEMS

    SUBPROBLEMS
      -> STRICTLY_SMALLER_OR_WELL_FOUNDED_MEASURE

    MEASURE_DECREASE
      -> EVENTUAL_BASE_CASE
      -> TERMINATION_EVIDENCE
  }

  PROCESS COMPLEXITY_REASONING {
    RECURRENCE_RELATION
      -> RECURSION_TREE_OR_RECURRENCE_ANALYSIS

    RECURSION_LEVELS
      -> WORK_PER_LEVEL

    WORK_PER_LEVEL + DEPTH
      -> TOTAL_TIME_COST

    CALL_STACK + TEMPORARY_COMBINATION_STORAGE
      -> SPACE_COMPLEXITY

    BALANCED_OR_UNBALANCED_PARTITIONS
      -> CASE_SPECIFIC_COMPLEXITY
  }

  PROCESS PARALLEL_REASONING {
    INDEPENDENT_SUBPROBLEMS
      -> PARALLEL_EXECUTION_CANDIDATES

    PARALLEL_SUBPROBLEM_EXECUTION
      -> SYNCHRONISATION_BEFORE_COMBINE

    CRITICAL_PATH
      -> PARALLEL_DEPTH

    TOTAL_WORK + PARALLEL_DEPTH
      -> PARALLEL_COMPLEXITY_PROFILE
  }

  RULES {
    IF DIVIDE_AND_CONQUER_IS_ASSERTED
    THEN REQUIRE DIVIDE_CONQUER_AND_COMBINE_OR_EQUIVALENT_RECURSIVE_DECOMPOSITION

    IF RECURSIVE_CALL_IS_USED
    THEN REQUIRE PROGRESS_TOWARD_BASE_CASE_FOR_TERMINATION_CLAIM

    IF SUBPROBLEMS_OVERLAP
    THEN DO_NOT AUTOMATICALLY_RECLASSIFY_AS_DYNAMIC_PROGRAMMING_WITHOUT_REUSE_CONTEXT

    IF MASTER_THEOREM_IS_APPLIED
    THEN REQUIRE APPLICABLE_RECURRENCE_FORM_AND_CONDITIONS

    IF QUICK_SORT_COMPLEXITY_IS_ANALYSED
    THEN PRESERVE PARTITION_AND_PIVOT_CONTEXT

    IF MERGE_SORT_COMPLEXITY_IS_ANALYSED
    THEN PRESERVE DIVISION_AND_MERGE_COST_CONTEXT

    IF PARALLEL_EXECUTION_IS_ASSERTED
    THEN PRESERVE SUBPROBLEM_INDEPENDENCE_AND_SYNCHRONISATION_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND DIVIDE_AND_CONQUER_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        PROBLEM_DECOMPOSITION_COMPLETENESS,
        BASE_CASE_CERTAINTY,
        SUBPROBLEM_SIZE_CERTAINTY,
        COMBINATION_FUNCTION_CERTAINTY,
        RECURRENCE_CERTAINTY,
        CORRECTNESS_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF BASE_CASE_OR_PROGRESS_MEASURE_IS_UNKNOWN
    THEN REDUCE_TERMINATION_CONFIDENCE

    IF PARTITION_SIZE_DISTRIBUTION_IS_UNKNOWN
    THEN REDUCE_CASE_COMPLEXITY_CONFIDENCE

    IF RECURRENCE_AND_EXECUTION_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        DIVIDE_AND_CONQUER_IDENTIFIER,
        PROBLEM_DEFINITION,
        DIVISION_RULE,
        BASE_CASE,
        COMBINATION_FUNCTION,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B
    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    DIVIDE_AND_CONQUER != DYNAMIC_PROGRAMMING
    DIVIDE_AND_CONQUER != RECURSION_AS_IDENTICAL_CONCEPT
    DIVIDE_PHASE != COMBINE_PHASE
    BASE_CASE != RECURSIVE_CASE
    RECURRENCE_RELATION != ALGORITHM_IMPLEMENTATION
    MASTER_THEOREM != UNIVERSAL_RECURRENCE_SOLVER
    BALANCED_PARTITION != GUARANTEED_PARTITION
    INDEPENDENT_SUBPROBLEMS != OVERLAPPING_SUBPROBLEMS
    TOTAL_WORK != PARALLEL_DEPTH
    TIME_COMPLEXITY != RECURSION_DEPTH_ALONE
    EMPIRICAL_RUNTIME != FORMAL_RECURRENCE_BOUND
    COMPLEXITY_DEPENDS_ON_PARTITION_SUBPROBLEM_SIZE_COMBINATION_COST_AND_IMPLEMENTATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_DIVIDE_AND_CONQUER_IDENTIFIER
    CHECK_PROBLEM_DEFINITION
    CHECK_INPUT_AND_OUTPUT
    CHECK_BASE_CASE
    CHECK_DIVISION_RULE
    CHECK_SUBPROBLEM_SET
    CHECK_SUBPROBLEM_SIZE_REDUCTION
    CHECK_RECURSIVE_CALLS
    CHECK_COMBINATION_FUNCTION
    CHECK_RECURRENCE_RELATION
    CHECK_RECURSION_TREE
    CHECK_TERMINATION_EVIDENCE
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_MASTER_THEOREM_APPLICABILITY_IF_USED
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PARALLEL_CONTEXT_IF_APPLICABLE
    CHECK_IMPLEMENTATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_DIVIDE_AND_CONQUER_ENTITIES
    PROBLEM_AND_SUBPROBLEM_RELATIONS
    DIVIDE_PHASE_RELATIONS
    BASE_CASE_RELATIONS
    RECURSIVE_CALL_RELATIONS
    CONQUER_PHASE_RELATIONS
    COMBINE_PHASE_RELATIONS
    RECURSION_TREE_RELATIONS
    RECURRENCE_RELATIONS
    MASTER_THEOREM_RELATIONS
    TERMINATION_RELATIONS
    CORRECTNESS_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    PARALLELISM_RELATIONS
    IMPLEMENTATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON PROBLEM_DECOMPOSITION_OR_ALGORITHM_CHANGE {
      NORMALISE
      RESOLVE_PROBLEM_SUBPROBLEM_AND_EXECUTION_IDENTITIES
      UPDATE_BASE_CASES
      UPDATE_DIVISION_AND_COMBINATION_RULES
      UPDATE_RECURSION_TREE
      UPDATE_RECURRENCE
      REASSESS_TERMINATION_CORRECTNESS_AND_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_OR_BENCHMARK_DATA {
      LINK_EVIDENCE
      UPDATE_EXECUTION_TRACE
      UPDATE_PARTITION_AND_SUBPROBLEM_DATA
      COMPARE_OBSERVED_WORK_WITH_RECURRENCE_MODEL
      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_DIVIDE_AND_CONQUER_ALGORITHM
      BY_PROBLEM
      BY_SUBPROBLEM
      BY_BASE_CASE
      BY_PARTITION
      BY_RECURSIVE_CALL
      BY_COMBINATION
      BY_RECURRENCE
      BY_RECURSION_TREE
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_PROBLEM_DECOMPOSITION
      ANALYSE_BASE_CASES
      TRACE_RECURSIVE_CALLS
      ANALYSE_COMBINATION
      BUILD_RECURSION_TREE
      ANALYSE_RECURRENCES
      CHECK_MASTER_THEOREM_APPLICABILITY
      ANALYSE_TERMINATION
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLEXITY
      ANALYSE_PARALLELISM
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_DIVIDE_AND_CONQUER_FROM_DYNAMIC_PROGRAMMING_AND_GENERIC_RECURSION
      DISTINGUISH_DIVIDE_CONQUER_AND_COMBINE_PHASES
      PRESERVE_PROBLEM_SIZE_PARTITION_BASE_CASE_RECURRENCE_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_RECURSION_DEPTH_FROM_TOTAL_WORK
      APPLY_MASTER_THEOREM_ONLY_WHEN_PRECONDITIONS_ARE_MET
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_DIVIDE_AND_CONQUER_INFERENCE
    }
  }

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

END FLOW