Searching Algorithm Ontology

AI SEARCH

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

FLOW SEARCHING_ALGORITHM_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Searching Algorithm Ontology"
    PURPOSE = "Formalise searching algorithms, search targets, search spaces, predicates, comparisons, traversal strategies, results, correctness, termination, complexity and execution evidence."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    SEARCHING_ALGORITHM
    SEARCH_ALGORITHM
    LINEAR_SEARCH
    SEQUENTIAL_SEARCH
    BINARY_SEARCH
    JUMP_SEARCH
    INTERPOLATION_SEARCH
    EXPONENTIAL_SEARCH
    FIBONACCI_SEARCH
    HASH_LOOKUP
    TREE_SEARCH
    BINARY_SEARCH_TREE_SEARCH
    GRAPH_SEARCH
    BREADTH_FIRST_SEARCH
    DEPTH_FIRST_SEARCH
    BEST_FIRST_SEARCH
    BIDIRECTIONAL_SEARCH
    HEURISTIC_SEARCH
    SEARCH_PROBLEM
    SEARCH_SPACE
    SEARCH_TARGET
    QUERY
    SEARCH_KEY
    KEY
    VALUE
    ELEMENT
    COLLECTION
    SEQUENCE
    SORTED_SEQUENCE
    ARRAY
    LIST
    HASH_TABLE
    TREE
    GRAPH
    NODE
    VERTEX
    EDGE
    INDEX
    POSITION
    RANGE
    LOWER_BOUND
    UPPER_BOUND
    MIDPOINT
    CANDIDATE
    CANDIDATE_SET
    PREDICATE
    COMPARATOR
    COMPARISON
    EQUALITY_TEST
    ORDERING_RELATION
    MATCH
    NONMATCH
    FOUND_RESULT
    NOT_FOUND_RESULT
    SEARCH_RESULT
    PATH
    FRONTIER
    OPEN_SET
    CLOSED_SET
    VISITED_SET
    QUEUE
    STACK
    PRIORITY_QUEUE
    HEURISTIC
    COST
    DEPTH
    BRANCHING_FACTOR
    OPERATION
    INITIALISE
    COMPARE
    VISIT
    EXPAND
    FILTER
    NARROW_RANGE
    ADVANCE
    BACKTRACK
    TERMINATE
    PRECONDITION
    POSTCONDITION
    INVARIANT
    LOOP_INVARIANT
    SEARCH_INVARIANT
    CORRECTNESS
    TERMINATION
    INPUT_SIZE
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    BEST_CASE
    AVERAGE_CASE
    WORST_CASE
    EXECUTION
    EXECUTION_TRACE
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    BENCHMARK
    PERFORMANCE_METRIC
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    SEARCHES
    SEARCHES_FOR
    SEARCHES_IN
    ACCEPTS
    PRODUCES
    HAS_QUERY
    HAS_TARGET
    HAS_KEY
    HAS_CANDIDATE
    HAS_RANGE
    HAS_LOWER_BOUND
    HAS_UPPER_BOUND
    HAS_MIDPOINT
    USES_PREDICATE
    USES_COMPARATOR
    COMPARES
    MATCHES
    VISITS
    EXPANDS
    FILTERS
    NARROWS
    ADVANCES
    BACKTRACKS
    ENQUEUES
    DEQUEUES
    PUSHES
    POPS
    PRIORITISES
    MARKS_VISITED
    DISCOVERS
    REACHES
    RETURNS
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    TERMINATES_AT
    HAS_CORRECTNESS
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    IMPLEMENTED_BY
    EXECUTED_BY
    BENCHMARKED_BY
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    SEARCH_ALGORITHM_SPECIFICATIONS
    PSEUDOCODE
    SOURCE_CODE
    SEARCH_SPACE_DEFINITIONS
    TARGET_AND_QUERY_DATA
    KEY_DEFINITIONS
    PREDICATE_DEFINITIONS
    COMPARATOR_DEFINITIONS
    ORDERING_DATA
    DATA_STRUCTURE_CONTEXT
    EXECUTION_TRACES
    COMPARISON_TRACES
    VISIT_AND_EXPANSION_TRACES
    CORRECTNESS_PROOFS
    COMPLEXITY_ANALYSES
    BENCHMARK_DATA
    IMPLEMENTATION_DATA
    LANGUAGE_AND_RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_SEARCH_ALGORITHM_IDENTIFIERS
    NORMALISE_ALGORITHM_VARIANT_NAMES
    NORMALISE_SEARCH_SPACE_IDENTIFIERS
    NORMALISE_TARGET_AND_QUERY_TYPES
    NORMALISE_KEY_TYPES
    NORMALISE_PREDICATE_SEMANTICS
    NORMALISE_COMPARATOR_SEMANTICS
    NORMALISE_ORDERING_RELATIONS
    NORMALISE_RANGE_AND_INDEX_TERMS
    NORMALISE_GRAPH_SEARCH_TERMS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_BENCHMARK_UNITS
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_ALGORITHM_SEARCH_SPACE_AND_TARGET_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS SEARCH_REASONING_PIPELINE {
    SEARCH_REQUEST
      -> ALGORITHM_IDENTIFICATION
      -> SEARCH_SPACE_AND_TARGET_RESOLUTION
      -> PRECONDITION_CHECK
      -> SEARCH_STRATEGY_MAPPING
      -> CANDIDATE_EXAMINATION
      -> MATCH_OR_EXHAUSTION
      -> RESULT_VALIDATION
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS LINEAR_SEARCH_REASONING {
    SEARCH_SEQUENCE
      -> FIRST_ELEMENT

    CURRENT_ELEMENT
      -> MATCH_TEST

    MATCH
      -> RETURN_FOUND_RESULT

    NONMATCH
      -> ADVANCE_TO_NEXT_ELEMENT

    END_OF_SEQUENCE
      -> RETURN_NOT_FOUND
  }

  PROCESS BINARY_SEARCH_REASONING {
    SORTED_SEQUENCE
      -> LOWER_BOUND + UPPER_BOUND

    WHILE LOWER_BOUND <= UPPER_BOUND
      -> MIDPOINT

    MIDPOINT_ELEMENT
      -> COMPARE_WITH_TARGET

    EQUAL
      -> RETURN_FOUND_RESULT

    TARGET_ORDERED_BEFORE_MIDPOINT
      -> UPPER_BOUND = MIDPOINT - 1

    TARGET_ORDERED_AFTER_MIDPOINT
      -> LOWER_BOUND = MIDPOINT + 1

    EMPTY_RANGE
      -> RETURN_NOT_FOUND
  }

  PROCESS HASH_LOOKUP_REASONING {
    SEARCH_KEY
      -> HASH_FUNCTION

    HASH_FUNCTION
      -> CANDIDATE_BUCKET_OR_SLOT

    COLLISION_STRATEGY
      -> CANDIDATE_ENTRIES

    CANDIDATE_ENTRY
      -> KEY_EQUALITY_TEST

    MATCH
      -> RETURN_FOUND_RESULT

    CANDIDATES_EXHAUSTED
      -> RETURN_NOT_FOUND
  }

  PROCESS TREE_SEARCH_REASONING {
    ROOT_NODE
      -> CURRENT_NODE

    CURRENT_NODE
      -> MATCH_TEST

    MATCH
      -> RETURN_FOUND_RESULT

    ORDERED_TREE
      -> SELECT_CHILD_USING_ORDERING

    UNORDERED_TREE
      -> TRAVERSAL_STRATEGY

    SEARCH_SPACE_EXHAUSTED
      -> RETURN_NOT_FOUND
  }

  PROCESS BREADTH_FIRST_SEARCH_REASONING {
    START_VERTEX
      -> QUEUE
      -> VISITED_SET

    ENQUEUE_START

    WHILE QUEUE_NOT_EMPTY
      -> DEQUEUE_VERTEX
      -> MATCH_OR_GOAL_TEST
      -> EXPAND_UNVISITED_NEIGHBOURS
      -> MARK_VISITED
      -> ENQUEUE_NEIGHBOURS

    MATCH
      -> RETURN_RESULT_OR_PATH

    FRONTIER_EMPTY
      -> NOT_FOUND
  }

  PROCESS DEPTH_FIRST_SEARCH_REASONING {
    START_VERTEX
      -> STACK_OR_RECURSION
      -> VISITED_SET

    CURRENT_VERTEX
      -> MATCH_OR_GOAL_TEST

    NONMATCH
      -> SELECT_UNVISITED_NEIGHBOUR
      -> DESCEND

    DEAD_END
      -> BACKTRACK

    MATCH
      -> RETURN_RESULT_OR_PATH

    SEARCH_EXHAUSTED
      -> NOT_FOUND
  }

  PROCESS HEURISTIC_SEARCH_REASONING {
    INITIAL_STATE
      -> FRONTIER

    FRONTIER
      -> SCORE_CANDIDATES

    SCORE_CANDIDATES
      -> SELECT_NEXT_CANDIDATE

    SELECTED_CANDIDATE
      -> GOAL_TEST

    NON_GOAL
      -> EXPAND_SUCCESSORS

    SUCCESSORS
      -> UPDATE_FRONTIER

    GOAL
      -> RETURN_RESULT_OR_PATH
  }

  PROCESS RESULT_REASONING {
    FOUND_RESULT
      -> TARGET_OR_MATCHED_ENTITY
      -> LOCATION_OR_PATH_IF_AVAILABLE

    NOT_FOUND_RESULT
      -> SEARCH_SPACE_EXHAUSTION_OR_VALID_TERMINATION

    RESULT
      -> POSTCONDITION_CHECK
  }

  PROCESS CORRECTNESS_REASONING {
    PRECONDITION
      -> VALID_SEARCH_SPACE

    SEARCH_INVARIANT
      -> TARGET_NOT_DISCARDED_WHILE_POSSIBLE

    TERMINATION
      -> FOUND_OR_EXHAUSTED_STATE

    FOUND
      -> MATCH_PREDICATE_TRUE

    NOT_FOUND
      -> NO_MATCH_EXISTS_WITHIN_DEFINED_SEARCH_SPACE

    CONDITIONS
      -> CORRECTNESS_EVIDENCE
  }

  PROCESS COMPLEXITY_REASONING {
    SEARCH_ALGORITHM + SEARCH_SPACE_SIZE + STRUCTURE
      -> OPERATION_COUNT_MODEL

    OPERATION_COUNT_MODEL
      -> COMPARISONS_VISITS_EXPANSIONS_OR_PROBES

    INPUT_DISTRIBUTION_AND_CASE
      -> BEST_AVERAGE_OR_WORST_CASE

    COST_FUNCTION
      -> TIME_COMPLEXITY

    FRONTIER_VISITED_RECURSION_OR_AUXILIARY_STATE
      -> SPACE_COMPLEXITY
  }

  RULES {
    IF BINARY_SEARCH_IS_ASSERTED
    THEN REQUIRE ORDERED_SEARCH_SPACE_AND_COMPATIBLE_COMPARATOR

    IF FOUND_RESULT_IS_ASSERTED
    THEN REQUIRE MATCH_PREDICATE_OR_EQUALITY_CONDITION

    IF NOT_FOUND_IS_ASSERTED
    THEN REQUIRE VALID_SEARCH_SPACE_EXHAUSTION_OR_LOGICALLY_EQUIVALENT_TERMINATION

    IF GRAPH_SEARCH_IS_PERFORMED
    THEN PRESERVE DIRECTION_WEIGHT_AND_VISITED_STATE_CONTEXT_WHERE_RELEVANT

    IF HEURISTIC_SEARCH_IS_USED
    THEN PRESERVE HEURISTIC_DEFINITION_AND_GOAL_CONTEXT

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE SEARCH_SPACE_STRUCTURE_SIZE_CASE_AND_ALGORITHM_VARIANT

    IF BENCHMARK_RESULT_IS_REPORTED
    THEN PRESERVE IMPLEMENTATION_RUNTIME_HARDWARE_DATASET_AND_CONFIGURATION

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND SEARCHING_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        SEARCH_SPACE_COMPLETENESS,
        TARGET_AND_PREDICATE_CERTAINTY,
        ORDERING_OR_STRUCTURE_CERTAINTY,
        EXECUTION_TRACE_COMPLETENESS,
        RESULT_VALIDATION_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF SEARCH_SPACE_IS_PARTIAL
    THEN REDUCE_NOT_FOUND_CONFIDENCE

    IF ORDERING_OR_COMPARATOR_IS_UNKNOWN
    THEN REDUCE_BINARY_SEARCH_CONFIDENCE

    IF COMPLETE_TRACE_AND_RESULT_VALIDATION_CONFIRM_BEHAVIOUR
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        SEARCH_ALGORITHM_IDENTIFIER,
        ALGORITHM_VARIANT,
        SEARCH_SPACE_TYPE,
        TARGET_OR_QUERY_TYPE,
        PREDICATE_OR_COMPARATOR,
        CONFIGURATION
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    SEARCHING_ALGORITHM != SEARCH_RESULT
    SEARCH_TARGET != SEARCH_KEY_IN_ALL_CONTEXTS
    MATCH != IDENTITY_IN_ALL_PREDICATE_CONTEXTS
    FOUND != UNIQUE_MATCH
    NOT_FOUND != TARGET_NONEXISTENCE_OUTSIDE_DEFINED_SEARCH_SPACE
    LINEAR_SEARCH != BINARY_SEARCH
    BINARY_SEARCH != BINARY_SEARCH_TREE_SEARCH
    BREADTH_FIRST_SEARCH != DEPTH_FIRST_SEARCH
    GRAPH_SEARCH != PATHFINDING_AS_IDENTICAL_CONCEPT
    HEURISTIC_SEARCH != GUARANTEED_OPTIMAL_SEARCH
    SEARCH_SPACE != DATA_STRUCTURE_AS_IDENTICAL_CONCEPT
    VISITED != EXPANDED_IN_ALL_ALGORITHMS
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    EMPIRICAL_PERFORMANCE != FORMAL_COMPLEXITY
    COMPLEXITY_DEPENDS_ON_STRUCTURE_INPUT_DISTRIBUTION_VARIANT_AND_IMPLEMENTATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_SEARCH_ALGORITHM_IDENTIFIER
    CHECK_ALGORITHM_VARIANT
    CHECK_SEARCH_SPACE
    CHECK_TARGET_QUERY_AND_KEY
    CHECK_PREDICATE_OR_COMPARATOR
    CHECK_PRECONDITIONS
    CHECK_ORDERING_IF_REQUIRED
    CHECK_EXECUTION_TRACE
    CHECK_VISITED_AND_FRONTIER_STATE_IF_APPLICABLE
    CHECK_FOUND_RESULT
    CHECK_NOT_FOUND_RESULT
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_TERMINATION
    CHECK_COMPLEXITY_CONTEXT
    CHECK_IMPLEMENTATION
    CHECK_BENCHMARK_CONTEXT
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_SEARCHING_ALGORITHM_ENTITIES
    SEARCH_SPACE_RELATIONS
    TARGET_QUERY_AND_KEY_RELATIONS
    PREDICATE_AND_COMPARATOR_RELATIONS
    RANGE_AND_CANDIDATE_RELATIONS
    LINEAR_SEARCH_RELATIONS
    BINARY_SEARCH_RELATIONS
    HASH_LOOKUP_RELATIONS
    TREE_SEARCH_RELATIONS
    BREADTH_FIRST_SEARCH_RELATIONS
    DEPTH_FIRST_SEARCH_RELATIONS
    HEURISTIC_SEARCH_RELATIONS
    FOUND_AND_NOT_FOUND_RELATIONS
    PATH_AND_REACHABILITY_RELATIONS
    CORRECTNESS_RELATIONS
    TERMINATION_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    IMPLEMENTATION_RELATIONS
    BENCHMARK_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON SEARCH_ALGORITHM_OR_CONFIGURATION_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_SEARCH_SPACE_AND_TARGET_IDENTITIES
      UPDATE_PRECONDITIONS_AND_STRATEGY
      UPDATE_EXECUTION_MODEL
      REASSESS_CORRECTNESS_AND_TERMINATION
      REASSESS_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_EXECUTION_OR_BENCHMARK_DATA {
      LINK_EVIDENCE
      UPDATE_EXECUTION_TRACE
      UPDATE_FOUND_OR_NOT_FOUND_EVIDENCE
      UPDATE_OPERATION_COUNTS
      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_SEARCH_ALGORITHM
      BY_ALGORITHM_VARIANT
      BY_SEARCH_SPACE
      BY_TARGET
      BY_QUERY
      BY_KEY
      BY_PREDICATE
      BY_COMPARATOR
      BY_RESULT
      BY_PATH
      BY_COMPLEXITY
      BY_EXECUTION
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_LINEAR_SEARCH
      TRACE_BINARY_SEARCH
      TRACE_HASH_LOOKUP
      TRACE_TREE_SEARCH
      TRACE_BREADTH_FIRST_SEARCH
      TRACE_DEPTH_FIRST_SEARCH
      ANALYSE_HEURISTIC_SEARCH
      VALIDATE_SEARCH_RESULTS
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLEXITY
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_SEARCH_ALGORITHM_FROM_SEARCH_RESULT
      DISTINGUISH_FOUND_NOT_FOUND_AND_UNRESOLVED_STATES
      PRESERVE_SEARCH_SPACE_TARGET_PREDICATE_STRUCTURE_VARIANT_IMPLEMENTATION_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_LINEAR_BINARY_TREE_GRAPH_AND_HEURISTIC_SEARCH
      DISTINGUISH_FORMAL_COMPLEXITY_FROM_EMPIRICAL_PERFORMANCE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_SEARCHING_INFERENCE
    }
  }

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

END FLOW