Array Ontology

AI SEARCH

FLOW ALGEBRA — ARRAY ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures/array-ontology.html

FLOW ARRAY_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Array Ontology"
    PURPOSE = "Formalise arrays as indexed data structures, including elements, dimensions, indices, memory layout, access, updates, resizing, traversal, complexity and array-state relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    ARRAY
    STATIC_ARRAY
    DYNAMIC_ARRAY
    ONE_DIMENSIONAL_ARRAY
    MULTIDIMENSIONAL_ARRAY
    RECTANGULAR_ARRAY
    JAGGED_ARRAY
    SPARSE_ARRAY
    DENSE_ARRAY
    ELEMENT
    VALUE
    ELEMENT_TYPE
    INDEX
    INDEX_SET
    LOWER_BOUND
    UPPER_BOUND
    LENGTH
    SIZE
    CAPACITY
    DIMENSION
    RANK
    SHAPE
    STRIDE
    OFFSET
    BASE_ADDRESS
    MEMORY_ADDRESS
    MEMORY_BLOCK
    CONTIGUOUS_MEMORY
    ROW_MAJOR_ORDER
    COLUMN_MAJOR_ORDER
    ARRAY_SLICE
    SUBARRAY
    VIEW
    OPERATION
    CREATE
    INITIALISE
    ACCESS
    READ
    WRITE
    UPDATE
    INSERT
    DELETE
    APPEND
    RESIZE
    COPY
    TRAVERSE
    ITERATE
    SEARCH
    SORT
    REVERSE
    CONCATENATE
    BOUNDS_CHECK
    OUT_OF_BOUNDS_ERROR
    ALLOCATION
    REALLOCATION
    DEALLOCATION
    INVARIANT
    ORDERING
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    MUTABLE_ARRAY
    IMMUTABLE_ARRAY
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_ELEMENT
    HAS_ELEMENT_TYPE
    HAS_INDEX
    HAS_INDEX_SET
    HAS_LENGTH
    HAS_SIZE
    HAS_CAPACITY
    HAS_DIMENSION
    HAS_RANK
    HAS_SHAPE
    HAS_STRIDE
    HAS_BASE_ADDRESS
    STORED_AT
    MAPS_TO
    PRECEDES
    FOLLOWS
    ACCESSES
    READS
    WRITES
    UPDATES
    INSERTS
    DELETES
    APPENDS
    RESIZES
    COPIES
    TRAVERSES
    SEARCHES
    SORTS
    REVERSES
    CONCATENATES
    SLICES
    VIEWS
    ALLOCATES
    REALLOCATES
    DEALLOCATES
    CHECKS
    HAS_INVARIANT
    HAS_ORDERING
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_MEMORY_LAYOUT
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    ARRAY_SPECIFICATIONS
    ARRAY_IMPLEMENTATIONS
    SOURCE_CODE
    ELEMENT_AND_TYPE_DATA
    INDEX_DATA
    DIMENSION_AND_SHAPE_DATA
    MEMORY_LAYOUT_DATA
    ACCESS_TRACES
    UPDATE_TRACES
    RESIZE_TRACES
    ALLOCATION_DATA
    COMPLEXITY_ANALYSES
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_ARRAY_IDENTIFIERS
    NORMALISE_ARRAY_TYPES
    NORMALISE_ELEMENT_TYPES
    NORMALISE_INDEX_BASES
    NORMALISE_INDEX_VALUES
    NORMALISE_LENGTH_SIZE_AND_CAPACITY
    NORMALISE_DIMENSIONS_RANK_AND_SHAPE
    NORMALISE_STRIDES
    NORMALISE_MEMORY_ADDRESSES
    NORMALISE_MEMORY_LAYOUT_NAMES
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_ARRAY_AND_ELEMENT_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS ARRAY_REASONING_PIPELINE {
    ARRAY_REFERENCE
      -> ARRAY_IDENTIFICATION
      -> ELEMENT_TYPE_RESOLUTION
      -> DIMENSION_AND_SHAPE_RESOLUTION
      -> INDEX_MAPPING
      -> MEMORY_LAYOUT_MAPPING
      -> OPERATION_MAPPING
      -> BOUNDS_AND_INVARIANT_CHECK
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS INDEX_REASONING {
    ARRAY + INDEX
      -> INDEX_DOMAIN_CHECK

    VALID_INDEX
      -> LOGICAL_ELEMENT_POSITION

    LOGICAL_ELEMENT_POSITION
      -> MEMORY_OFFSET_IF_APPLICABLE

    MEMORY_OFFSET + BASE_ADDRESS
      -> ELEMENT_LOCATION

    INVALID_INDEX
      -> OUT_OF_BOUNDS_ERROR_OR_LANGUAGE_DEFINED_BEHAVIOUR
  }

  PROCESS MULTIDIMENSIONAL_REASONING {
    MULTIDIMENSIONAL_INDEX
      -> DIMENSION_COORDINATES

    DIMENSION_COORDINATES + SHAPE + STRIDES
      -> LINEAR_OFFSET

    LINEAR_OFFSET
      -> ELEMENT_LOCATION

    MEMORY_LAYOUT
      -> ROW_MAJOR_OR_COLUMN_MAJOR_OR_IMPLEMENTATION_DEFINED_MAPPING
  }

  PROCESS ACCESS_REASONING {
    ARRAY + VALID_INDEX
      -> ELEMENT_LOCATION

    ELEMENT_LOCATION
      -> READ_OR_WRITE

    READ
      -> ELEMENT_VALUE

    WRITE
      -> NEW_ELEMENT_VALUE
      -> ARRAY_STATE_UPDATE
  }

  PROCESS DYNAMIC_ARRAY_REASONING {
    APPEND_OR_INSERT
      -> CAPACITY_CHECK

    AVAILABLE_CAPACITY
      -> PLACE_ELEMENT

    INSUFFICIENT_CAPACITY
      -> NEW_CAPACITY_SELECTION
      -> REALLOCATION_OR_NEW_ALLOCATION
      -> ELEMENT_COPY_OR_MOVE
      -> PLACE_ELEMENT

    RESULT
      -> SIZE_AND_CAPACITY_UPDATE
  }

  PROCESS INSERT_DELETE_REASONING {
    INSERT_AT_POSITION
      -> BOUNDS_AND_CAPACITY_CHECK

    INSERT_AT_POSITION
      -> SHIFT_ELEMENTS_IF_REQUIRED
      -> PLACE_NEW_ELEMENT

    DELETE_AT_POSITION
      -> REMOVE_ELEMENT
      -> SHIFT_ELEMENTS_IF_REQUIRED

    RESULT
      -> SIZE_UPDATE
  }

  PROCESS SLICE_REASONING {
    ARRAY + SLICE_RANGE
      -> RANGE_VALIDATION

    RANGE_VALIDATION
      -> SUBARRAY_OR_VIEW

    VIEW
      -> SHARED_BACKING_STORAGE_IF_IMPLEMENTATION_SUPPORTS

    COPY_SLICE
      -> INDEPENDENT_STORAGE
  }

  PROCESS COMPLEXITY_REASONING {
    ARRAY + OPERATION
      -> INPUT_SIZE_AND_IMPLEMENTATION

    DIRECT_INDEX_ACCESS
      -> ACCESS_COMPLEXITY

    SEARCH
      -> SEARCH_ALGORITHM_AND_ORDERING_CONTEXT

    INSERT_OR_DELETE
      -> POSITION_AND_SHIFT_COST

    DYNAMIC_RESIZE
      -> REALLOCATION_AND_COPY_COST

    OPERATION_COST
      -> TIME_AND_SPACE_COMPLEXITY
  }

  PROCESS INVARIANT_REASONING {
    ARRAY_STATE
      -> LENGTH_SIZE_CAPACITY_RELATIONS

    DYNAMIC_ARRAY
      -> REQUIRE SIZE <= CAPACITY

    INDEX_SET
      -> BOUNDS_RELATION

    MULTIDIMENSIONAL_ARRAY
      -> SHAPE_AND_RANK_CONSISTENCY

    POST_OPERATION_STATE
      -> INVARIANT_CHECK
  }

  RULES {
    IF ARRAY_ELEMENT_IS_ACCESSED
    THEN REQUIRE ARRAY_IDENTITY_INDEX_AND_BOUNDS_CONTEXT

    IF MEMORY_ADDRESS_IS_INFERRED
    THEN REQUIRE MEMORY_LAYOUT_BASE_ADDRESS_ELEMENT_SIZE_AND_INDEX_MAPPING

    IF ARRAY_IS_MULTIDIMENSIONAL
    THEN PRESERVE SHAPE_RANK_STRIDES_AND_LAYOUT_CONTEXT

    IF DYNAMIC_ARRAY_RESIZES
    THEN DO_NOT ASSUME BASE_ADDRESS_REMAINS_UNCHANGED

    IF SLICE_IS_CREATED
    THEN DISTINGUISH VIEW_FROM_COPY

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE OPERATION_IMPLEMENTATION_INPUT_SIZE_AND_CASE_CONTEXT

    IF INDEX_BASE_DIFFERS_BY_LANGUAGE_OR_API
    THEN PRESERVE INDEXING_CONVENTION

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND ARRAY_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ARRAY_IDENTITY_CERTAINTY,
        ELEMENT_TYPE_CERTAINTY,
        INDEX_AND_BOUNDS_CERTAINTY,
        SHAPE_AND_DIMENSION_COMPLETENESS,
        MEMORY_LAYOUT_CERTAINTY,
        OPERATION_TRACE_COMPLETENESS,
        IMPLEMENTATION_CERTAINTY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF MEMORY_LAYOUT_IS_UNKNOWN
    THEN REDUCE_PHYSICAL_LOCATION_INFERENCE_CONFIDENCE

    IF INDEXING_CONVENTION_IS_UNKNOWN
    THEN REDUCE_INDEX_MAPPING_CONFIDENCE

    IF COMPLETE_OPERATION_TRACE_CONFIRMS_STATE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ARRAY_IDENTIFIER,
        ELEMENT_TYPE,
        SHAPE,
        INDEXING_CONVENTION,
        IMPLEMENTATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    ARRAY != ELEMENT
    INDEX != VALUE
    INDEX != MEMORY_ADDRESS
    LENGTH != CAPACITY_IN_DYNAMIC_ARRAYS
    SIZE != CAPACITY
    DIMENSION != RANK
    SHAPE != MEMORY_LAYOUT
    ROW_MAJOR != COLUMN_MAJOR
    ARRAY_SLICE != ARRAY_COPY_IN_ALL_IMPLEMENTATIONS
    VIEW != INDEPENDENT_STORAGE_IN_ALL_IMPLEMENTATIONS
    STATIC_ARRAY != DYNAMIC_ARRAY
    DYNAMIC_ARRAY != LINKED_LIST
    DIRECT_INDEX_ACCESS_COMPLEXITY != SEARCH_COMPLEXITY
    RESIZE != APPEND_IN_ALL_CASES
    CONTIGUOUS_LOGICAL_INDEXING != GUARANTEED_PHYSICAL_LAYOUT_IN_ALL_HIGH_LEVEL_RUNTIMES
    IMPLEMENTATION_LANGUAGE_AND_RUNTIME_AFFECT_ARRAY_BEHAVIOUR
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_ARRAY_IDENTIFIER
    CHECK_ARRAY_TYPE
    CHECK_ELEMENT_TYPE
    CHECK_INDEXING_CONVENTION
    CHECK_BOUNDS
    CHECK_LENGTH_SIZE_AND_CAPACITY
    CHECK_DIMENSIONS_RANK_AND_SHAPE
    CHECK_STRIDES
    CHECK_MEMORY_LAYOUT
    CHECK_ACCESS_RELATIONS
    CHECK_UPDATE_RELATIONS
    CHECK_INSERT_DELETE_AND_APPEND
    CHECK_RESIZE
    CHECK_SLICE_AND_VIEW_RELATIONS
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_ARRAY_ENTITIES
    ARRAY_TYPE_RELATIONS
    ELEMENT_AND_TYPE_RELATIONS
    INDEX_AND_BOUNDS_RELATIONS
    LENGTH_SIZE_AND_CAPACITY_RELATIONS
    DIMENSION_RANK_AND_SHAPE_RELATIONS
    STRIDE_AND_OFFSET_RELATIONS
    MEMORY_LAYOUT_RELATIONS
    ACCESS_AND_UPDATE_RELATIONS
    INSERT_DELETE_AND_APPEND_RELATIONS
    RESIZE_RELATIONS
    SLICE_AND_VIEW_RELATIONS
    ARRAY_STATE_TRANSITIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON ARRAY_OPERATION {
      NORMALISE
      RESOLVE_ARRAY_AND_ELEMENT_IDENTITIES
      UPDATE_ARRAY_STATE
      UPDATE_ELEMENTS_AND_INDICES
      UPDATE_SIZE_AND_CAPACITY
      UPDATE_MEMORY_MAPPING_IF_REQUIRED
      RECHECK_INVARIANTS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_MEMORY_LAYOUT
      REASSESS_COMPLEXITY
      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_ARRAY
      BY_ARRAY_TYPE
      BY_ELEMENT
      BY_INDEX
      BY_DIMENSION
      BY_SHAPE
      BY_MEMORY_LAYOUT
      BY_OPERATION
      BY_SLICE
      BY_SIZE
      BY_CAPACITY
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_ARRAY_INDICES
      ANALYSE_MULTIDIMENSIONAL_MAPPING
      TRACE_ARRAY_ACCESS_AND_UPDATES
      ANALYSE_DYNAMIC_ARRAY_RESIZING
      ANALYSE_INSERTION_AND_DELETION
      ANALYSE_SLICES_AND_VIEWS
      ANALYSE_COMPLEXITY
      CHECK_ARRAY_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_ARRAY_FROM_ELEMENT
      DISTINGUISH_INDEX_FROM_MEMORY_ADDRESS
      DISTINGUISH_LENGTH_SIZE_AND_CAPACITY
      PRESERVE_ELEMENT_TYPE_INDEXING_SHAPE_LAYOUT_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_SLICE_VIEW_AND_COPY
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_ARRAY_INFERENCE
    }
  }

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

END FLOW