Rooted Tree Ontology

FLOW ALGEBRA
ROOTED TREE ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Graph and Network Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/rooted-tree-ontology.html
Version: 1.0 | Date: 2026-10-14
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source page wording not independently verified.

1. ONTOLOGY IDENTITY
ontology_id: kireth:mathematical-entities:rooted-tree
canonical_entity: RootedTree
parent_class: Tree
related_classes: Graph, Vertex, Edge, Root, Parent, Child, Ancestor, Descendant, Leaf, Subtree, Forest
scope: Finite rooted trees; explicitly mark extensions to infinite trees.

2. TYPED ENTITIES
Vertex := unique identifier
Edge := unordered pair of distinct vertices
Tree := (V: Set[Vertex], E: Set[Edge])
RootedTree := (V: Set[Vertex], E: Set[Edge], root: Vertex)
Parent := partial map V -> V
Children := map V -> Set[Vertex]
Depth := map V -> NaturalNumber
Subtree := rooted induced descendant tree

3. CONSTRUCTION AND INVARIANTS
require |V| >= 1
require root in V
require E subset {{u,v} | u,v in V and u != v}
require graph (V,E) connected and acyclic
assert |E| = |V| - 1
assert unique simple undirected path between every two vertices
assert parent(root) undefined
assert for every v != root, parent(v) is the unique neighbour of v on the path to root
assert depth(root) = 0
assert depth(v) = depth(parent(v)) + 1 for v != root
assert no vertex is its own strict ancestor

4. RELATIONSHIP ALGEBRA
parent_of(p,c) := parent(c) = p
child_of(c,p) := parent_of(p,c)
ancestor_of(a,v) := a occurs strictly before v on root-to-v path
descendant_of(v,a) := ancestor_of(a,v)
root_of(r,T) := r = T.root
sibling_of(u,v) := u != v and parent(u) defined and parent(u) = parent(v)
leaf(v) := Children(v) = empty set
internal(v) := Children(v) != empty set
subtree_rooted_at(v) := induced graph on {v} union descendants(v)
lowest_common_ancestor(u,v) := deepest common ancestor allowing each vertex itself

5. EXECUTABLE FLOW RULES
flow validate_rooted_tree(T):
  verify vertex identifiers unique
  verify endpoints of every edge exist
  verify root exists
  verify connected(T) and acyclic(T)
  derive parent and depth by traversal from root
  return VALID or structured errors

flow derive_ancestry(T):
  require validate_rooted_tree(T) == VALID
  for each vertex v != root:
    emit parent_of(parent(v),v)
    emit child_of(v,parent(v))
  compute transitive closure of parent_of as strict ancestor_of
  emit descendant_of as inverse of ancestor_of

flow classify_vertices(T):
  require VALID
  for each v in V:
    if Children(v) empty: emit Leaf(v)
    else: emit InternalVertex(v)
  emit Root(root)

flow query_subtree(T,v):
  require VALID and v in V
  return induced descendant subtree with root v

6. MATHEMATICAL INFERENCE
R1: parent_of(a,b) and parent_of(b,c) => ancestor_of(a,c)
R2: ancestor_of(a,b) and ancestor_of(b,c) => ancestor_of(a,c)
R3: parent_of(a,b) => depth(b) = depth(a)+1
R4: v != root => exactly one parent(v)
R5: connected(T) and acyclic(T) => unique simple path between each pair
R6: |V|=n finite and Tree(T) => |E|=n-1
R7: ancestor_of(a,b) => not ancestor_of(b,a)
R8: subtree_rooted_at(v) => every included vertex has root-to-vertex path passing through v

7. SEMANTIC DISTINCTIONS
RootedTree != UnrootedTree: a distinguished root determines parent/child direction.
RootedTree != DirectedAcyclicGraph: a DAG can have multiple parents or alternative paths.
RootedTree != BinaryTree: a general rooted tree may have any finite number of children.
RootedTree != SpanningTree: spanning tree refers to a tree spanning a specified graph.
RootedTree != OntologyHierarchy: an ontology may allow multiple inheritance and cycles in some relations.
A one-vertex rooted tree is valid and its root is also a leaf.

8. CONFIDENCE AND PROVENANCE
confidence: 1.0 for formal consequences under validated axioms
confidence: contextual for mappings to external knowledge graphs
provenance.source_url: URL above
provenance.source_verification: not independently verified
provenance.formalisation: authored mathematical model

9. VALIDATION
check graph connectivity, acyclicity, vertex uniqueness, edge endpoints and root membership
check exactly one parent for every non-root vertex
check depth consistency and no ancestry cycles
check inferred parent/child and ancestor/descendant inverse relations
reject cycles, disconnected components, missing root and multiple-parent assignments

10. FLOW HASH AND UPDATE MODEL
FLOW_HASH := SHA256(canonical_utf8(ontology_id + version + normalised_entities + axioms + inference_rules))
UPDATE_MODEL := versioned; preserve provenance; recompute hash when canonical semantics change
Canonicalisation must fix ordering, Unicode normalisation and field serialization.

11. AI CONSUMPTION
entity_type: MathematicalGraphStructure
input: validated vertex set, edge set, root identifier
output: parent map, children map, depth, ancestors, descendants, leaves, subtrees
reasoning: deterministic graph traversal and typed logical inference
limitations: finite-tree algorithms here do not automatically extend to arbitrary infinite trees
interoperability: graph theory, data structures, taxonomy, dependency modelling, hierarchical knowledge representation

END FLOW ALGEBRA