Greedy Algorithm Ontology

AI SEARCH

FLOW ALGEBRA — GREEDY ALGORITHM ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms/greedy-algorithm-ontology.html

FLOW GREEDY_ALGORITHM_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Greedy Algorithm Ontology"
    PURPOSE = "Formalise greedy algorithms, candidate sets, local choices, feasibility, greedy-choice properties, optimal substructure, objective functions, correctness and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    GREEDY_ALGORITHM
    GREEDY_METHOD
    PROBLEM
    PROBLEM_INSTANCE
    CANDIDATE
    CANDIDATE_SET
    FEASIBLE_CANDIDATE
    INFEASIBLE_CANDIDATE
    PARTIAL_SOLUTION
    COMPLETE_SOLUTION
    OPTIMAL_SOLUTION
    LOCAL_CHOICE
    GREEDY_CHOICE
    SELECTION_FUNCTION
    FEASIBILITY_FUNCTION
    OBJECTIVE_FUNCTION
    SOLUTION_FUNCTION
    COST
    VALUE
    WEIGHT
    PROFIT
    PRIORITY
    CONSTRAINT
    FEASIBILITY
    GREEDY_CHOICE_PROPERTY
    OPTIMAL_SUBSTRUCTURE
    EXCHANGE_ARGUMENT
    CUT_PROPERTY
    SAFE_EDGE
    SAFE_CHOICE
    MATROID
    INDEPENDENT_SET
    ACTIVITY_SELECTION
    FRACTIONAL_KNAPSACK
    HUFFMAN_CODING
    DIJKSTRA_ALGORITHM
    PRIM_ALGORITHM
    KRUSKAL_ALGORITHM
    MINIMUM_SPANNING_TREE
    SHORTEST_PATH
    INTERVAL_SCHEDULING
    COIN_CHANGE
    STATE
    STATE_TRANSITION
    ITERATION
    ORDERING
    SORTED_CANDIDATES
    PRIORITY_QUEUE
    DISJOINT_SET
    PRECONDITION
    POSTCONDITION
    INVARIANT
    CORRECTNESS
    TERMINATION
    COUNTEREXAMPLE
    APPROXIMATION
    INPUT_SIZE
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    CONFIGURATION
    BENCHMARK
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    SOLVES
    ACCEPTS
    PRODUCES
    HAS_CANDIDATE
    HAS_CANDIDATE_SET
    SELECTS
    CHOOSES
    HAS_LOCAL_CHOICE
    HAS_GREEDY_CHOICE
    HAS_SELECTION_FUNCTION
    CHECKS_FEASIBILITY
    HAS_FEASIBILITY_FUNCTION
    HAS_OBJECTIVE
    HAS_SOLUTION_FUNCTION
    HAS_COST
    HAS_VALUE
    HAS_WEIGHT
    HAS_PRIORITY
    SATISFIES
    VIOLATES
    EXTENDS
    PRESERVES
    HAS_GREEDY_CHOICE_PROPERTY
    HAS_OPTIMAL_SUBSTRUCTURE
    PROVEN_BY
    USES_EXCHANGE_ARGUMENT
    USES_CUT_PROPERTY
    ORDERS
    SORTS
    ENQUEUES
    EXTRACTS
    UNIONS
    FINDS
    HAS_STATE
    TRANSITIONS_TO
    ITERATES
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    IMPLEMENTED_BY
    EXECUTED_BY
    BENCHMARKED_BY
    HAS_CONFIGURATION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    GREEDY_ALGORITHM_SPECIFICATIONS
    PROBLEM_DEFINITIONS
    PSEUDOCODE
    SOURCE_CODE
    CANDIDATE_DATA
    SELECTION_FUNCTIONS
    FEASIBILITY_FUNCTIONS
    OBJECTIVE_FUNCTIONS
    CONSTRAINT_DATA
    ORDERING_DATA
    GREEDY_CHOICE_PROOFS
    OPTIMAL_SUBSTRUCTURE_PROOFS
    EXCHANGE_ARGUMENTS
    CUT_PROPERTY_EVIDENCE
    EXECUTION_TRACES
    COUNTEREXAMPLES
    COMPLEXITY_ANALYSES
    BENCHMARK_DATA
    IMPLEMENTATION_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_GREEDY_ALGORITHM_IDENTIFIERS
    NORMALISE_PROBLEM_IDENTIFIERS
    NORMALISE_CANDIDATE_IDENTIFIERS
    NORMALISE_SELECTION_FUNCTIONS
    NORMALISE_FEASIBILITY_FUNCTIONS
    NORMALISE_OBJECTIVE_FUNCTIONS
    NORMALISE_CONSTRAINTS
    NORMALISE_ORDERING_AND_PRIORITY
    NORMALISE_GREEDY_CHOICE_TERMS
    NORMALISE_OPTIMALITY_TERMS
    NORMALISE_COMPLEXITY_NOTATION
    RESOLVE_ALGORITHM_CANDIDATE_AND_SOLUTION_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS GREEDY_ALGORITHM_PIPELINE {
    PROBLEM_INSTANCE
      -> CANDIDATE_SET
      -> INITIAL_PARTIAL_SOLUTION
      -> SELECT_BEST_LOCAL_CANDIDATE
      -> FEASIBILITY_CHECK
      -> ACCEPT_OR_REJECT
      -> UPDATE_PARTIAL_SOLUTION
      -> REPEAT
      -> COMPLETE_SOLUTION
      -> OBJECTIVE_EVALUATION
      -> CORRECTNESS_OR_OPTIMALITY_VALIDATION
  }

  PROCESS SELECTION_REASONING {
    CURRENT_STATE + CANDIDATE_SET
      -> AVAILABLE_CANDIDATES

    AVAILABLE_CANDIDATES
      -> SELECTION_FUNCTION

    SELECTION_FUNCTION
      -> LOCALLY_PREFERRED_CANDIDATE

    LOCALLY_PREFERRED_CANDIDATE
      -> GREEDY_CHOICE
  }

  PROCESS FEASIBILITY_REASONING {
    PARTIAL_SOLUTION + GREEDY_CHOICE
      -> FEASIBILITY_FUNCTION

    CONSTRAINTS_SATISFIED
      -> ACCEPT_CHOICE

    CONSTRAINTS_VIOLATED
      -> REJECT_CHOICE

    ACCEPTED_CHOICE
      -> EXTENDED_PARTIAL_SOLUTION
  }

  PROCESS ITERATIVE_REASONING {
    PARTIAL_SOLUTION(T1)
      -> GREEDY_CHOICE

    GREEDY_CHOICE
      -> ACCEPT_OR_REJECT

    RESULT
      -> PARTIAL_SOLUTION(T2)

    TERMINATION_CONDITION_FALSE
      -> NEXT_ITERATION

    TERMINATION_CONDITION_TRUE
      -> COMPLETE_SOLUTION
  }

  PROCESS GREEDY_CHOICE_PROPERTY_REASONING {
    PROBLEM_INSTANCE
      -> CANDIDATE_GREEDY_CHOICE

    GREEDY_CHOICE
      -> REDUCED_SUBPROBLEM

    IF SOME_GLOBAL_OPTIMUM_CONTAINS_GREEDY_CHOICE
      -> SAFE_CHOICE_EVIDENCE

    SAFE_CHOICE_EVIDENCE
      -> GREEDY_CHOICE_PROPERTY
  }

  PROCESS OPTIMAL_SUBSTRUCTURE_REASONING {
    OPTIMAL_SOLUTION
      -> GREEDY_CHOICE + RESIDUAL_SOLUTION

    RESIDUAL_SOLUTION
      -> SUBPROBLEM

    IF RESIDUAL_SOLUTION_IS_OPTIMAL_FOR_SUBPROBLEM
      -> OPTIMAL_SUBSTRUCTURE_EVIDENCE
  }

  PROCESS EXCHANGE_ARGUMENT_REASONING {
    ARBITRARY_OPTIMAL_SOLUTION
      -> COMPARE_WITH_GREEDY_CHOICE

    OPTIMAL_SOLUTION_LACKS_GREEDY_CHOICE
      -> IDENTIFY_EXCHANGE

    EXCHANGE
      -> REPLACE_ALTERNATIVE_WITH_GREEDY_CHOICE

    IF FEASIBILITY_PRESERVED_AND_OBJECTIVE_NOT_WORSENED
      -> OPTIMAL_SOLUTION_CONTAINING_GREEDY_CHOICE

    RESULT
      -> GREEDY_SAFETY_EVIDENCE
  }

  PROCESS CUT_PROPERTY_REASONING {
    PARTIAL_SPANNING_STRUCTURE
      -> VALID_CUT

    CROSSING_EDGES
      -> MINIMUM_WEIGHT_SAFE_EDGE

    SAFE_EDGE
      -> EXTEND_PARTIAL_SOLUTION

    REPEAT
      -> MINIMUM_SPANNING_STRUCTURE
  }

  PROCESS ORDERING_REASONING {
    CANDIDATE_SET
      -> PRIORITY_OR_SORT_KEY

    PRIORITY_OR_SORT_KEY
      -> ORDERED_CANDIDATES

    ORDERED_CANDIDATES
      -> GREEDY_SELECTION_SEQUENCE
  }

  PROCESS CORRECTNESS_REASONING {
    PRECONDITIONS
      -> VALID_PROBLEM_INSTANCE

    GREEDY_CHOICE_PROPERTY
      + OPTIMAL_SUBSTRUCTURE
      -> OPTIMALITY_PROOF_FRAMEWORK

    INVARIANT
      -> PRESERVED_AFTER_EACH_ACCEPTED_CHOICE

    TERMINATION
      -> COMPLETE_FEASIBLE_SOLUTION

    PROOF_FRAMEWORK + COMPLETE_SOLUTION
      -> CORRECTNESS_OR_OPTIMALITY_EVIDENCE
  }

  PROCESS COMPLEXITY_REASONING {
    INPUT_SIZE
      -> CANDIDATE_COUNT

    CANDIDATE_ORDERING
      -> SORT_OR_PRIORITY_COST

    EACH_ITERATION
      -> SELECTION_COST + FEASIBILITY_COST + UPDATE_COST

    TOTAL_ITERATIONS
      -> TOTAL_TIME_COMPLEXITY

    CANDIDATE_STORAGE + PARTIAL_SOLUTION + AUXILIARY_STRUCTURES
      -> SPACE_COMPLEXITY
  }

  RULES {
    IF GREEDY_ALGORITHM_IS_ASSERTED_OPTIMAL
    THEN REQUIRE PROBLEM_SPECIFIC_OPTIMALITY_EVIDENCE

    IF LOCALLY_BEST_CHOICE_IS_SELECTED
    THEN DO_NOT AUTOMATICALLY_ASSERT GLOBAL_OPTIMALITY

    IF GREEDY_CHOICE_PROPERTY_IS_ASSERTED
    THEN REQUIRE PROOF_EXCHANGE_ARGUMENT_CUT_PROPERTY_OR_EQUIVALENT_EVIDENCE

    IF OPTIMAL_SUBSTRUCTURE_IS_ASSERTED
    THEN DISTINGUISH IT_FROM_GREEDY_CHOICE_PROPERTY

    IF DIJKSTRA_IS_CLASSIFIED_AS_GREEDY
    THEN PRESERVE NONNEGATIVE_EDGE_WEIGHT_PRECONDITION_FOR_STANDARD_SHORTEST_PATH_CORRECTNESS

    IF FRACTIONAL_KNAPSACK_IS_ANALYSED
    THEN DISTINGUISH IT_FROM_ZERO_ONE_KNAPSACK

    IF COUNTEREXAMPLE_EXISTS_FOR_GREEDY_RULE
    THEN DO_NOT ASSERT UNIVERSAL_OPTIMALITY

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND GREEDY_ALGORITHM_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        CANDIDATE_SET_COMPLETENESS,
        SELECTION_FUNCTION_CERTAINTY,
        FEASIBILITY_FUNCTION_CERTAINTY,
        OBJECTIVE_FUNCTION_CERTAINTY,
        GREEDY_CHOICE_EVIDENCE_QUALITY,
        OPTIMALITY_PROOF_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF GREEDY_CHOICE_PROPERTY_IS_UNPROVEN
    THEN REDUCE_OPTIMALITY_CONFIDENCE

    IF OBJECTIVE_OR_CONSTRAINTS_ARE_INCOMPLETE
    THEN REDUCE_SOLUTION_QUALITY_CONFIDENCE

    IF FORMAL_PROOF_AND_EXECUTION_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        GREEDY_ALGORITHM_IDENTIFIER,
        PROBLEM_DEFINITION,
        SELECTION_FUNCTION,
        FEASIBILITY_FUNCTION,
        OBJECTIVE_FUNCTION,
        CONFIGURATION
      )

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

  REASONING_CONSTRAINTS {
    GREEDY_ALGORITHM != DYNAMIC_PROGRAMMING
    GREEDY_ALGORITHM != HEURISTIC_AS_IDENTICAL_CONCEPT
    LOCAL_OPTIMUM != GLOBAL_OPTIMUM
    GREEDY_CHOICE_PROPERTY != OPTIMAL_SUBSTRUCTURE
    FEASIBLE_SOLUTION != OPTIMAL_SOLUTION
    SELECTION_FUNCTION != OBJECTIVE_FUNCTION
    FEASIBILITY_FUNCTION != OBJECTIVE_FUNCTION
    EXCHANGE_ARGUMENT != GREEDY_ALGORITHM
    CUT_PROPERTY != UNIVERSAL_GREEDY_PROPERTY
    FRACTIONAL_KNAPSACK != ZERO_ONE_KNAPSACK
    DIJKSTRA_CORRECTNESS_REQUIRES_RELEVANT_WEIGHT_PRECONDITIONS
    COIN_CHANGE_GREEDY_OPTIMALITY_DEPENDS_ON_COIN_SYSTEM
    COUNTEREXAMPLE_INVALIDATES_UNIVERSAL_OPTIMALITY_CLAIM_FOR_THAT_RULE_AND_DOMAIN
    TIME_COMPLEXITY_DEPENDS_ON_SELECTION_ORDERING_AND_AUXILIARY_DATA_STRUCTURES
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_GREEDY_ALGORITHM_IDENTIFIER
    CHECK_PROBLEM_DEFINITION
    CHECK_CANDIDATE_SET
    CHECK_SELECTION_FUNCTION
    CHECK_FEASIBILITY_FUNCTION
    CHECK_OBJECTIVE_FUNCTION
    CHECK_CONSTRAINTS
    CHECK_GREEDY_CHOICE_SEQUENCE
    CHECK_PARTIAL_SOLUTION_STATES
    CHECK_TERMINATION
    CHECK_GREEDY_CHOICE_PROPERTY_IF_CLAIMED
    CHECK_OPTIMAL_SUBSTRUCTURE_IF_CLAIMED
    CHECK_EXCHANGE_ARGUMENT_OR_OTHER_PROOF
    CHECK_COUNTEREXAMPLES
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_COMPLEXITY_CONTEXT
    CHECK_IMPLEMENTATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_GREEDY_ALGORITHM_ENTITIES
    CANDIDATE_RELATIONS
    SELECTION_RELATIONS
    FEASIBILITY_RELATIONS
    OBJECTIVE_RELATIONS
    GREEDY_CHOICE_RELATIONS
    PARTIAL_SOLUTION_STATE_TRANSITIONS
    GREEDY_CHOICE_PROPERTY_RELATIONS
    OPTIMAL_SUBSTRUCTURE_RELATIONS
    EXCHANGE_ARGUMENT_RELATIONS
    CUT_PROPERTY_RELATIONS
    CORRECTNESS_AND_OPTIMALITY_RELATIONS
    COUNTEREXAMPLE_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    IMPLEMENTATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON PROBLEM_GREEDY_RULE_OR_CONSTRAINT_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_CANDIDATE_AND_SOLUTION_IDENTITIES
      UPDATE_CANDIDATE_SET
      UPDATE_SELECTION_AND_FEASIBILITY_FUNCTIONS
      UPDATE_OBJECTIVE_AND_CONSTRAINTS
      REASSESS_GREEDY_CHOICE_PROPERTY
      REASSESS_OPTIMALITY_AND_CORRECTNESS
      REASSESS_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_PROOF_OR_COUNTEREXAMPLE {
      LINK_EVIDENCE
      UPDATE_EXECUTION_TRACE
      UPDATE_PROOF_RELATIONS
      UPDATE_COUNTEREXAMPLE_RELATIONS
      REASSESS_OPTIMALITY_CLAIMS
      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_GREEDY_ALGORITHM
      BY_PROBLEM
      BY_CANDIDATE
      BY_SELECTION_FUNCTION
      BY_FEASIBILITY_FUNCTION
      BY_OBJECTIVE
      BY_GREEDY_CHOICE
      BY_PARTIAL_SOLUTION
      BY_PROOF
      BY_COUNTEREXAMPLE
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_GREEDY_SELECTION
      ANALYSE_FEASIBILITY
      TRACE_GREEDY_ITERATIONS
      ANALYSE_GREEDY_CHOICE_PROPERTY
      ANALYSE_OPTIMAL_SUBSTRUCTURE
      ANALYSE_EXCHANGE_ARGUMENTS
      ANALYSE_CUT_PROPERTY
      ANALYSE_CORRECTNESS_AND_OPTIMALITY
      ANALYSE_COUNTEREXAMPLES
      ANALYSE_COMPLEXITY
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_GREEDY_ALGORITHM_FROM_DYNAMIC_PROGRAMMING_AND_GENERIC_HEURISTICS
      DISTINGUISH_LOCAL_CHOICE_FROM_GLOBAL_OPTIMALITY
      PRESERVE_PROBLEM_CANDIDATE_SELECTION_FEASIBILITY_OBJECTIVE_CONSTRAINT_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT
      REQUIRE_PROBLEM_SPECIFIC_EVIDENCE_FOR_OPTIMALITY
      PRESERVE_COUNTEREXAMPLES_AND_UNCERTAINTY
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_GREEDY_OPTIMALITY_INFERENCE
    }
  }

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

END FLOW