Tree Ontology

AI SEARCH

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

FLOW TREE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Tree Ontology"
    PURPOSE = "Formalise tree data structures, nodes, roots, parent-child relations, subtrees, depth, height, traversal, search, insertion, deletion, ordering, balancing, invariants and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    TREE
    ROOTED_TREE
    ORDERED_TREE
    UNORDERED_TREE
    BINARY_TREE
    FULL_BINARY_TREE
    COMPLETE_BINARY_TREE
    PERFECT_BINARY_TREE
    BALANCED_TREE
    BINARY_SEARCH_TREE
    AVL_TREE
    RED_BLACK_TREE
    B_TREE
    B_PLUS_TREE
    TRIE
    HEAP_TREE
    NODE
    ROOT_NODE
    INTERNAL_NODE
    LEAF_NODE
    PARENT_NODE
    CHILD_NODE
    SIBLING_NODE
    ANCESTOR
    DESCENDANT
    SUBTREE
    EDGE
    VALUE
    KEY
    LEFT_CHILD
    RIGHT_CHILD
    DEPTH
    HEIGHT
    LEVEL
    DEGREE
    PATH
    ROOT_TO_NODE_PATH
    OPERATION
    CREATE
    INSERT
    DELETE
    SEARCH
    LOOKUP
    UPDATE
    TRAVERSE
    PREORDER_TRAVERSAL
    INORDER_TRAVERSAL
    POSTORDER_TRAVERSAL
    LEVEL_ORDER_TRAVERSAL
    ROTATE_LEFT
    ROTATE_RIGHT
    REBALANCE
    SPLIT
    MERGE
    INVARIANT
    ACYCLICITY_INVARIANT
    CONNECTIVITY_INVARIANT
    PARENT_INVARIANT
    BINARY_ARITY_INVARIANT
    SEARCH_ORDER_INVARIANT
    BALANCE_INVARIANT
    COLOUR_INVARIANT
    NODE_CAPACITY_INVARIANT
    ORDERING
    BALANCE_FACTOR
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    MEMORY
    POINTER
    REFERENCE
    IMPLEMENTATION
    MUTABLE_TREE
    IMMUTABLE_TREE
    PERSISTENT_TREE
    STRUCTURAL_SHARING
    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_KEY
    HAS_VALUE
    PARENT_OF
    CHILD_OF
    LEFT_CHILD_OF
    RIGHT_CHILD_OF
    SIBLING_OF
    ANCESTOR_OF
    DESCENDANT_OF
    ROOT_OF
    HAS_SUBTREE
    CONNECTED_TO
    PRECEDES
    FOLLOWS
    HAS_DEPTH
    HAS_HEIGHT
    HAS_LEVEL
    HAS_DEGREE
    HAS_PATH
    INSERTS
    DELETES
    SEARCHES
    LOOKS_UP
    UPDATES
    TRAVERSES
    ROTATES
    REBALANCES
    SPLITS
    MERGES
    HAS_ORDERING
    HAS_BALANCE_FACTOR
    HAS_INVARIANT
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    POINTS_TO
    REFERENCES
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    TREE_SPECIFICATIONS
    TREE_IMPLEMENTATIONS
    SOURCE_CODE
    NODE_DATA
    KEY_AND_VALUE_DATA
    EDGE_DATA
    PARENT_CHILD_DATA
    ROOT_DATA
    TRAVERSAL_TRACES
    SEARCH_TRACES
    INSERTION_TRACES
    DELETION_TRACES
    ROTATION_AND_REBALANCING_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_TREE_IDENTIFIERS
    NORMALISE_TREE_TYPES
    NORMALISE_NODE_IDENTIFIERS
    NORMALISE_KEY_AND_VALUE_TYPES
    NORMALISE_EDGE_IDENTIFIERS
    NORMALISE_PARENT_CHILD_RELATIONS
    NORMALISE_DEPTH_HEIGHT_AND_LEVEL
    NORMALISE_TRAVERSAL_NAMES
    NORMALISE_OPERATION_NAMES
    NORMALISE_BALANCE_FACTORS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_TREE_NODE_AND_EDGE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS TREE_REASONING_PIPELINE {
    TREE_REFERENCE
      -> TREE_IDENTIFICATION
      -> TREE_TYPE_RESOLUTION
      -> ROOT_NODE_RESOLUTION
      -> NODE_AND_EDGE_MAPPING
      -> STRUCTURAL_PROPERTY_MAPPING
      -> OPERATION_MAPPING
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS STRUCTURE_REASONING {
    TREE
      -> ROOT_NODE

    ROOT_NODE
      -> CHILD_RELATIONS

    CHILD_RELATIONS
      -> DESCENDANT_RELATIONS

    NODE
      -> PARENT_RELATION_EXCEPT_ROOT

    NODE_AND_EDGE_SET
      -> CONNECTIVITY_AND_ACYCLICITY_CHECK
  }

  PROCESS DEPTH_HEIGHT_REASONING {
    ROOT_NODE
      -> DEPTH = 0

    CHILD_NODE
      -> DEPTH = PARENT_DEPTH + 1

    LEAF_NODE
      -> HEIGHT = 0

    INTERNAL_NODE
      -> HEIGHT = 1 + MAX(CHILD_HEIGHTS)

    TREE_HEIGHT
      -> ROOT_HEIGHT
  }

  PROCESS BINARY_TREE_REASONING {
    BINARY_TREE
      -> EACH_NODE_HAS_AT_MOST_TWO_CHILDREN

    CHILDREN
      -> LEFT_CHILD
      -> RIGHT_CHILD

    BINARY_STRUCTURE
      -> BINARY_ARITY_INVARIANT
  }

  PROCESS SEARCH_TREE_REASONING {
    BINARY_SEARCH_TREE
      -> SEARCH_ORDER_INVARIANT

    NODE_WITH_KEY(K)
      -> LEFT_SUBTREE_KEYS
      -> RIGHT_SUBTREE_KEYS

    SEARCH(K)
      -> COMPARE_WITH_CURRENT_NODE_KEY

    K < CURRENT_KEY
      -> SEARCH_LEFT_SUBTREE

    K > CURRENT_KEY
      -> SEARCH_RIGHT_SUBTREE

    K == CURRENT_KEY
      -> MATCH
  }

  PROCESS INSERTION_REASONING {
    INSERT(KEY_VALUE)
      -> TREE_TYPE_SPECIFIC_SEARCH

    INSERTION_POSITION
      -> CREATE_OR_ATTACH_NODE

    ATTACH_NODE
      -> UPDATE_PARENT_CHILD_RELATIONS

    BALANCED_TREE
      -> UPDATE_HEIGHT_OR_BALANCE_METADATA
      -> REBALANCE_IF_REQUIRED

    RESULT
      -> INVARIANT_CHECK
  }

  PROCESS DELETION_REASONING {
    DELETE(TARGET)
      -> TARGET_SEARCH

    TARGET_NODE
      -> ZERO_CHILD_CASE
      OR -> ONE_CHILD_CASE
      OR -> MULTIPLE_CHILD_CASE

    STRUCTURAL_REPLACEMENT
      -> UPDATE_PARENT_CHILD_RELATIONS

    BALANCED_TREE
      -> RECOMPUTE_BALANCE
      -> REBALANCE_IF_REQUIRED

    RESULT
      -> INVARIANT_CHECK
  }

  PROCESS TRAVERSAL_REASONING {
    PREORDER
      -> VISIT_NODE
      -> TRAVERSE_CHILD_SUBTREES

    INORDER_BINARY
      -> TRAVERSE_LEFT
      -> VISIT_NODE
      -> TRAVERSE_RIGHT

    POSTORDER
      -> TRAVERSE_CHILD_SUBTREES
      -> VISIT_NODE

    LEVEL_ORDER
      -> VISIT_NODES_BY_DEPTH
  }

  PROCESS BALANCING_REASONING {
    BALANCED_TREE_UPDATE
      -> BALANCE_STATE

    BALANCE_STATE
      -> VALID_OR_IMBALANCED

    IMBALANCED
      -> ROTATION_OR_RESTRUCTURING

    ROTATION_OR_RESTRUCTURING
      -> UPDATED_PARENT_CHILD_RELATIONS

    UPDATED_STRUCTURE
      -> BALANCE_INVARIANT_CHECK
  }

  PROCESS PATH_REASONING {
    NODE_A + NODE_B
      -> ANCESTOR_AND_PARENT_RELATIONS

    RELATIONS
      -> PATH_CANDIDATE

    TREE_UNIQUENESS_PROPERTY
      -> UNIQUE_SIMPLE_PATH_BETWEEN_CONNECTED_NODES
  }

  PROCESS COMPLEXITY_REASONING {
    TREE + OPERATION
      -> NODE_COUNT_HEIGHT_AND_TREE_TYPE

    SEARCH_INSERT_DELETE
      -> TRAVERSAL_DEPTH

    BALANCED_SEARCH_TREE
      -> HEIGHT_BOUND_CONTEXT

    UNBALANCED_TREE
      -> ACTUAL_HEIGHT_CONTEXT

    TRAVERSAL
      -> VISITED_NODE_COUNT

    COST
      -> TIME_AND_SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_TREE_STATE(T1)
      + UPDATE
      -> NEW_TREE_STATE(T2)

    T2
      -> COPY_CHANGED_PATH_IF_REQUIRED

    T1 + T2
      -> STRUCTURAL_SHARING

    T1
      -> PRESERVED
  }

  RULES {
    IF TREE_IS_ROOTED
    THEN REQUIRE ONE_DESIGNATED_ROOT_PER_TREE_CONTEXT

    IF NODE_IS_NOT_ROOT
    THEN REQUIRE ONE_PARENT_IN_STANDARD_ROOTED_TREE_CONTEXT

    IF BINARY_TREE_IS_ASSERTED
    THEN REQUIRE AT_MOST_TWO_CHILDREN_PER_NODE

    IF BINARY_SEARCH_TREE_IS_ASSERTED
    THEN REQUIRE DEFINED_KEY_ORDERING_INVARIANT

    IF BALANCED_TREE_IS_ASSERTED
    THEN REQUIRE TREE_TYPE_SPECIFIC_BALANCE_INVARIANT

    IF TREE_STRUCTURE_IS_UPDATED
    THEN RECHECK CONNECTIVITY_ACYCLICITY_AND_TYPE_SPECIFIC_INVARIANTS

    IF PERSISTENT_TREE_IS_UPDATED
    THEN PRESERVE PRIOR_TREE_STATE

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND TREE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        TREE_IDENTITY_CERTAINTY,
        TREE_TYPE_CERTAINTY,
        NODE_IDENTITY_COMPLETENESS,
        EDGE_AND_PARENT_CHILD_COMPLETENESS,
        ROOT_CERTAINTY,
        OPERATION_TRACE_COMPLETENESS,
        INVARIANT_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF NODE_OR_EDGE_DATA_IS_PARTIAL
    THEN REDUCE_STRUCTURE_PATH_AND_HEIGHT_CONFIDENCE

    IF TREE_TYPE_IS_UNKNOWN
    THEN REDUCE_ORDERING_AND_BALANCE_CONFIDENCE

    IF COMPLETE_STRUCTURE_AND_OPERATION_TRACE_CONFIRM_INVARIANTS
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        TREE_IDENTIFIER,
        TREE_TYPE,
        NODE_IDENTIFIER,
        KEY_TYPE,
        IMPLEMENTATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    TREE != GENERAL_GRAPH
    NODE != KEY
    NODE != VALUE
    ROOT_NODE != LEAF_NODE_IN_GENERAL
    PARENT != ANCESTOR_AS_IDENTICAL_RELATION
    CHILD != DESCENDANT_AS_IDENTICAL_RELATION
    DEPTH != HEIGHT
    LEVEL != HEIGHT
    BINARY_TREE != BINARY_SEARCH_TREE
    BINARY_SEARCH_TREE != BALANCED_TREE
    BALANCED_TREE != PERFECT_TREE
    COMPLETE_BINARY_TREE != FULL_BINARY_TREE
    HEAP_TREE != BINARY_SEARCH_TREE
    TRAVERSAL_ORDER != SORTED_ORDER_EXCEPT_WHERE_INVARIANTS_SUPPORT_IT
    ROTATION != VALUE_REORDERING_WITHOUT_STRUCTURAL_CONTEXT
    PERSISTENT_TREE != MUTABLE_TREE
    COMPLEXITY_DEPENDS_ON_TREE_TYPE_HEIGHT_OPERATION_AND_IMPLEMENTATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_TREE_IDENTIFIER
    CHECK_TREE_TYPE
    CHECK_ROOT
    CHECK_NODE_IDENTITIES
    CHECK_EDGE_IDENTITIES
    CHECK_PARENT_CHILD_RELATIONS
    CHECK_CONNECTIVITY
    CHECK_ACYCLICITY
    CHECK_DEPTH_HEIGHT_AND_LEVEL
    CHECK_BINARY_ARITY_IF_APPLICABLE
    CHECK_SEARCH_ORDER_IF_APPLICABLE
    CHECK_BALANCE_IF_APPLICABLE
    CHECK_INSERTION_AND_DELETION
    CHECK_TRAVERSALS
    CHECK_ROTATIONS_AND_REBALANCING
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_TREE_ENTITIES
    TREE_TYPE_RELATIONS
    ROOT_RELATIONS
    NODE_AND_EDGE_RELATIONS
    PARENT_CHILD_RELATIONS
    ANCESTOR_DESCENDANT_RELATIONS
    SUBTREE_RELATIONS
    DEPTH_HEIGHT_AND_LEVEL_RELATIONS
    PATH_RELATIONS
    SEARCH_RELATIONS
    INSERTION_RELATIONS
    DELETION_RELATIONS
    TRAVERSAL_RELATIONS
    ROTATION_AND_REBALANCING_RELATIONS
    TREE_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 TREE_OPERATION {
      NORMALISE
      RESOLVE_TREE_NODE_AND_EDGE_IDENTITIES
      UPDATE_NODE_AND_EDGE_SET
      UPDATE_PARENT_CHILD_RELATIONS
      UPDATE_ROOT_IF_REQUIRED
      RECOMPUTE_DEPTH_HEIGHT_AND_BALANCE
      RECHECK_INVARIANTS
      UPDATE_OPERATION_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      RECHECK_TREE_TYPE_AND_INVARIANTS
      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_TREE
      BY_TREE_TYPE
      BY_ROOT
      BY_NODE
      BY_EDGE
      BY_PARENT
      BY_CHILD
      BY_ANCESTOR
      BY_SUBTREE
      BY_DEPTH
      BY_HEIGHT
      BY_OPERATION
      BY_TRAVERSAL
      BY_INVARIANT
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_TREE_STRUCTURE
      COMPUTE_DEPTH_AND_HEIGHT
      ANALYSE_BINARY_TREES
      ANALYSE_SEARCH_TREES
      TRACE_INSERTIONS
      TRACE_DELETIONS
      TRACE_TRAVERSALS
      ANALYSE_BALANCING
      ANALYSE_PATHS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_TREE_FROM_GENERAL_GRAPH
      DISTINGUISH_NODE_KEY_AND_VALUE
      DISTINGUISH_DEPTH_HEIGHT_AND_LEVEL
      PRESERVE_TREE_TYPE_ROOT_STRUCTURE_ORDERING_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_BINARY_TREE_SEARCH_TREE_AND_BALANCED_TREE
      PRESERVE_TREE_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_TREE_INFERENCE
    }
  }

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

END FLOW