Search Tree Ontology

FLOW ALGEBRA
SEARCH TREE ONTOLOGY
Kireth Semantic Library | Discrete AI Mathematics
Version: 1.0 | Date: 2026-10-11
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/search-tree-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Domain synthesis; source webpage not independently verified

1. PURPOSE
Represent search trees as typed mathematical structures for state-space exploration, inference, planning, constraint solving, and optimisation. Distinguish a search tree of paths from a state graph: multiple tree nodes may represent the same underlying state.

2. TYPES
State := immutable description of a problem configuration
Action := applicable transition operator
TreeNode := (id, state, parent_id?, incoming_action?, depth, path_cost)
TreeEdge := (parent_id, child_id, action, step_cost)
SearchTree := (nodes, edges, root_id)
Frontier := collection of generated but unexpanded nodes
Explored := set of states or node identifiers, according to algorithm
GoalPredicate := State -> Bool
SuccessorFunction := State -> finite sequence of (Action, State, Cost)
Heuristic := State -> nonnegative real (when appropriate)
SearchResult := Success(path, cost) | Failure | Cutoff | Unknown

3. STRUCTURAL AXIOMS
A1: Root exists and has no parent.
A2: Every non-root tree node has exactly one parent.
A3: No node is its own ancestor; the directed tree is acyclic.
A4: Every node is reachable from the root by exactly one tree path.
A5: For each edge (u,v,a,c), state(v) is a successor of state(u) under a.
A6: depth(root)=0; depth(v)=depth(parent(v))+1.
A7: g(root)=0; g(v)=g(parent(v))+step_cost(parent(v),v).
A8: A repeated state may occur in distinct tree nodes; state deduplication is an optional graph-search policy.

4. TYPED RELATIONSHIPS
HAS_ROOT: SearchTree x TreeNode
HAS_NODE: SearchTree x TreeNode
HAS_EDGE: SearchTree x TreeEdge
PARENT_OF: TreeNode x TreeNode
CHILD_OF: TreeNode x TreeNode
ANCESTOR_OF: TreeNode x TreeNode
REPRESENTS_STATE: TreeNode x State
EXPANDS_TO: TreeNode x TreeNode
GENERATED_BY: TreeNode x Action
SATISFIES_GOAL: TreeNode x GoalPredicate
IN_FRONTIER: TreeNode x Frontier
HAS_PATH_COST: TreeNode x Real
HAS_HEURISTIC_VALUE: TreeNode x Real
PRUNED_BY: TreeNode x PruningRule

5. EXECUTION SEMANTICS
initialise(problem):
  root := node(problem.initial_state, null, null, 0, 0)
  frontier := [root]
  explored := empty
  return (root, frontier, explored)

expand(node):
  for each (action, next_state, cost) in successors(node.state):
    require action applicable to node.state
    create child with parent=node and path_cost=node.path_cost+cost
    yield child

search(problem, policy):
  frontier := policy.initial_frontier(root)
  while frontier not empty:
    node := policy.remove_next(frontier)
    if goal(node.state): return Success(reconstruct(node), node.path_cost)
    if policy.should_expand(node):
      for child in expand(node):
        if policy.accept(child): policy.insert(frontier, child)
  return Failure only if finite/exhaustively explored under a complete policy

6. SEARCH POLICIES
BFS: FIFO frontier; complete for finite branching factor and finite shallowest goal depth; shortest number-of-edges path when edges have equal cost.
DFS: LIFO frontier; finite-memory advantages in depth-first traversal; not complete on infinite-depth trees without safeguards.
DLS: DFS with explicit depth bound; Cutoff distinct from Failure.
IDS: increasing depth limits; complete for finite branching factor when a goal has finite depth.
UCS: priority by accumulated cost g; optimal under suitable positive lower-bounded step-cost assumptions.
GreedyBestFirst: priority by heuristic h; neither completeness nor optimality is guaranteed in general.
AStar: priority by f=g+h; optimality depends on heuristic conditions, cost assumptions, and graph-search implementation.
BranchAndBound: prune only when a valid bound proves no improvement over incumbent is possible.
Backtracking: explore partial assignments; prune on constraint violation.

7. INFERENCE RULES
R1 ROOT: root(T)=r -> depth(r)=0.
R2 PARENT: parent(v)=u -> child(u,v).
R3 ANCESTOR_BASE: parent(v)=u -> ancestor(u,v).
R4 ANCESTOR_TRANSITIVE: ancestor(u,v) and ancestor(v,w) -> ancestor(u,w).
R5 PATH_COST: edge(u,v,c) and g(u)=k -> g(v)=k+c.
R6 GOAL: goal(state(n))=true -> candidate_solution(n).
R7 SOUND_PRUNE: lower_bound(n)>=incumbent for minimisation -> prune(n), provided lower_bound is admissible for every completion.
R8 REPEATED_STATE: state(u)=state(v) does not imply u=v.
R9 DOMINANCE: for equivalent future possibilities, a state record with no higher cost can dominate a higher-cost duplicate when the required assumptions hold.

8. MATHEMATICAL PROPERTIES
Branching factor b := maximum or average number of children, as specified.
Depth d := depth of a shallowest goal node.
Maximum search depth m := maximum explored depth, potentially infinite.
Full b-ary tree nodes through depth d: sum_{i=0}^{d} b^i = (b^(d+1)-1)/(b-1) for b != 1.
For b=1: node count = d+1.
BFS worst-case time and frontier space are exponential in d for b>1, commonly O(b^(d+1)) for tree search.
DFS worst-case time O(b^m) and stack memory O(bm) for standard tree-search bookkeeping with finite m.
IDS worst-case time O(b^d) for b>1 and stack memory O(bd), under standard assumptions.
These are model-dependent bounds, not universal guarantees for arbitrary graph-search implementations.

9. WORKED EXAMPLE
Initial state S; actions produce A and B.
A produces C; B produces D; goal(D)=true.
Tree edges: S->A, S->B, A->C, B->D.
BFS visitation: S, A, B, C, D (assuming left-to-right child order).
Returned path: S->B->D; depth=2.
If each edge cost=1, path cost=2.
Changing action costs can invalidate BFS cost optimality; use UCS when cost optimality is required.

10. CORRECTNESS OBLIGATIONS
C1: Every generated child follows an applicable action.
C2: Reconstructed solution is a valid path from initial state to goal.
C3: Pruning rules preserve at least one optimal solution when optimality is claimed.
C4: Termination assumptions are explicit: finite tree, bounded depth, or fair complete exploration.
C5: Priority and tie-breaking semantics are specified for reproducibility.
C6: Negative or zero step costs are handled explicitly before asserting UCS/A* guarantees.

11. SEMANTIC_EQUIVALENCE
"search tree" ~= "tree of search paths" when nodes denote distinct path occurrences.
"state-space graph" != "search tree" because graph states may be shared across paths.
"search node" != "state" because nodes also carry parent, depth and cost metadata.
"pruning" != "goal failure" because pruning depends on a justified exclusion rule.
"frontier" ~= "open list" in implementations using an open-list search structure.

12. VALIDATION
V1: Unique node identifiers.
V2: Exactly one root; no cycles; each non-root has one parent.
V3: All edge endpoints exist; every child depth is parent depth + 1.
V4: Edge actions agree with successor function.
V5: Path costs equal accumulated edge costs.
V6: A reported solution ends in a goal state.
V7: A Failure result is not emitted after an incomplete cutoff.
V8: Claims of optimality include algorithm-specific assumptions.
V9: Complexity bounds declare branching and depth assumptions.

13. CONFIDENCE
Formal tree axioms: HIGH.
Algorithmic guarantees: HIGH only when stated assumptions hold.
Heuristic quality: CONTEXT_DEPENDENT.
Application-specific performance: EMPIRICAL; requires measured evidence.

14. FLOW_HASH
Algorithm: SHA-256 over canonical UTF-8 bytes of the final published file.
Value: COMPUTE_ON_PUBLICATION (not fabricated).
Canonicalisation: preserve LF line endings and stable field order.

15. UPDATE_MODEL
Versioning: semantic versioning; increment when type contracts or inference rules change.
Triggers: new algorithms, corrected complexity conditions, improved proofs, ontology alignment updates.
Checks: re-run V1-V9 and verify example traces.
Provenance: retain author, version, source URL and modification date.

16. AI_CONSUMPTION
Input: problem definition, states, successor function, goal predicate, cost model, policy.
Output: typed tree trace, expanded nodes, candidate path, proof conditions, result status.
Guardrails: do not equate incomplete search with unsatisfiability; do not claim shortest or optimal paths without conditions; distinguish tree search from graph search.
Cross-links: Graph Algorithms Ontology; Constraint Satisfaction Ontology; Backtracking Ontology; Branch and Bound Ontology; Algorithm Analysis Ontology; Knowledge Graph Mathematics Ontology.

END FLOW ALGEBRA