Algorithms

AI SEARCH

FLOW ALGEBRA — ALGORITHMS
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms.html

FLOW ALGORITHMS {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Algorithms"
    PURPOSE = "Formalise algorithms, inputs, outputs, computational steps, control structures, correctness, complexity, algorithmic paradigms, optimisation, execution and semantic relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    ALGORITHM
    COMPUTATIONAL_PROCEDURE
    PROCEDURE
    INPUT
    OUTPUT
    PARAMETER
    PRECONDITION
    POSTCONDITION
    STATE
    STEP
    OPERATION
    INSTRUCTION
    DECISION
    BRANCH
    LOOP
    ITERATION
    RECURSION
    BASE_CASE
    RECURSIVE_CASE
    TERMINATION_CONDITION
    INVARIANT
    LOOP_INVARIANT
    RECURSIVE_INVARIANT
    CORRECTNESS
    PARTIAL_CORRECTNESS
    TOTAL_CORRECTNESS
    TERMINATION
    PROOF
    COMPLEXITY
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    BEST_CASE
    AVERAGE_CASE
    WORST_CASE
    ASYMPTOTIC_COMPLEXITY
    BIG_O
    BIG_OMEGA
    BIG_THETA
    SEARCH_ALGORITHM
    SORTING_ALGORITHM
    GRAPH_ALGORITHM
    STRING_ALGORITHM
    NUMERICAL_ALGORITHM
    OPTIMISATION_ALGORITHM
    RANDOMISED_ALGORITHM
    DETERMINISTIC_ALGORITHM
    APPROXIMATION_ALGORITHM
    ONLINE_ALGORITHM
    OFFLINE_ALGORITHM
    PARALLEL_ALGORITHM
    DISTRIBUTED_ALGORITHM
    GREEDY_ALGORITHM
    DIVIDE_AND_CONQUER
    DYNAMIC_PROGRAMMING
    BACKTRACKING
    BRANCH_AND_BOUND
    BRUTE_FORCE
    HEURISTIC
    METAHEURISTIC
    DATA_STRUCTURE
    SEARCH_SPACE
    SOLUTION
    CANDIDATE_SOLUTION
    OBJECTIVE_FUNCTION
    CONSTRAINT
    COST
    RESOURCE
    RANDOM_VARIABLE
    RANDOM_SEED
    PROBABILITY
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    PROGRAMMING_LANGUAGE
    RUNTIME
    CONFIGURATION
    BENCHMARK
    PERFORMANCE_METRIC
    ERROR
    FAILURE
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    ACCEPTS
    PRODUCES
    HAS_PARAMETER
    REQUIRES
    ENSURES
    HAS_STEP
    PRECEDES
    FOLLOWS
    BRANCHES_TO
    ITERATES
    RECURSES_ON
    TERMINATES_AT
    MAINTAINS
    HAS_INVARIANT
    SOLVES
    SEARCHES
    SORTS
    TRAVERSES
    OPTIMISES
    APPROXIMATES
    USES
    DEPENDS_ON
    DECOMPOSES_INTO
    COMBINES
    SELECTS
    EXPLORES
    PRUNES
    MEMOISES
    TABULATES
    HAS_OBJECTIVE
    HAS_CONSTRAINT
    HAS_COST
    HAS_COMPLEXITY
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    PROVEN_CORRECT_BY
    IMPLEMENTED_BY
    EXECUTED_BY
    BENCHMARKED_BY
    HAS_CONFIGURATION
    HAS_STATE
    TRANSITIONS_TO
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    ALGORITHM_SPECIFICATIONS
    PSEUDOCODE
    SOURCE_CODE
    INPUT_DEFINITIONS
    OUTPUT_DEFINITIONS
    PRECONDITIONS
    POSTCONDITIONS
    INVARIANT_DEFINITIONS
    CORRECTNESS_PROOFS
    COMPLEXITY_ANALYSES
    EXECUTION_TRACES
    BENCHMARK_DATA
    DATA_STRUCTURE_CONTEXT
    RANDOMISED_EXECUTION_DATA
    OPTIMISATION_DATA
    CONFIGURATION_DATA
    LANGUAGE_AND_RUNTIME_CONTEXT
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_ALGORITHM_IDENTIFIERS
    NORMALISE_ALGORITHM_NAMES
    NORMALISE_INPUT_AND_OUTPUT_TYPES
    NORMALISE_PARAMETER_NAMES
    NORMALISE_OPERATION_NAMES
    NORMALISE_CONTROL_STRUCTURES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_ASYMPTOTIC_BOUNDS
    NORMALISE_ALGORITHMIC_PARADIGM_NAMES
    NORMALISE_OBJECTIVE_AND_CONSTRAINT_TERMS
    NORMALISE_RANDOM_SEEDS_AND_PROBABILITY_CONTEXT
    NORMALISE_BENCHMARK_UNITS
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_ALGORITHM_AND_IMPLEMENTATION_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS ALGORITHM_REASONING_PIPELINE {
    ALGORITHM_REFERENCE
      -> ALGORITHM_IDENTIFICATION
      -> INPUT_OUTPUT_AND_CONTRACT_MAPPING
      -> STEP_AND_CONTROL_FLOW_MAPPING
      -> PARADIGM_CLASSIFICATION
      -> CORRECTNESS_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> EXECUTION_AND_BENCHMARK_MAPPING
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS EXECUTION_REASONING {
    INPUT
      -> PRECONDITION_CHECK

    VALID_INPUT
      -> INITIAL_STATE

    INITIAL_STATE
      -> ALGORITHM_STEPS

    EACH_STEP
      -> STATE_TRANSITION

    TERMINATION_CONDITION
      -> FINAL_STATE

    FINAL_STATE
      -> OUTPUT

    OUTPUT
      -> POSTCONDITION_CHECK
  }

  PROCESS ITERATIVE_REASONING {
    LOOP
      -> INITIALISATION

    INITIALISATION
      -> LOOP_CONDITION

    CONDITION_TRUE
      -> LOOP_BODY

    LOOP_BODY
      -> STATE_UPDATE
      -> LOOP_INVARIANT_CHECK
      -> LOOP_CONDITION

    CONDITION_FALSE
      -> LOOP_EXIT
  }

  PROCESS RECURSIVE_REASONING {
    PROBLEM_INSTANCE
      -> BASE_CASE_CHECK

    BASE_CASE
      -> DIRECT_RESULT

    RECURSIVE_CASE
      -> SMALLER_OR_TRANSFORMED_SUBPROBLEM

    SUBPROBLEM
      -> RECURSIVE_CALL

    RECURSIVE_RESULTS
      -> COMBINATION

    COMBINATION
      -> RESULT
  }

  PROCESS DIVIDE_AND_CONQUER_REASONING {
    PROBLEM
      -> DIVIDE

    DIVIDE
      -> SUBPROBLEMS

    SUBPROBLEMS
      -> SOLVE_RECURSIVELY_OR_DIRECTLY

    SUBPROBLEM_SOLUTIONS
      -> COMBINE

    COMBINE
      -> PROBLEM_SOLUTION
  }

  PROCESS GREEDY_REASONING {
    PROBLEM_STATE
      -> FEASIBLE_CHOICES

    FEASIBLE_CHOICES
      -> GREEDY_SELECTION_RULE

    SELECTED_CHOICE
      -> UPDATED_STATE

    UPDATED_STATE
      -> REPEAT_UNTIL_SOLUTION

    RESULT
      -> OPTIMALITY_OR_APPROXIMATION_ANALYSIS
  }

  PROCESS DYNAMIC_PROGRAMMING_REASONING {
    PROBLEM
      -> OVERLAPPING_SUBPROBLEMS

    SUBPROBLEMS
      -> RECURRENCE_RELATION

    RECURRENCE_RELATION
      -> MEMOISATION_OR_TABULATION

    STORED_SUBPROBLEM_SOLUTIONS
      -> COMBINE

    COMBINE
      -> FINAL_SOLUTION
  }

  PROCESS BACKTRACKING_REASONING {
    SEARCH_STATE
      -> CANDIDATE_CHOICES

    CANDIDATE_CHOICE
      -> CONSTRAINT_CHECK

    VALID_PARTIAL_SOLUTION
      -> EXTEND_SEARCH

    INVALID_PARTIAL_SOLUTION
      -> PRUNE

    DEAD_END
      -> BACKTRACK

    COMPLETE_VALID_STATE
      -> SOLUTION
  }

  PROCESS RANDOMISED_REASONING {
    INPUT + RANDOM_SOURCE
      -> RANDOM_DECISION

    RANDOM_DECISION
      -> EXECUTION_PATH

    EXECUTION_PATH
      -> OUTPUT_OR_COST

    REPEATED_RUNS_OR_PROBABILITY_MODEL
      -> EXPECTED_BEHAVIOUR_AND_ERROR_BOUNDS
  }

  PROCESS CORRECTNESS_REASONING {
    PRECONDITION
      -> INITIAL_VALID_STATE

    ALGORITHM_STEP
      -> INVARIANT_PRESERVATION

    INVARIANT + TERMINATION
      -> POSTCONDITION

    POSTCONDITION
      -> CORRECTNESS_CLAIM

    TERMINATION_PROOF + PARTIAL_CORRECTNESS
      -> TOTAL_CORRECTNESS
  }

  PROCESS COMPLEXITY_REASONING {
    ALGORITHM + INPUT_SIZE_MODEL
      -> BASIC_OPERATION_COUNT_OR_RESOURCE_MODEL

    RESOURCE_MODEL
      -> COST_FUNCTION

    COST_FUNCTION
      -> BEST_AVERAGE_OR_WORST_CASE

    COST_FUNCTION
      -> ASYMPTOTIC_BOUND

    MEMORY_REQUIREMENTS
      -> SPACE_COMPLEXITY
  }

  PROCESS BENCHMARK_REASONING {
    IMPLEMENTATION + INPUT_DATASET + ENVIRONMENT
      -> EXECUTION

    EXECUTION
      -> WALL_CLOCK_TIME
      -> MEMORY_USAGE
      -> THROUGHPUT_OR_OTHER_METRICS

    REPEATED_EXECUTIONS
      -> PERFORMANCE_DISTRIBUTION

    PERFORMANCE_DISTRIBUTION
      -> EMPIRICAL_PROFILE
  }

  RULES {
    IF ALGORITHM_IS_ASSERTED_TO_SOLVE_PROBLEM
    THEN PRESERVE INPUT_DOMAIN_OUTPUT_CONTRACT_AND_PRECONDITIONS

    IF CORRECTNESS_IS_ASSERTED
    THEN DISTINGUISH PARTIAL_CORRECTNESS_FROM_TOTAL_CORRECTNESS

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE INPUT_SIZE_MODEL_CASE_COST_MODEL_AND_ALGORITHM_VARIANT

    IF BENCHMARK_RESULT_IS_REPORTED
    THEN PRESERVE IMPLEMENTATION_HARDWARE_RUNTIME_DATASET_AND_CONFIGURATION

    IF RANDOMISED_ALGORITHM_IS_ANALYSED
    THEN PRESERVE RANDOMNESS_MODEL_SEED_OR_DISTRIBUTIONAL_CONTEXT

    IF GREEDY_ALGORITHM_RETURNS_SOLUTION
    THEN DO_NOT ASSERT GLOBAL_OPTIMALITY_WITHOUT_PROOF_OR_KNOWN_PROPERTY

    IF APPROXIMATION_ALGORITHM_IS_USED
    THEN PRESERVE APPROXIMATION_GUARANTEE_IF_AVAILABLE

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND ALGORITHM_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        INPUT_OUTPUT_CONTRACT_COMPLETENESS,
        CONTROL_FLOW_COMPLETENESS,
        CORRECTNESS_EVIDENCE_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        IMPLEMENTATION_CERTAINTY,
        BENCHMARK_REPRODUCIBILITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF PRECONDITIONS_OR_INPUT_MODEL_ARE_UNKNOWN
    THEN REDUCE_CORRECTNESS_AND_COMPLEXITY_CONFIDENCE

    IF ONLY_EMPIRICAL_RESULTS_EXIST
    THEN DO_NOT TREAT_AS_FORMAL_COMPLEXITY_PROOF

    IF FORMAL_PROOF_AND_REPRODUCIBLE_EXECUTION_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ALGORITHM_IDENTIFIER,
        ALGORITHM_VARIANT,
        INPUT_OUTPUT_CONTRACT,
        PARADIGM,
        CONFIGURATION
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    ALGORITHM != IMPLEMENTATION
    ALGORITHM != PROGRAM
    INPUT != PARAMETER
    OUTPUT != POSTCONDITION
    ITERATION != RECURSION
    PARTIAL_CORRECTNESS != TOTAL_CORRECTNESS
    TERMINATION != CORRECTNESS_ALONE
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    SPACE_COMPLEXITY != RAW_MEMORY_MEASUREMENT_WITHOUT_INPUT_MODEL
    BIG_O != EXACT_RUNTIME
    BIG_O != BIG_THETA
    AVERAGE_CASE != EXPECTED_CASE_WITHOUT_DEFINED_DISTRIBUTION
    GREEDY_SOLUTION != NECESSARILY_GLOBAL_OPTIMUM
    HEURISTIC_RESULT != GUARANTEED_OPTIMUM
    APPROXIMATION != HEURISTIC_AS_IDENTICAL_CONCEPT
    RANDOMISED != NONDETERMINISTIC_AS_IDENTICAL_COMPUTATIONAL_MODEL
    EMPIRICAL_BENCHMARK != FORMAL_COMPLEXITY_ANALYSIS
    ALGORITHM_PERFORMANCE_DEPENDS_ON_INPUT_DISTRIBUTION_IMPLEMENTATION_AND_ENVIRONMENT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_ALGORITHM_IDENTIFIER
    CHECK_INPUT_AND_OUTPUT_TYPES
    CHECK_PRECONDITIONS
    CHECK_POSTCONDITIONS
    CHECK_STEPS_AND_CONTROL_FLOW
    CHECK_TERMINATION_CONDITION
    CHECK_INVARIANTS
    CHECK_ALGORITHMIC_PARADIGM
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_COMPLEXITY_CONTEXT
    CHECK_RANDOMNESS_CONTEXT_IF_APPLICABLE
    CHECK_OPTIMISATION_OBJECTIVE_AND_CONSTRAINTS_IF_APPLICABLE
    CHECK_IMPLEMENTATION
    CHECK_BENCHMARK_CONTEXT
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_ALGORITHM_ENTITIES
    INPUT_OUTPUT_RELATIONS
    PRECONDITION_AND_POSTCONDITION_RELATIONS
    STEP_AND_CONTROL_FLOW_RELATIONS
    ITERATION_RELATIONS
    RECURSION_RELATIONS
    PARADIGM_RELATIONS
    CORRECTNESS_RELATIONS
    TERMINATION_RELATIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    OPTIMISATION_RELATIONS
    RANDOMISED_ALGORITHM_RELATIONS
    IMPLEMENTATION_RELATIONS
    BENCHMARK_AND_PERFORMANCE_RELATIONS
    EXECUTION_STATE_TRANSITIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON ALGORITHM_SPECIFICATION_OR_IMPLEMENTATION_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_AND_IMPLEMENTATION_IDENTITIES
      UPDATE_INPUT_OUTPUT_CONTRACT
      UPDATE_CONTROL_FLOW
      RECHECK_INVARIANTS_AND_TERMINATION
      REASSESS_CORRECTNESS
      REASSESS_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_OR_BENCHMARK_DATA {
      LINK_EVIDENCE
      UPDATE_EXECUTION_RELATIONS
      UPDATE_EMPIRICAL_PERFORMANCE_PROFILE
      COMPARE_WITH_COMPLEXITY_EXPECTATIONS
      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_ALGORITHM
      BY_ALGORITHM_TYPE
      BY_INPUT
      BY_OUTPUT
      BY_OPERATION
      BY_PARADIGM
      BY_INVARIANT
      BY_CORRECTNESS
      BY_COMPLEXITY
      BY_IMPLEMENTATION
      BY_BENCHMARK
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_ALGORITHM_EXECUTION
      ANALYSE_ITERATION
      ANALYSE_RECURSION
      ANALYSE_DIVIDE_AND_CONQUER
      ANALYSE_GREEDY_METHODS
      ANALYSE_DYNAMIC_PROGRAMMING
      ANALYSE_BACKTRACKING
      ANALYSE_RANDOMISED_ALGORITHMS
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLEXITY
      ANALYSE_BENCHMARKS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_ALGORITHM_FROM_IMPLEMENTATION
      DISTINGUISH_FORMAL_COMPLEXITY_FROM_EMPIRICAL_RUNTIME
      PRESERVE_INPUT_MODEL_CASE_VARIANT_IMPLEMENTATION_LANGUAGE_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_PARTIAL_FROM_TOTAL_CORRECTNESS
      PRESERVE_RANDOMNESS_OPTIMISATION_AND_APPROXIMATION_CONTEXT
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_ALGORITHM_INFERENCE
    }
  }

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

END FLOW