Linked List Ontology

AI SEARCH

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

FLOW LINKED_LIST_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Linked List Ontology"
    PURPOSE = "Formalise linked lists, nodes, values, references, traversal, insertion, deletion, ordering, structural invariants, complexity and linked-memory relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    LINKED_LIST
    SINGLY_LINKED_LIST
    DOUBLY_LINKED_LIST
    CIRCULAR_LINKED_LIST
    CIRCULAR_SINGLY_LINKED_LIST
    CIRCULAR_DOUBLY_LINKED_LIST
    SORTED_LINKED_LIST
    UNSORTED_LINKED_LIST
    NODE
    HEAD_NODE
    TAIL_NODE
    SENTINEL_NODE
    VALUE
    ELEMENT
    NEXT_REFERENCE
    PREVIOUS_REFERENCE
    NULL_REFERENCE
    POINTER
    REFERENCE
    MEMORY_ADDRESS
    MEMORY_LOCATION
    LIST_STATE
    POSITION
    INDEX
    SIZE
    LENGTH
    OPERATION
    CREATE
    INITIALISE
    ACCESS
    SEARCH
    FIND
    TRAVERSE
    ITERATE
    INSERT
    INSERT_HEAD
    INSERT_TAIL
    INSERT_BEFORE
    INSERT_AFTER
    DELETE
    DELETE_HEAD
    DELETE_TAIL
    REMOVE
    UPDATE
    REVERSE
    CONCATENATE
    SPLIT
    MERGE
    CLEAR
    ALLOCATION
    DEALLOCATION
    LINK_UPDATE
    INVARIANT
    HEAD_INVARIANT
    TAIL_INVARIANT
    LINK_INVARIANT
    BIDIRECTIONAL_LINK_INVARIANT
    CIRCULARITY_INVARIANT
    ORDERING_INVARIANT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    MUTABLE_LINKED_LIST
    IMMUTABLE_LINKED_LIST
    PERSISTENT_LINKED_LIST
    STRUCTURAL_SHARING
    ITERATOR
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_NODE
    HAS_HEAD
    HAS_TAIL
    HAS_VALUE
    HAS_NEXT
    HAS_PREVIOUS
    POINTS_TO
    REFERENCES
    PRECEDES
    FOLLOWS
    STORED_AT
    ACCESSES
    SEARCHES
    FINDS
    TRAVERSES
    ITERATES
    INSERTS
    DELETES
    REMOVES
    UPDATES
    REVERSES
    CONCATENATES
    SPLITS
    MERGES
    CLEARS
    ALLOCATES
    DEALLOCATES
    UPDATES_LINK
    HAS_SIZE
    HAS_LENGTH
    HAS_POSITION
    HAS_INVARIANT
    HAS_ORDERING
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    LINKED_LIST_SPECIFICATIONS
    IMPLEMENTATION_DEFINITIONS
    SOURCE_CODE
    NODE_DATA
    VALUE_DATA
    NEXT_AND_PREVIOUS_REFERENCE_DATA
    HEAD_AND_TAIL_DATA
    MEMORY_DATA
    OPERATION_TRACES
    TRAVERSAL_TRACES
    INSERTION_TRACES
    DELETION_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_LINKED_LIST_IDENTIFIERS
    NORMALISE_LINKED_LIST_TYPES
    NORMALISE_NODE_IDENTIFIERS
    NORMALISE_VALUE_TYPES
    NORMALISE_REFERENCE_IDENTIFIERS
    NORMALISE_HEAD_AND_TAIL_IDENTITIES
    NORMALISE_POSITION_AND_INDEX_TERMS
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_MEMORY_ADDRESSES
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_LIST_NODE_AND_REFERENCE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS LINKED_LIST_REASONING_PIPELINE {
    LINKED_LIST_REFERENCE
      -> LIST_IDENTIFICATION
      -> LIST_TYPE_RESOLUTION
      -> NODE_AND_REFERENCE_MAPPING
      -> HEAD_AND_TAIL_RESOLUTION
      -> OPERATION_MAPPING
      -> STRUCTURAL_INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS SINGLY_LINKED_REASONING {
    HEAD_NODE
      -> NEXT_REFERENCE

    NEXT_REFERENCE
      -> NEXT_NODE

    NEXT_NODE
      -> REPEAT_UNTIL_NULL_OR_HEAD_IF_CIRCULAR

    NODE_SEQUENCE
      -> LIST_ORDER
  }

  PROCESS DOUBLY_LINKED_REASONING {
    NODE
      -> NEXT_REFERENCE
      -> NEXT_NODE

    NODE
      -> PREVIOUS_REFERENCE
      -> PREVIOUS_NODE

    NEXT_NODE.PREVIOUS
      -> CURRENT_NODE

    PREVIOUS_NODE.NEXT
      -> CURRENT_NODE

    RELATIONS
      -> BIDIRECTIONAL_LINK_INVARIANT
  }

  PROCESS INSERTION_REASONING {
    INSERT_POSITION
      -> PREDECESSOR_AND_SUCCESSOR_RESOLUTION

    NEW_NODE
      -> ALLOCATION_IF_REQUIRED

    NEW_NODE
      -> VALUE_ASSIGNMENT

    SINGLY_LINKED_INSERT
      -> NEW_NODE.NEXT = SUCCESSOR
      -> PREDECESSOR.NEXT = NEW_NODE

    DOUBLY_LINKED_INSERT
      -> NEW_NODE.PREVIOUS = PREDECESSOR
      -> NEW_NODE.NEXT = SUCCESSOR
      -> PREDECESSOR.NEXT = NEW_NODE
      -> SUCCESSOR.PREVIOUS = NEW_NODE

    RESULT
      -> SIZE_UPDATE
      -> INVARIANT_CHECK
  }

  PROCESS DELETION_REASONING {
    TARGET_NODE
      -> PREDECESSOR_AND_SUCCESSOR_RESOLUTION

    SINGLY_LINKED_DELETE
      -> PREDECESSOR.NEXT = SUCCESSOR

    DOUBLY_LINKED_DELETE
      -> PREDECESSOR.NEXT = SUCCESSOR
      -> SUCCESSOR.PREVIOUS = PREDECESSOR

    TARGET_NODE
      -> DETACH_REFERENCES
      -> DEALLOCATION_IF_REQUIRED

    RESULT
      -> SIZE_UPDATE
      -> HEAD_TAIL_UPDATE_IF_REQUIRED
      -> INVARIANT_CHECK
  }

  PROCESS TRAVERSAL_REASONING {
    START_NODE
      -> VISIT_NODE

    VISIT_NODE
      -> PROCESS_VALUE

    PROCESS_VALUE
      -> FOLLOW_NEXT_OR_PREVIOUS_REFERENCE

    TERMINATION_CONDITION
      -> NULL_REFERENCE
      OR -> RETURN_TO_START_IN_CIRCULAR_LIST
      OR -> EXPLICIT_BOUND
  }

  PROCESS SEARCH_REASONING {
    SEARCH_VALUE_OR_PREDICATE
      -> START_AT_HEAD_OR_DEFINED_NODE

    CURRENT_NODE
      -> VALUE_COMPARISON

    MATCH
      -> RETURN_NODE_OR_POSITION

    NO_MATCH
      -> FOLLOW_NEXT_REFERENCE

    END_REACHED
      -> NOT_FOUND
  }

  PROCESS REVERSE_REASONING {
    LINKED_LIST
      -> NODE_TRAVERSAL

    EACH_NODE
      -> REVERSE_LINK_DIRECTION

    SINGLY_LINKED_LIST
      -> SWAP_HEAD_AND_TAIL_AFTER_LINK_REVERSAL

    DOUBLY_LINKED_LIST
      -> SWAP_NEXT_AND_PREVIOUS_PER_NODE
      -> SWAP_HEAD_AND_TAIL

    RESULT
      -> INVARIANT_CHECK
  }

  PROCESS CIRCULAR_REASONING {
    CIRCULAR_LINKED_LIST
      -> HEAD_AND_TAIL

    SINGLY_CIRCULAR
      -> TAIL.NEXT = HEAD

    DOUBLY_CIRCULAR
      -> TAIL.NEXT = HEAD
      -> HEAD.PREVIOUS = TAIL

    TRAVERSAL
      -> TERMINATE_ON_RETURN_TO_START_OR_EXPLICIT_COUNT
  }

  PROCESS COMPLEXITY_REASONING {
    LINKED_LIST + OPERATION
      -> INPUT_SIZE_MODEL

    HEAD_INSERT_OR_DELETE
      -> LOCAL_LINK_UPDATE_COST

    SEARCH_OR_INDEX_ACCESS
      -> TRAVERSAL_DISTANCE

    TAIL_OPERATION
      -> TAIL_REFERENCE_AND_LIST_TYPE_CONTEXT

    OPERATION_COST
      -> TIME_COMPLEXITY

    NODE_AND_REFERENCE_STORAGE
      -> SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_LIST_STATE(T1)
      + UPDATE
      -> NEW_LIST_STATE(T2)

    T2
      -> NEW_PATH_OR_PREFIX_NODES_IF_REQUIRED

    T1 + T2
      -> STRUCTURAL_SHARING

    T1
      -> PRESERVED
  }

  RULES {
    IF LINKED_LIST_NODE_IS_IDENTIFIED
    THEN PRESERVE LIST_IDENTITY_NODE_IDENTITY_VALUE_AND_REFERENCE_CONTEXT

    IF SINGLY_LINKED_LIST_IS_ASSERTED
    THEN DO_NOT REQUIRE PREVIOUS_REFERENCE

    IF DOUBLY_LINKED_LIST_IS_ASSERTED
    THEN CHECK FORWARD_AND_BACKWARD_LINK_CONSISTENCY

    IF CIRCULAR_LINKED_LIST_IS_ASSERTED
    THEN DO_NOT USE_NULL_AS_THE_ONLY_TRAVERSAL_TERMINATION_ASSUMPTION

    IF NODE_IS_DELETED
    THEN UPDATE HEAD_TAIL_AND_NEIGHBOUR_REFERENCES_AS_REQUIRED

    IF INDEX_ACCESS_COMPLEXITY_IS_ASSERTED
    THEN PRESERVE WHETHER_INDEX_IS_LOGICAL_POSITION_RATHER_THAN_DIRECT_ADDRESS

    IF PERSISTENT_LIST_IS_UPDATED
    THEN PRESERVE PRIOR_LIST_STATE

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND LINKED_LIST_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        LIST_IDENTITY_CERTAINTY,
        LIST_TYPE_CERTAINTY,
        NODE_IDENTITY_COMPLETENESS,
        REFERENCE_GRAPH_COMPLETENESS,
        HEAD_AND_TAIL_CERTAINTY,
        OPERATION_TRACE_COMPLETENESS,
        INVARIANT_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF REFERENCE_GRAPH_IS_PARTIAL
    THEN REDUCE_STRUCTURE_AND_TRAVERSAL_CONFIDENCE

    IF LIST_TYPE_IS_UNKNOWN
    THEN REDUCE_OPERATION_AND_INVARIANT_CONFIDENCE

    IF COMPLETE_REFERENCE_GRAPH_AND_OPERATION_TRACE_CONFIRM_STATE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        LINKED_LIST_IDENTIFIER,
        LIST_TYPE,
        NODE_IDENTIFIER,
        VALUE_TYPE,
        IMPLEMENTATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    LINKED_LIST != ARRAY
    NODE != VALUE
    NODE_IDENTITY != NODE_POSITION
    NEXT_REFERENCE != NEXT_NODE
    PREVIOUS_REFERENCE != PREVIOUS_NODE
    HEAD != FIRST_VALUE
    TAIL != LAST_VALUE
    SINGLY_LINKED_LIST != DOUBLY_LINKED_LIST
    LINEAR_LINKED_LIST != CIRCULAR_LINKED_LIST
    LOGICAL_INDEX != DIRECT_MEMORY_OFFSET
    SEARCH != DIRECT_INDEX_ACCESS
    DELETE_NODE != NECESSARILY_IMMEDIATE_MEMORY_DEALLOCATION
    REVERSE != SORT
    PERSISTENT_LINKED_LIST != MUTABLE_LINKED_LIST
    COMPLEXITY_DEPENDS_ON_OPERATION_LIST_TYPE_AND_AVAILABLE_REFERENCES
    IMPLEMENTATION_LANGUAGE_AND_RUNTIME_AFFECT_MEMORY_MANAGEMENT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_LINKED_LIST_IDENTIFIER
    CHECK_LIST_TYPE
    CHECK_NODE_IDENTITIES
    CHECK_VALUES
    CHECK_HEAD_AND_TAIL
    CHECK_NEXT_REFERENCES
    CHECK_PREVIOUS_REFERENCES_IF_APPLICABLE
    CHECK_CIRCULARITY_IF_APPLICABLE
    CHECK_SIZE_AND_LENGTH
    CHECK_INSERTION_RELATIONS
    CHECK_DELETION_RELATIONS
    CHECK_TRAVERSAL
    CHECK_SEARCH
    CHECK_REVERSE
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE_AND_STRUCTURAL_SHARING
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_LINKED_LIST_ENTITIES
    LIST_TYPE_RELATIONS
    NODE_AND_VALUE_RELATIONS
    HEAD_AND_TAIL_RELATIONS
    NEXT_AND_PREVIOUS_REFERENCE_RELATIONS
    NODE_ORDER_RELATIONS
    INSERTION_RELATIONS
    DELETION_RELATIONS
    TRAVERSAL_RELATIONS
    SEARCH_RELATIONS
    REVERSE_RELATIONS
    CIRCULARITY_RELATIONS
    LINKED_LIST_STATE_TRANSITIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    PERSISTENCE_AND_STRUCTURAL_SHARING_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON LINKED_LIST_OPERATION {
      NORMALISE
      RESOLVE_LIST_NODE_AND_REFERENCE_IDENTITIES
      UPDATE_NODE_SET
      UPDATE_NEXT_AND_PREVIOUS_RELATIONS
      UPDATE_HEAD_AND_TAIL
      UPDATE_SIZE
      RECHECK_INVARIANTS
      UPDATE_OPERATION_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      REASSESS_MEMORY_MANAGEMENT
      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_LINKED_LIST
      BY_LIST_TYPE
      BY_NODE
      BY_VALUE
      BY_HEAD
      BY_TAIL
      BY_NEXT_REFERENCE
      BY_PREVIOUS_REFERENCE
      BY_OPERATION
      BY_TRAVERSAL
      BY_SEARCH
      BY_INVARIANT
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_SINGLY_LINKED_LISTS
      ANALYSE_DOUBLY_LINKED_LISTS
      TRACE_INSERTIONS
      TRACE_DELETIONS
      TRACE_TRAVERSALS
      ANALYSE_SEARCH
      ANALYSE_REVERSE
      ANALYSE_CIRCULAR_LISTS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_NODE_FROM_VALUE_AND_POSITION
      DISTINGUISH_SINGLY_DOUBLY_AND_CIRCULAR_LISTS
      PRESERVE_LIST_TYPE_NODE_REFERENCE_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_LOGICAL_INDEX_FROM_DIRECT_MEMORY_ACCESS
      PRESERVE_LINKED_LIST_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_LINKED_LIST_INFERENCE
    }
  }

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

END FLOW