Trie Ontology

AI SEARCH

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

FLOW TRIE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Trie Ontology"
    PURPOSE = "Formalise trie data structures, keys, prefixes, nodes, labelled edges, terminal markers, insertion, lookup, deletion, prefix search, traversal, compressed variants, invariants and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    TRIE
    PREFIX_TREE
    STANDARD_TRIE
    COMPRESSED_TRIE
    RADIX_TREE
    PATRICIA_TRIE
    BINARY_TRIE
    TERNARY_SEARCH_TRIE
    MUTABLE_TRIE
    IMMUTABLE_TRIE
    PERSISTENT_TRIE
    NODE
    ROOT_NODE
    INTERNAL_NODE
    TERMINAL_NODE
    LEAF_NODE
    PARENT_NODE
    CHILD_NODE
    EDGE
    EDGE_LABEL
    SYMBOL
    CHARACTER
    TOKEN
    KEY
    KEY_SEQUENCE
    PREFIX
    SUFFIX
    VALUE
    PAYLOAD
    TERMINAL_MARKER
    END_OF_KEY_MARKER
    ALPHABET
    CHILD_MAP
    CHILD_ARRAY
    CHILD_REFERENCE
    PATH
    KEY_PATH
    PREFIX_PATH
    DEPTH
    HEIGHT
    SIZE
    NODE_COUNT
    KEY_COUNT
    OPERATION
    CREATE
    INSERT
    LOOKUP
    SEARCH
    PREFIX_SEARCH
    LONGEST_PREFIX_MATCH
    AUTOCOMPLETE
    DELETE
    REMOVE
    UPDATE
    TRAVERSE
    ITERATE
    ENUMERATE_KEYS
    COMPRESS
    SPLIT_EDGE
    MERGE_EDGE
    PRUNE
    INVARIANT
    ROOT_INVARIANT
    PREFIX_INVARIANT
    EDGE_LABEL_INVARIANT
    TERMINAL_INVARIANT
    KEY_PATH_INVARIANT
    COMPRESSION_INVARIANT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    MEMORY
    POINTER
    REFERENCE
    STRUCTURAL_SHARING
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_NODE
    HAS_ROOT
    HAS_EDGE
    HAS_CHILD
    HAS_PARENT
    HAS_LABEL
    HAS_SYMBOL
    HAS_KEY
    HAS_PREFIX
    HAS_VALUE
    HAS_PAYLOAD
    HAS_TERMINAL_MARKER
    PARENT_OF
    CHILD_OF
    CONNECTED_TO
    LABELLED_BY
    REPRESENTS
    PREFIX_OF
    SUFFIX_OF
    EXTENDS_PREFIX
    HAS_PATH
    HAS_DEPTH
    HAS_HEIGHT
    HAS_SIZE
    HAS_NODE_COUNT
    HAS_KEY_COUNT
    INSERTS
    LOOKS_UP
    SEARCHES
    SEARCHES_PREFIX
    MATCHES_PREFIX
    AUTOCOMPLETES
    DELETES
    REMOVES
    UPDATES
    TRAVERSES
    ITERATES
    ENUMERATES
    COMPRESSES
    SPLITS
    MERGES
    PRUNES
    POINTS_TO
    REFERENCES
    HAS_INVARIANT
    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 {
    TRIE_SPECIFICATIONS
    TRIE_IMPLEMENTATIONS
    SOURCE_CODE
    KEY_DATA
    SYMBOL_AND_ALPHABET_DATA
    NODE_DATA
    EDGE_AND_LABEL_DATA
    PREFIX_DATA
    VALUE_AND_PAYLOAD_DATA
    TERMINAL_MARKER_DATA
    INSERTION_TRACES
    LOOKUP_TRACES
    PREFIX_SEARCH_TRACES
    DELETION_TRACES
    COMPRESSION_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_TRIE_IDENTIFIERS
    NORMALISE_TRIE_TYPES
    NORMALISE_NODE_IDENTIFIERS
    NORMALISE_EDGE_IDENTIFIERS
    NORMALISE_SYMBOL_ENCODING
    NORMALISE_KEYS
    NORMALISE_PREFIXES
    NORMALISE_EDGE_LABELS
    NORMALISE_TERMINAL_MARKERS
    NORMALISE_VALUE_AND_PAYLOAD_TYPES
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_TRIE_NODE_KEY_AND_PATH_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS TRIE_REASONING_PIPELINE {
    TRIE_REFERENCE
      -> TRIE_IDENTIFICATION
      -> TRIE_TYPE_RESOLUTION
      -> ROOT_RESOLUTION
      -> NODE_EDGE_AND_LABEL_MAPPING
      -> KEY_PREFIX_AND_TERMINAL_MAPPING
      -> OPERATION_MAPPING
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS KEY_PATH_REASONING {
    KEY_SEQUENCE
      -> SYMBOL_SEQUENCE

    ROOT_NODE
      -> FIRST_SYMBOL_OR_EDGE_LABEL

    EACH_SYMBOL_OR_LABEL_SEGMENT
      -> CHILD_TRANSITION

    CHILD_TRANSITIONS
      -> KEY_PATH

    COMPLETE_KEY_PATH + TERMINAL_MARKER
      -> STORED_KEY
  }

  PROCESS INSERTION_REASONING {
    INSERT(KEY)
      -> START_AT_ROOT

    FOR EACH SYMBOL_OR_LABEL_SEGMENT
      -> FIND_MATCHING_CHILD_EDGE

    MATCH_EXISTS
      -> FOLLOW_EDGE

    MATCH_MISSING
      -> CREATE_NODE_AND_EDGE

    END_OF_KEY
      -> SET_TERMINAL_MARKER
      -> STORE_VALUE_IF_APPLICABLE

    RESULT
      -> KEY_COUNT_AND_NODE_COUNT_UPDATE
      -> INVARIANT_CHECK
  }

  PROCESS LOOKUP_REASONING {
    LOOKUP(KEY)
      -> START_AT_ROOT

    KEY_SYMBOLS
      -> FOLLOW_MATCHING_EDGES

    MISSING_EDGE
      -> NOT_FOUND

    ALL_KEY_SYMBOLS_CONSUMED
      -> CHECK_TERMINAL_MARKER

    TERMINAL_MARKER_PRESENT
      -> KEY_FOUND

    TERMINAL_MARKER_ABSENT
      -> PREFIX_ONLY_NOT_FULL_KEY
  }

  PROCESS PREFIX_SEARCH_REASONING {
    PREFIX
      -> FOLLOW_PREFIX_PATH

    PREFIX_PATH_NOT_FOUND
      -> NO_MATCHES

    PREFIX_PATH_FOUND
      -> PREFIX_NODE_OR_POSITION

    PREFIX_NODE_OR_POSITION
      -> TRAVERSE_DESCENDANTS

    TERMINAL_DESCENDANTS
      -> MATCHING_KEYS
  }

  PROCESS LONGEST_PREFIX_REASONING {
    QUERY_SEQUENCE
      -> START_AT_ROOT

    FOLLOW_MATCHING_PATH
      -> TRACK_LAST_TERMINAL_POSITION

    MATCH_FAILURE_OR_QUERY_END
      -> RETURN_LONGEST_TERMINAL_PREFIX_IF_ANY
  }

  PROCESS DELETION_REASONING {
    DELETE(KEY)
      -> LOOKUP_KEY_PATH

    KEY_NOT_FOUND
      -> NO_STATE_CHANGE

    KEY_FOUND
      -> REMOVE_TERMINAL_MARKER_OR_VALUE

    NODE_WITH_NO_CHILDREN_AND_NOT_TERMINAL
      -> PRUNE_UPWARD

    SHARED_PREFIX_NODE
      -> PRESERVE_NODE

    RESULT
      -> KEY_COUNT_AND_NODE_COUNT_UPDATE
      -> INVARIANT_CHECK
  }

  PROCESS COMPRESSED_TRIE_REASONING {
    COMPRESSED_TRIE
      -> EDGE_LABEL_MAY_CONTAIN_MULTIPLE_SYMBOLS

    INSERT_OR_LOOKUP
      -> LONGEST_COMMON_PREFIX_WITH_EDGE_LABEL

    PARTIAL_EDGE_MATCH
      -> SPLIT_EDGE

    REDUNDANT_SINGLE_CHILD_NONTERMINAL_NODE
      -> MERGE_EDGE_IF_VARIANT_PERMITS

    RESULT
      -> COMPRESSION_INVARIANT_CHECK
  }

  PROCESS AUTOCOMPLETE_REASONING {
    QUERY_PREFIX
      -> PREFIX_SEARCH

    MATCHING_KEYS
      -> OPTIONAL_RANKING_OR_LIMITING_POLICY

    RANKED_OR_ENUMERATED_KEYS
      -> AUTOCOMPLETE_RESULTS
  }

  PROCESS COMPLEXITY_REASONING {
    TRIE + OPERATION
      -> KEY_LENGTH_PREFIX_LENGTH_ALPHABET_AND_IMPLEMENTATION

    LOOKUP_OR_INSERT
      -> SYMBOL_OR_LABEL_TRANSITIONS

    PREFIX_SEARCH
      -> PREFIX_TRAVERSAL + OUTPUT_ENUMERATION

    DELETE
      -> KEY_PATH_LENGTH + PRUNING_COST

    CHILD_LOOKUP
      -> CHILD_REPRESENTATION_COST

    MEMORY_USAGE
      -> NODE_EDGE_LABEL_AND_CHILD_STORAGE

    COSTS
      -> TIME_AND_SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_TRIE_STATE(T1)
      + UPDATE
      -> NEW_TRIE_STATE(T2)

    T2
      -> COPY_CHANGED_PATH_IF_REQUIRED

    T1 + T2
      -> STRUCTURAL_SHARING

    T1
      -> PRESERVED
  }

  RULES {
    IF KEY_IS_STORED
    THEN REQUIRE COMPLETE_KEY_PATH_AND_TERMINAL_MARKER_OR_EQUIVALENT_END_STATE

    IF PATH_EXISTS_WITHOUT_TERMINAL_MARKER
    THEN DO_NOT ASSERT FULL_KEY_EXISTS

    IF PREFIX_IS_SEARCHED
    THEN DISTINGUISH PREFIX_MATCH_FROM_EXACT_KEY_MATCH

    IF COMPRESSED_TRIE_IS_USED
    THEN PRESERVE MULTI_SYMBOL_EDGE_LABELS

    IF KEY_IS_DELETED
    THEN PRESERVE NODES_REQUIRED_BY_OTHER_KEYS_OR_PREFIXES

    IF EDGE_IS_SPLIT
    THEN PRESERVE ALL_EXISTING_KEY_PATH_SEMANTICS

    IF PERSISTENT_TRIE_IS_UPDATED
    THEN PRESERVE PRIOR_TRIE_STATE

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND TRIE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        TRIE_IDENTITY_CERTAINTY,
        TRIE_TYPE_CERTAINTY,
        NODE_AND_EDGE_COMPLETENESS,
        EDGE_LABEL_CERTAINTY,
        TERMINAL_MARKER_COMPLETENESS,
        KEY_AND_PREFIX_COMPLETENESS,
        OPERATION_TRACE_COMPLETENESS,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF TERMINAL_MARKER_DATA_IS_UNKNOWN
    THEN REDUCE_EXACT_KEY_MEMBERSHIP_CONFIDENCE

    IF EDGE_LABEL_OR_COMPRESSION_DATA_IS_PARTIAL
    THEN REDUCE_PATH_AND_PREFIX_CONFIDENCE

    IF COMPLETE_KEY_PATH_AND_TERMINAL_DATA_CONFIRM_STATE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        TRIE_IDENTIFIER,
        TRIE_TYPE,
        KEY_ENCODING,
        ALPHABET,
        IMPLEMENTATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    TRIE != GENERAL_TREE
    TRIE != BINARY_SEARCH_TREE
    NODE != KEY
    EDGE_LABEL != NODE_VALUE
    PREFIX != FULL_KEY_IN_GENERAL
    PATH_EXISTENCE != KEY_MEMBERSHIP
    TERMINAL_NODE != LEAF_NODE_IN_ALL_TRIES
    LEAF_NODE != NECESSARILY_ONLY_KEY_END
    STANDARD_TRIE != COMPRESSED_TRIE
    RADIX_TREE != STANDARD_SINGLE_SYMBOL_EDGE_TRIE
    PREFIX_SEARCH != EXACT_LOOKUP
    LONGEST_PREFIX_MATCH != LEXICOGRAPHIC_MAXIMUM
    AUTOCOMPLETE != PREFIX_SEARCH_AS_IDENTICAL_OPERATION_WHEN_RANKING_OR_FILTERING_APPLIES
    PERSISTENT_TRIE != MUTABLE_TRIE
    COMPLEXITY_DEPENDS_ON_KEY_LENGTH_CHILD_REPRESENTATION_AND_TRIE_VARIANT
    ENCODING_AND_SYMBOL_SEGMENTATION_AFFECT_KEY_PATHS
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_TRIE_IDENTIFIER
    CHECK_TRIE_TYPE
    CHECK_ROOT
    CHECK_NODE_IDENTITIES
    CHECK_EDGE_IDENTITIES
    CHECK_EDGE_LABELS
    CHECK_KEY_ENCODING
    CHECK_PREFIX_RELATIONS
    CHECK_TERMINAL_MARKERS
    CHECK_KEY_PATHS
    CHECK_INSERTION
    CHECK_LOOKUP
    CHECK_PREFIX_SEARCH
    CHECK_LONGEST_PREFIX_MATCH
    CHECK_DELETION_AND_PRUNING
    CHECK_COMPRESSION_IF_APPLICABLE
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_TRIE_ENTITIES
    TRIE_TYPE_RELATIONS
    NODE_AND_EDGE_RELATIONS
    EDGE_LABEL_RELATIONS
    KEY_AND_PREFIX_RELATIONS
    TERMINAL_MARKER_RELATIONS
    KEY_PATH_RELATIONS
    INSERTION_RELATIONS
    LOOKUP_RELATIONS
    PREFIX_SEARCH_RELATIONS
    LONGEST_PREFIX_MATCH_RELATIONS
    AUTOCOMPLETE_RELATIONS
    DELETION_AND_PRUNING_RELATIONS
    COMPRESSION_RELATIONS
    TRIE_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 TRIE_OPERATION {
      NORMALISE
      RESOLVE_TRIE_NODE_KEY_AND_PATH_IDENTITIES
      UPDATE_NODE_AND_EDGE_SET
      UPDATE_EDGE_LABELS
      UPDATE_TERMINAL_MARKERS
      UPDATE_KEY_AND_NODE_COUNTS
      RECHECK_KEY_PATH_AND_COMPRESSION_INVARIANTS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_ENCODING_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_KEY_PATHS
      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_TRIE
      BY_TRIE_TYPE
      BY_NODE
      BY_EDGE
      BY_EDGE_LABEL
      BY_KEY
      BY_PREFIX
      BY_TERMINAL_MARKER
      BY_OPERATION
      BY_LOOKUP
      BY_PREFIX_SEARCH
      BY_AUTOCOMPLETE
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_KEY_PATHS
      TRACE_INSERTIONS
      TRACE_EXACT_LOOKUPS
      ANALYSE_PREFIX_SEARCH
      ANALYSE_LONGEST_PREFIX_MATCH
      TRACE_DELETIONS_AND_PRUNING
      ANALYSE_COMPRESSED_TRIES
      ANALYSE_AUTOCOMPLETE
      CHECK_TRIE_INVARIANTS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_TRIE_FROM_GENERAL_TREE_AND_BINARY_SEARCH_TREE
      DISTINGUISH_PREFIX_MATCH_FROM_EXACT_KEY_MEMBERSHIP
      PRESERVE_KEY_ENCODING_ALPHABET_EDGE_LABEL_TRIE_VARIANT_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_STANDARD_FROM_COMPRESSED_TRIES
      PRESERVE_TERMINAL_MARKERS_KEY_PATH_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_TRIE_INFERENCE
    }
  }

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

END FLOW