Recursive Graph Entity Ontology

FLOW ALGEBRA
Recursive Graph Entity Ontology — Kireth Semantic Library
Version: 1.0 | Date: 2026-10-14
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/recursive-mathematical-entities/recursive-graph-entity-ontology.html
Source alignment: pending verification of webpage content.
Authors: Mark Higgins — Sky (Recursive AI)

1. PURPOSE
Represent graphs defined, generated, traversed, or decomposed recursively with explicit typing, termination, provenance and verifiable graph invariants.

2. TYPES
Graph := (V: Set[Vertex], E: Set[Edge], directed: Bool)
Vertex := (id: Identifier, attributes: Map)
Edge := (source: Vertex, target: Vertex, attributes: Map)
RecursiveGraph := (base: Graph, expansion: ExpansionRule, depth: Nat | Infinity, semantics: Semantics)
ExpansionRule := (input: Graph, parameters: Map) -> Graph
GraphState := (graph: Graph, iteration: Nat, visited: Set[Vertex])
GraphRelation := (source: Vertex, predicate: RelationType, target: Vertex)
TerminationCertificate := (measure: State -> WellFoundedOrder, proof: Evidence)

3. RELATIONSHIPS
HAS_VERTEX(Graph, Vertex)
HAS_EDGE(Graph, Edge)
CONNECTS(Edge, Vertex, Vertex)
EXPANDS_TO(GraphState, GraphState)
HAS_BASE_CASE(RecursiveGraph, Graph)
USES_RECURSION_RULE(RecursiveGraph, ExpansionRule)
DEPENDS_ON(GraphState, GraphState)
REACHABLE_FROM(Vertex, Vertex)
IS_SUBGRAPH_OF(Graph, Graph)
HAS_TERMINATION_PROOF(RecursiveGraph, TerminationCertificate)

4. FORMAL SEMANTICS
G_0 = B, where B is the declared base graph.
G_(n+1) = F(G_n), where F is a well-typed graph expansion rule.
For cumulative construction, require V_n subseteq V_(n+1) and E_n subseteq E_(n+1).
For replacement rewriting, monotonic growth is NOT assumed.
Finite-depth recursive graph: G_k = F^k(B).
Infinite cumulative graph: G_infinity = union_(n>=0) G_n, provided inclusions are compatible.
Least fixed-point semantics: mu F, only when F acts monotonically on a suitable complete lattice.

5. INFERENCE RULES
BASE: VALID_GRAPH(B) => VALID_STATE(G_0).
STEP: VALID_STATE(G_n) and PRESERVES_INVARIANTS(F,G_n) => VALID_STATE(G_(n+1)).
REACHABILITY_BASE: EDGE(u,v) => REACHABLE(u,v).
REACHABILITY_STEP: REACHABLE(u,v) and EDGE(v,w) => REACHABLE(u,w).
REACHABILITY_IDENTITY: REACHABLE(u,u) only when reflexive reachability is requested.
SUBGRAPH_TRANSITIVITY: SUBGRAPH(A,B) and SUBGRAPH(B,C) => SUBGRAPH(A,C).
TERMINATION: a strictly decreasing well-founded measure on every recursive call proves termination of finite recursive evaluation.
CYCLE_POLICY: graph cycles are allowed; recursive evaluation must use visited-state detection, memoisation or another sound termination mechanism when appropriate.

6. VALIDATION
- Vertex identifiers are unique within each graph.
- Every edge endpoint belongs to the graph's vertex set.
- Directed and undirected semantics are declared; undirected edges are treated as unordered endpoint pairs.
- Parallel edges and self-loops are permitted only when the graph model declares them.
- Base cases and expansion rules are well typed.
- The recursion depth is a nonnegative integer or an explicitly defined infinite construction.
- Fixed-point claims require suitable order-theoretic assumptions.
- Recursive traversal specifies cycle handling and stopping conditions.
- Reachability inference does not silently assume symmetry for directed graphs.

7. WORKED EXAMPLES
Example A — Recursive path:
B: V={v0}, E={}.
F adds vertex v_(n+1) and edge (v_n,v_(n+1)).
G_2: V={v0,v1,v2}; E={(v0,v1),(v1,v2)}.
Reachable(v0,v2) follows by transitivity.

Example B — Binary tree:
B: a single root vertex r.
At each expansion, add two children to every leaf at the previous depth.
After depth d, vertex count = 2^(d+1)-1 and edge count = 2^(d+1)-2.
These counts assume no shared child vertices and expansion through depth d.

Example C — Recursive graph traversal:
DFS(v,visited): if v in visited, return visited; otherwise mark v visited and recursively process each unvisited neighbour.
For a finite graph, each vertex is marked at most once, ensuring termination.

8. SEMANTIC_EQUIVALENCE
recursive graph construction ~ iterative application of a graph expansion operator, for equal base, rule and iteration count.
recursive reachability ~ transitive closure of the edge relation, with reflexive closure included only when specified.
recursive tree ~ a special case of recursive graph with tree constraints.
NOT_EQUIVALENT: graph recursion and acyclic graph; recursive graphs may contain cycles.

9. CONFIDENCE
Mathematical definitions: high confidence under declared assumptions.
Instance-level inferences: confidence depends on validated input graph and rule completeness.
Unverified source-page alignment: pending.

10. FLOW_HASH
Canonicalise type declarations, sorted vertices/edges, relation predicates, expansion rules, semantics and version; encode UTF-8; compute SHA-256. Store computed digest at ingestion. No digest is asserted here without canonical execution.

11. UPDATE_MODEL
When graph data, recursion rules, invariants or semantics change: increment version, revalidate edges and proofs, recompute reachability as needed, invalidate dependent inferences and regenerate FLOW_HASH.

12. AI_CONSUMPTION
Input: typed graph, base case, expansion or traversal rule, recursion depth, graph semantics.
Process: type-check -> validate graph -> apply rule or traverse -> check invariants and termination -> derive relations -> record provenance.
Output: graph state, inferred relations, validation report, uncertainty/limitations, provenance, version and hash.
Reject or flag: dangling edges, undeclared graph semantics, unsupported fixed-point assumptions, unbounded recursion without a defined interpretation.

END FLOW ALGEBRA