Data Structures

AI SEARCH

FLOW ALGEBRA — DATA STRUCTURES
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures.html

FLOW DATA_STRUCTURES {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Data Structures"
    PURPOSE = "Formalise computational data structures, their elements, organisation, access patterns, operations, invariants, complexity, memory representation and semantic relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    DATA_STRUCTURE
    ABSTRACT_DATA_TYPE
    ELEMENT
    VALUE
    KEY
    INDEX
    NODE
    EDGE
    POINTER
    REFERENCE
    MEMORY_LOCATION
    COLLECTION
    SEQUENCE
    ARRAY
    STATIC_ARRAY
    DYNAMIC_ARRAY
    MATRIX
    VECTOR
    LIST
    LINKED_LIST
    SINGLY_LINKED_LIST
    DOUBLY_LINKED_LIST
    CIRCULAR_LIST
    STACK
    QUEUE
    DEQUE
    PRIORITY_QUEUE
    SET
    MULTISET
    MAP
    DICTIONARY
    HASH_TABLE
    HASH_FUNCTION
    HASH_BUCKET
    COLLISION
    TREE
    ROOTED_TREE
    BINARY_TREE
    BINARY_SEARCH_TREE
    AVL_TREE
    RED_BLACK_TREE
    B_TREE
    B_PLUS_TREE
    HEAP
    BINARY_HEAP
    TRIE
    GRAPH
    DIRECTED_GRAPH
    UNDIRECTED_GRAPH
    WEIGHTED_GRAPH
    DIRECTED_ACYCLIC_GRAPH
    ADJACENCY_LIST
    ADJACENCY_MATRIX
    UNION_FIND
    DISJOINT_SET
    BLOOM_FILTER
    SKIP_LIST
    BUFFER
    RING_BUFFER
    RECORD
    STRUCTURE
    TUPLE
    OBJECT
    ITERATOR
    OPERATION
    INSERTION
    DELETION
    SEARCH
    LOOKUP
    ACCESS
    UPDATE
    TRAVERSAL
    SORT
    MERGE
    SPLIT
    PUSH
    POP
    ENQUEUE
    DEQUEUE
    PEEK
    ROTATION
    REBALANCING
    RESIZE
    INVARIANT
    ORDERING
    CAPACITY
    SIZE
    COMPLEXITY
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    MEMORY_LAYOUT
    CONTIGUOUS_STORAGE
    LINKED_STORAGE
    MUTABLE_STRUCTURE
    IMMUTABLE_STRUCTURE
    PERSISTENT_DATA_STRUCTURE
    CONCURRENT_DATA_STRUCTURE
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_ELEMENT
    HAS_KEY
    HAS_VALUE
    HAS_INDEX
    HAS_NODE
    HAS_EDGE
    POINTS_TO
    REFERENCES
    PRECEDES
    FOLLOWS
    PARENT_OF
    CHILD_OF
    CONNECTED_TO
    ADJACENT_TO
    ROOT_OF
    MAPS_TO
    HASHES_TO
    STORED_IN
    IMPLEMENTS
    REPRESENTS
    INSERTS
    DELETES
    SEARCHES
    LOOKS_UP
    ACCESSES
    UPDATES
    TRAVERSES
    SORTS
    MERGES
    SPLITS
    PUSHES
    POPS
    ENQUEUES
    DEQUEUES
    ROTATES
    REBALANCES
    RESIZES
    PRESERVES
    HAS_INVARIANT
    HAS_ORDERING
    HAS_SIZE
    HAS_CAPACITY
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_MEMORY_LAYOUT
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    DATA_STRUCTURE_DEFINITIONS
    ABSTRACT_DATA_TYPE_SPECIFICATIONS
    IMPLEMENTATION_DATA
    SOURCE_CODE
    ELEMENT_DATA
    KEY_VALUE_DATA
    NODE_AND_EDGE_DATA
    MEMORY_LAYOUT_DATA
    OPERATION_TRACES
    COMPLEXITY_ANALYSES
    INVARIANT_DEFINITIONS
    BENCHMARK_DATA
    CONFIGURATION_DATA
    LANGUAGE_AND_RUNTIME_CONTEXT
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_DATA_STRUCTURE_IDENTIFIERS
    NORMALISE_DATA_STRUCTURE_NAMES
    NORMALISE_ABSTRACT_DATA_TYPE_NAMES
    NORMALISE_ELEMENT_AND_KEY_TYPES
    NORMALISE_OPERATION_NAMES
    NORMALISE_NODE_AND_EDGE_IDENTIFIERS
    NORMALISE_ORDERING_RELATIONS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_MEMORY_UNITS
    NORMALISE_CAPACITY_AND_SIZE
    NORMALISE_IMPLEMENTATION_NAMES
    RESOLVE_STRUCTURE_AND_ELEMENT_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS DATA_STRUCTURE_REASONING_PIPELINE {
    STRUCTURE_REFERENCE
      -> STRUCTURE_IDENTIFICATION
      -> ABSTRACT_TYPE_AND_IMPLEMENTATION_MAPPING
      -> ELEMENT_AND_RELATION_MAPPING
      -> OPERATION_MAPPING
      -> INVARIANT_VALIDATION
      -> COMPLEXITY_ANALYSIS
      -> MEMORY_REPRESENTATION_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS ARRAY_REASONING {
    ARRAY
      -> CONTIGUOUS_OR_DEFINED_STORAGE

    INDEX
      -> OFFSET_CALCULATION

    OFFSET_CALCULATION
      -> ELEMENT_LOCATION

    ARRAY_ACCESS
      -> ELEMENT_VALUE

    RESIZE_IF_DYNAMIC
      -> CAPACITY_CHANGE
  }

  PROCESS LINKED_LIST_REASONING {
    LINKED_LIST
      -> NODE_SEQUENCE

    NODE
      -> VALUE + NEXT_REFERENCE

    DOUBLY_LINKED_NODE
      -> PREVIOUS_REFERENCE + NEXT_REFERENCE

    INSERTION_OR_DELETION
      -> LINK_UPDATES

    LINK_UPDATES
      -> LIST_INVARIANT_CHECK
  }

  PROCESS STACK_REASONING {
    STACK
      -> TOP_POSITION

    PUSH
      -> ADD_ELEMENT_AT_TOP

    POP
      -> REMOVE_TOP_ELEMENT

    PEEK
      -> READ_TOP_ELEMENT

    STACK_OPERATIONS
      -> LIFO_ORDERING
  }

  PROCESS QUEUE_REASONING {
    QUEUE
      -> FRONT_AND_REAR

    ENQUEUE
      -> ADD_AT_REAR

    DEQUEUE
      -> REMOVE_FROM_FRONT

    QUEUE_OPERATIONS
      -> FIFO_ORDERING
  }

  PROCESS HASH_TABLE_REASONING {
    KEY
      -> HASH_FUNCTION

    HASH_FUNCTION
      -> HASH_VALUE

    HASH_VALUE
      -> BUCKET_INDEX

    BUCKET_INDEX
      -> BUCKET

    COLLISION
      -> COLLISION_RESOLUTION

    LOOKUP
      -> KEY_MATCH
      -> VALUE
  }

  PROCESS TREE_REASONING {
    TREE
      -> ROOT_NODE

    ROOT_NODE
      -> CHILD_RELATIONS

    CHILD_RELATIONS
      -> SUBTREES

    TREE_OPERATION
      -> TRAVERSAL_OR_SEARCH_OR_UPDATE

    ORDERED_TREE
      -> ORDERING_INVARIANT_CHECK
  }

  PROCESS BALANCED_TREE_REASONING {
    SEARCH_TREE_UPDATE
      -> HEIGHT_OR_BALANCE_CHANGE

    BALANCE_CONDITION_CHECK
      -> VALID_OR_IMBALANCED

    IMBALANCED
      -> ROTATION_OR_RESTRUCTURING

    ROTATION_OR_RESTRUCTURING
      -> RESTORED_INVARIANT
  }

  PROCESS HEAP_REASONING {
    HEAP
      -> HEAP_ORDER_PROPERTY

    INSERTION
      -> APPEND_OR_PLACE_NEW_ELEMENT
      -> SIFT_UP

    REMOVE_ROOT
      -> ROOT_REPLACEMENT
      -> SIFT_DOWN

    RESULT
      -> HEAP_INVARIANT
  }

  PROCESS GRAPH_REASONING {
    GRAPH
      -> VERTEX_SET + EDGE_SET

    EDGE
      -> SOURCE_AND_TARGET_OR_ENDPOINTS

    REPRESENTATION
      -> ADJACENCY_LIST_OR_MATRIX_OR_OTHER

    TRAVERSAL
      -> VISITED_VERTEX_SEQUENCE

    GRAPH_PROPERTIES
      -> DIRECTED_WEIGHTED_CONNECTED_ACYCLIC_OR_OTHER_RELATIONS
  }

  PROCESS COMPLEXITY_REASONING {
    DATA_STRUCTURE + OPERATION
      -> INPUT_SIZE_MODEL

    INPUT_SIZE_MODEL
      -> OPERATION_COST

    OPERATION_COST
      -> BEST_AVERAGE_OR_WORST_CASE

    COST_FUNCTION
      -> ASYMPTOTIC_COMPLEXITY

    MEMORY_REQUIREMENTS
      -> SPACE_COMPLEXITY
  }

  PROCESS INVARIANT_REASONING {
    DATA_STRUCTURE
      -> INVARIANT_SET

    OPERATION
      -> STATE_TRANSFORMATION

    STATE_TRANSFORMATION
      -> POST_OPERATION_STATE

    POST_OPERATION_STATE
      -> INVARIANT_CHECK

    VIOLATION
      -> INVALID_STRUCTURE_STATE
  }

  RULES {
    IF DATA_STRUCTURE_IS_IDENTIFIED
    THEN PRESERVE ABSTRACT_TYPE_IMPLEMENTATION_ELEMENT_TYPE_AND_CONFIGURATION_CONTEXT

    IF COMPLEXITY_IS_ASSERTED
    THEN REQUIRE OPERATION_INPUT_MODEL_CASE_AND_IMPLEMENTATION_CONTEXT

    IF HASH_TABLE_LOOKUP_IS_ANALYSED
    THEN PRESERVE HASH_FUNCTION_LOAD_FACTOR_AND_COLLISION_STRATEGY

    IF TREE_IS_CLASSIFIED_AS_BALANCED
    THEN REQUIRE BALANCE_INVARIANT_EVIDENCE

    IF GRAPH_IS_CLASSIFIED_AS_DIRECTED
    THEN PRESERVE EDGE_DIRECTION

    IF STRUCTURE_IS_MUTABLE
    THEN TRACK STATE_CHANGES_ACROSS_OPERATIONS

    IF STRUCTURE_IS_PERSISTENT
    THEN PRESERVE VERSIONED_STATES_AND_STRUCTURAL_SHARING

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND DATA_STRUCTURE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        STRUCTURE_IDENTITY_CERTAINTY,
        IMPLEMENTATION_CERTAINTY,
        ELEMENT_AND_RELATION_COMPLETENESS,
        OPERATION_TRACE_COMPLETENESS,
        INVARIANT_EVIDENCE_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        MEMORY_LAYOUT_CERTAINTY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF IMPLEMENTATION_IS_UNKNOWN
    THEN REDUCE_OPERATION_AND_MEMORY_INFERENCE_CONFIDENCE

    IF COMPLEXITY_CASE_OR_INPUT_MODEL_IS_UNKNOWN
    THEN REDUCE_COMPLEXITY_CONFIDENCE

    IF COMPLETE_OPERATION_TRACE_AND_INVARIANT_CHECK_CONFIRM_STATE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ABSTRACT_DATA_TYPE,
        IMPLEMENTATION,
        ELEMENT_TYPE,
        KEY_TYPE,
        CONFIGURATION
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    ABSTRACT_DATA_TYPE != CONCRETE_IMPLEMENTATION
    ARRAY != LINKED_LIST
    STACK != QUEUE
    SET != MULTISET
    MAP != SET
    TREE != GRAPH_IN_GENERAL_CLASSIFICATION_CONTEXT
    BINARY_TREE != BINARY_SEARCH_TREE
    BINARY_SEARCH_TREE != BALANCED_TREE
    HEAP != SORTED_SEQUENCE
    HASH_VALUE != UNIQUE_KEY_IDENTITY
    HASH_COLLISION != DUPLICATE_KEY
    INDEX != VALUE
    NODE != ELEMENT_VALUE_IN_ALL_IMPLEMENTATIONS
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    SPACE_COMPLEXITY != OBJECT_SIZE_WITHOUT_INPUT_MODEL
    AVERAGE_CASE != WORST_CASE
    MUTABLE != NONPERSISTENT_IN_ALL_MODELS
    COMPLEXITY_AND_PERFORMANCE_DEPEND_ON_IMPLEMENTATION_AND_CONTEXT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_STRUCTURE_IDENTIFIER
    CHECK_ABSTRACT_DATA_TYPE
    CHECK_IMPLEMENTATION
    CHECK_ELEMENT_TYPES
    CHECK_KEY_VALUE_RELATIONS
    CHECK_INDEX_RELATIONS
    CHECK_NODE_AND_EDGE_RELATIONS
    CHECK_ORDERING
    CHECK_OPERATIONS
    CHECK_INVARIANTS
    CHECK_SIZE_AND_CAPACITY
    CHECK_COMPLEXITY_CONTEXT
    CHECK_MEMORY_LAYOUT
    CHECK_MUTABILITY_AND_PERSISTENCE
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_DATA_STRUCTURE_ENTITIES
    ABSTRACT_DATA_TYPE_RELATIONS
    ELEMENT_AND_KEY_VALUE_RELATIONS
    INDEX_RELATIONS
    NODE_AND_EDGE_RELATIONS
    ORDERING_RELATIONS
    OPERATION_RELATIONS
    ARRAY_RELATIONS
    LINKED_LIST_RELATIONS
    STACK_AND_QUEUE_RELATIONS
    HASH_TABLE_RELATIONS
    TREE_RELATIONS
    HEAP_RELATIONS
    GRAPH_RELATIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    MEMORY_LAYOUT_RELATIONS
    MUTABILITY_AND_PERSISTENCE_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON STRUCTURE_OPERATION {
      NORMALISE
      RESOLVE_STRUCTURE_AND_ELEMENT_IDENTITIES
      UPDATE_ELEMENTS_KEYS_NODES_AND_EDGES
      UPDATE_SIZE_AND_CAPACITY
      UPDATE_ORDERING
      RECHECK_INVARIANTS
      UPDATE_OPERATION_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_OR_CONFIGURATION_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      REASSESS_MEMORY_LAYOUT
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    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_DATA_STRUCTURE
      BY_ABSTRACT_DATA_TYPE
      BY_ELEMENT
      BY_KEY
      BY_OPERATION
      BY_ARRAY
      BY_LIST
      BY_STACK
      BY_QUEUE
      BY_HASH_TABLE
      BY_TREE
      BY_HEAP
      BY_GRAPH
      BY_COMPLEXITY
      BY_INVARIANT
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_ARRAYS
      ANALYSE_LINKED_LISTS
      ANALYSE_STACKS_AND_QUEUES
      ANALYSE_HASH_TABLES
      ANALYSE_TREES_AND_BALANCING
      ANALYSE_HEAPS
      ANALYSE_GRAPHS
      ANALYSE_OPERATIONS
      ANALYSE_COMPLEXITY
      CHECK_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_ABSTRACT_DATA_TYPE_FROM_IMPLEMENTATION
      PRESERVE_ELEMENT_KEY_OPERATION_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_AVERAGE_FROM_WORST_CASE_COMPLEXITY
      DISTINGUISH_HASH_COLLISION_FROM_DUPLICATE_KEY
      PRESERVE_STRUCTURE_INVARIANTS
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_DATA_STRUCTURE_INFERENCE
    }
  }

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

END FLOW