Algorithm Ontology

AI SEARCH

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

FLOW ALGORITHM_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Algorithm Ontology"
    PURPOSE = "Formalise algorithms as computational procedures, including inputs, outputs, steps, control flow, state transitions, correctness, termination, complexity, implementations and execution evidence."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    ALGORITHM
    ALGORITHM_INSTANCE
    ALGORITHM_VARIANT
    COMPUTATIONAL_PROCEDURE
    PROBLEM
    PROBLEM_INSTANCE
    INPUT
    INPUT_DOMAIN
    OUTPUT
    OUTPUT_DOMAIN
    PARAMETER
    PRECONDITION
    POSTCONDITION
    STEP
    OPERATION
    INSTRUCTION
    STATE
    INITIAL_STATE
    INTERMEDIATE_STATE
    FINAL_STATE
    STATE_TRANSITION
    SEQUENCE
    BRANCH
    CONDITION
    LOOP
    ITERATION
    RECURSION
    RECURSIVE_CALL
    BASE_CASE
    TERMINATION_CONDITION
    INVARIANT
    LOOP_INVARIANT
    CORRECTNESS
    PARTIAL_CORRECTNESS
    TOTAL_CORRECTNESS
    TERMINATION
    PROOF
    COMPLEXITY
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    BEST_CASE
    AVERAGE_CASE
    WORST_CASE
    ASYMPTOTIC_BOUND
    BIG_O
    BIG_OMEGA
    BIG_THETA
    COST_MODEL
    INPUT_SIZE
    DATA_STRUCTURE
    DETERMINISTIC_ALGORITHM
    RANDOMISED_ALGORITHM
    EXACT_ALGORITHM
    APPROXIMATION_ALGORITHM
    HEURISTIC_ALGORITHM
    ITERATIVE_ALGORITHM
    RECURSIVE_ALGORITHM
    SEQUENTIAL_ALGORITHM
    PARALLEL_ALGORITHM
    DISTRIBUTED_ALGORITHM
    ONLINE_ALGORITHM
    OFFLINE_ALGORITHM
    IMPLEMENTATION
    SOURCE_CODE
    PROGRAMMING_LANGUAGE
    RUNTIME
    EXECUTION
    EXECUTION_TRACE
    RESULT
    RANDOM_SOURCE
    RANDOM_SEED
    PROBABILITY_DISTRIBUTION
    BENCHMARK
    PERFORMANCE_METRIC
    CONFIGURATION
    ERROR
    FAILURE
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    VARIANT_OF
    SOLVES
    ACCEPTS
    PRODUCES
    HAS_INPUT_DOMAIN
    HAS_OUTPUT_DOMAIN
    HAS_PARAMETER
    REQUIRES
    ENSURES
    HAS_STEP
    HAS_OPERATION
    PRECEDES
    FOLLOWS
    BRANCHES_TO
    ITERATES
    RECURSES_ON
    HAS_BASE_CASE
    TERMINATES_AT
    HAS_STATE
    TRANSITIONS_TO
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_TERMINATION
    PROVEN_BY
    HAS_COMPLEXITY
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_COST_MODEL
    USES
    DEPENDS_ON
    IMPLEMENTED_BY
    WRITTEN_IN
    EXECUTED_BY
    HAS_EXECUTION
    HAS_TRACE
    RETURNS
    USES_RANDOM_SOURCE
    BENCHMARKED_BY
    HAS_METRIC
    HAS_CONFIGURATION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    ALGORITHM_SPECIFICATIONS
    FORMAL_DEFINITIONS
    PSEUDOCODE
    SOURCE_CODE
    INPUT_OUTPUT_CONTRACTS
    PRECONDITIONS
    POSTCONDITIONS
    CONTROL_FLOW_DATA
    INVARIANT_DEFINITIONS
    CORRECTNESS_PROOFS
    TERMINATION_PROOFS
    COMPLEXITY_ANALYSES
    EXECUTION_TRACES
    BENCHMARK_DATA
    IMPLEMENTATION_DATA
    LANGUAGE_AND_RUNTIME_CONTEXT
    RANDOMNESS_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_ALGORITHM_IDENTIFIERS
    NORMALISE_ALGORITHM_VARIANT_NAMES
    NORMALISE_PROBLEM_IDENTIFIERS
    NORMALISE_INPUT_AND_OUTPUT_TYPES
    NORMALISE_PARAMETER_NAMES
    NORMALISE_STEP_AND_OPERATION_NAMES
    NORMALISE_CONTROL_FLOW_STRUCTURES
    NORMALISE_STATE_IDENTIFIERS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_ASYMPTOTIC_BOUNDS
    NORMALISE_COST_MODELS
    NORMALISE_IMPLEMENTATION_IDENTIFIERS
    NORMALISE_RANDOMNESS_CONTEXT
    NORMALISE_BENCHMARK_UNITS
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_ALGORITHM_VARIANT_AND_IMPLEMENTATION_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS ALGORITHM_REASONING_PIPELINE {
    ALGORITHM_REFERENCE
      -> ALGORITHM_IDENTIFICATION
      -> VARIANT_RESOLUTION
      -> PROBLEM_AND_CONTRACT_MAPPING
      -> STEP_AND_CONTROL_FLOW_MAPPING
      -> STATE_TRANSITION_MAPPING
      -> CORRECTNESS_AND_TERMINATION_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> IMPLEMENTATION_AND_EXECUTION_MAPPING
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS CONTRACT_REASONING {
    PROBLEM_INSTANCE
      -> INPUT

    INPUT
      -> PRECONDITION_CHECK

    VALID_INPUT
      -> ALGORITHM_EXECUTION

    EXECUTION_RESULT
      -> OUTPUT

    OUTPUT
      -> POSTCONDITION_CHECK

    VALID_POSTCONDITION
      -> CONTRACT_SATISFACTION_EVIDENCE
  }

  PROCESS EXECUTION_REASONING {
    INITIAL_STATE
      -> FIRST_STEP

    STEP
      -> OPERATION

    OPERATION
      -> STATE_TRANSITION

    STATE_TRANSITION
      -> NEXT_STATE

    NEXT_STATE
      -> NEXT_STEP_OR_TERMINATION

    TERMINATION
      -> FINAL_STATE
      -> RESULT
  }

  PROCESS BRANCH_REASONING {
    CONDITION
      -> EVALUATION

    TRUE
      -> TRUE_BRANCH

    FALSE
      -> FALSE_BRANCH

    SELECTED_BRANCH
      -> NEXT_STATE
  }

  PROCESS ITERATION_REASONING {
    LOOP
      -> INITIALISATION

    INITIALISATION
      -> CONDITION_CHECK

    CONDITION_TRUE
      -> LOOP_BODY

    LOOP_BODY
      -> STATE_UPDATE
      -> INVARIANT_CHECK
      -> CONDITION_CHECK

    CONDITION_FALSE
      -> LOOP_EXIT
  }

  PROCESS RECURSION_REASONING {
    PROBLEM_INSTANCE
      -> BASE_CASE_CHECK

    BASE_CASE_MATCH
      -> DIRECT_RESULT

    RECURSIVE_CASE
      -> SUBPROBLEM

    SUBPROBLEM
      -> RECURSIVE_CALL

    RECURSIVE_RESULT
      -> COMBINATION_OR_RETURN

    RESULT
      -> CALLER
  }

  PROCESS CORRECTNESS_REASONING {
    PRECONDITION
      -> INITIAL_VALID_STATE

    INITIAL_VALID_STATE
      -> INVARIANT_ESTABLISHMENT

    EACH_STEP_OR_ITERATION
      -> INVARIANT_PRESERVATION

    TERMINATION_STATE + INVARIANT
      -> POSTCONDITION

    POSTCONDITION
      -> PARTIAL_CORRECTNESS_EVIDENCE

    PARTIAL_CORRECTNESS + TERMINATION_PROOF
      -> TOTAL_CORRECTNESS_EVIDENCE
  }

  PROCESS TERMINATION_REASONING {
    EXECUTION
      -> TERMINATION_CONDITION

    ITERATIVE_OR_RECURSIVE_PROCESS
      -> VARIANT_OR_WELL_FOUNDED_MEASURE_IF_AVAILABLE

    MEASURE_DECREASES_OR_PROGRESS_ESTABLISHED
      -> TERMINATION_EVIDENCE

    NONTERMINATING_TRACE_OR_COUNTEREXAMPLE
      -> TERMINATION_CLAIM_CONTRADICTION
  }

  PROCESS COMPLEXITY_REASONING {
    ALGORITHM_VARIANT + INPUT_SIZE_MODEL
      -> COST_MODEL

    COST_MODEL
      -> BASIC_OPERATION_COUNT_OR_RESOURCE_USAGE

    RESOURCE_FUNCTION
      -> BEST_AVERAGE_OR_WORST_CASE

    RESOURCE_FUNCTION
      -> ASYMPTOTIC_BOUND

    AUXILIARY_MEMORY
      -> SPACE_COMPLEXITY
  }

  PROCESS RANDOMISED_REASONING {
    INPUT + RANDOM_SOURCE
      -> RANDOM_CHOICES

    RANDOM_CHOICES
      -> EXECUTION_PATH

    EXECUTION_PATH
      -> RESULT_AND_COST

    DISTRIBUTION_OVER_RANDOM_CHOICES
      -> EXPECTED_RESULT_OR_EXPECTED_COST

    REPEATED_EXECUTIONS
      -> EMPIRICAL_DISTRIBUTION
  }

  PROCESS IMPLEMENTATION_REASONING {
    ALGORITHM
      -> IMPLEMENTATION

    IMPLEMENTATION
      -> PROGRAMMING_LANGUAGE

    IMPLEMENTATION
      -> DATA_STRUCTURES_AND_MACHINE_OPERATIONS

    IMPLEMENTATION + RUNTIME + CONFIGURATION
      -> EXECUTABLE_BEHAVIOUR
  }

  PROCESS BENCHMARK_REASONING {
    IMPLEMENTATION + DATASET + ENVIRONMENT
      -> BENCHMARK_EXECUTION

    BENCHMARK_EXECUTION
      -> TIME_MEMORY_THROUGHPUT_OR_OTHER_METRICS

    REPEATED_RUNS
      -> PERFORMANCE_DISTRIBUTION

    PERFORMANCE_DISTRIBUTION
      -> EMPIRICAL_PERFORMANCE_PROFILE
  }

  RULES {
    IF ALGORITHM_IS_IDENTIFIED
    THEN PRESERVE PROBLEM_INPUT_OUTPUT_AND_VARIANT_CONTEXT

    IF CORRECTNESS_IS_ASSERTED
    THEN PRESERVE PRECONDITIONS_POSTCONDITIONS_AND_PROOF_SCOPE

    IF TOTAL_CORRECTNESS_IS_ASSERTED
    THEN REQUIRE PARTIAL_CORRECTNESS_AND_TERMINATION_EVIDENCE

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE INPUT_SIZE_CASE_COST_MODEL_AND_VARIANT

    IF RANDOMISED_ALGORITHM_IS_ANALYSED
    THEN PRESERVE RANDOMNESS_AND_DISTRIBUTIONAL_CONTEXT

    IF IMPLEMENTATION_IS_BENCHMARKED
    THEN DISTINGUISH EMPIRICAL_PERFORMANCE_FROM_FORMAL_COMPLEXITY

    IF TWO_IMPLEMENTATIONS_DIFFER
    THEN DO_NOT ASSUME DIFFERENT_ABSTRACT_ALGORITHM

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND ALGORITHM_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        VARIANT_CERTAINTY,
        CONTRACT_COMPLETENESS,
        CONTROL_FLOW_COMPLETENESS,
        CORRECTNESS_EVIDENCE_QUALITY,
        TERMINATION_EVIDENCE_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF PRECONDITION_POSTCONDITION_OR_INPUT_MODEL_IS_UNKNOWN
    THEN REDUCE_CORRECTNESS_CONFIDENCE

    IF COST_MODEL_OR_CASE_IS_UNKNOWN
    THEN REDUCE_COMPLEXITY_CONFIDENCE

    IF FORMAL_PROOF_EXECUTION_AND_TEST_EVIDENCE_CONVERGE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ALGORITHM_IDENTIFIER,
        ALGORITHM_VARIANT,
        PROBLEM_DEFINITION,
        INPUT_OUTPUT_CONTRACT,
        COST_MODEL
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    ALGORITHM != IMPLEMENTATION
    ALGORITHM != EXECUTION
    ALGORITHM_VARIANT != IMPLEMENTATION_VARIANT_IN_ALL_CONTEXTS
    INPUT != INPUT_DOMAIN
    OUTPUT != OUTPUT_DOMAIN
    PRECONDITION != INPUT
    POSTCONDITION != OUTPUT
    PARTIAL_CORRECTNESS != TOTAL_CORRECTNESS
    CORRECTNESS != TERMINATION
    TERMINATION != EFFICIENCY
    ITERATION != RECURSION
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    SPACE_COMPLEXITY != RAW_MEMORY_USAGE_WITHOUT_INPUT_MODEL
    BIG_O != BIG_THETA
    ASYMPTOTIC_BOUND != EXACT_COST
    AVERAGE_CASE != EXPECTED_CASE_WITHOUT_DEFINED_DISTRIBUTION
    RANDOMISED_ALGORITHM != NONDETERMINISTIC_ALGORITHM_AS_IDENTICAL_CONCEPT
    BENCHMARK_RESULT != FORMAL_COMPLEXITY_BOUND
    PERFORMANCE_DEPENDS_ON_IMPLEMENTATION_RUNTIME_HARDWARE_INPUT_AND_CONFIGURATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_ALGORITHM_IDENTIFIER
    CHECK_ALGORITHM_VARIANT
    CHECK_PROBLEM_DEFINITION
    CHECK_INPUT_AND_OUTPUT_DOMAINS
    CHECK_PRECONDITIONS
    CHECK_POSTCONDITIONS
    CHECK_STEPS_AND_OPERATIONS
    CHECK_CONTROL_FLOW
    CHECK_STATE_TRANSITIONS
    CHECK_INVARIANTS
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_TERMINATION_EVIDENCE
    CHECK_COMPLEXITY_CONTEXT
    CHECK_RANDOMNESS_CONTEXT_IF_APPLICABLE
    CHECK_IMPLEMENTATION
    CHECK_BENCHMARK_CONTEXT
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_ALGORITHM_ENTITIES
    ALGORITHM_VARIANT_RELATIONS
    PROBLEM_RELATIONS
    INPUT_OUTPUT_CONTRACT_RELATIONS
    STEP_AND_OPERATION_RELATIONS
    CONTROL_FLOW_RELATIONS
    STATE_TRANSITION_RELATIONS
    ITERATION_RELATIONS
    RECURSION_RELATIONS
    INVARIANT_RELATIONS
    CORRECTNESS_RELATIONS
    TERMINATION_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    RANDOMISED_ALGORITHM_RELATIONS
    IMPLEMENTATION_RELATIONS
    EXECUTION_TRACE_RELATIONS
    BENCHMARK_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON ALGORITHM_SPECIFICATION_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_AND_VARIANT_IDENTITIES
      UPDATE_PROBLEM_AND_CONTRACT
      UPDATE_CONTROL_FLOW
      UPDATE_STATE_TRANSITIONS
      RECHECK_CORRECTNESS_AND_TERMINATION
      REASSESS_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON IMPLEMENTATION_EXECUTION_OR_BENCHMARK_CHANGE {
      LINK_EVIDENCE
      UPDATE_IMPLEMENTATION_CONTEXT
      UPDATE_EXECUTION_TRACES
      UPDATE_EMPIRICAL_PERFORMANCE
      COMPARE_WITH_FORMAL_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_ALGORITHM
      BY_VARIANT
      BY_PROBLEM
      BY_INPUT
      BY_OUTPUT
      BY_STEP
      BY_OPERATION
      BY_STATE
      BY_INVARIANT
      BY_CORRECTNESS
      BY_TERMINATION
      BY_COMPLEXITY
      BY_IMPLEMENTATION
      BY_EXECUTION
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_ALGORITHM_CONTRACTS
      TRACE_EXECUTION_STEPS
      ANALYSE_BRANCHES_AND_ITERATION
      ANALYSE_RECURSION
      ANALYSE_CORRECTNESS
      ANALYSE_TERMINATION
      ANALYSE_COMPLEXITY
      ANALYSE_RANDOMISED_BEHAVIOUR
      MAP_IMPLEMENTATIONS
      ANALYSE_BENCHMARKS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_ALGORITHM_IMPLEMENTATION_AND_EXECUTION
      DISTINGUISH_PARTIAL_CORRECTNESS_TOTAL_CORRECTNESS_AND_TERMINATION
      PRESERVE_PROBLEM_CONTRACT_VARIANT_COST_MODEL_IMPLEMENTATION_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_FORMAL_COMPLEXITY_FROM_EMPIRICAL_PERFORMANCE
      PRESERVE_RANDOMNESS_CONTEXT
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_ALGORITHM_INFERENCE
    }
  }

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

END FLOW