State Space Ontology

FLOW ALGEBRA
STATE SPACE ONTOLOGY
Kireth Semantic Library | Discrete AI Mathematics
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/state-space-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Domain-grounded synthesis; source webpage not independently verified.

01. PURPOSE
Model states, actions, transitions, goals, constraints and search procedures as typed, verifiable mathematical objects. Distinguish the state space (possible configurations) from the search tree (paths explored by a procedure).

02. TYPE SYSTEM
StateSpace := (S, A, T, S0, G)
S : Set[State]
A : Set[Action]
T : Relation[State, Action, State]
S0 : Subset[S]                         # admissible initial states
G : Subset[S]                          # goal states
State := immutable configuration of variables
Action := applicable operation on a state
Transition := (source:State, action:Action, target:State)
Path := finite sequence of transitions with adjacent endpoints
Cost := RealNonNegative
Heuristic := State -> RealNonNegative
Constraint := State -> Boolean
Policy := State -> Action (partial)
Visited := Subset[S]
Frontier := Collection[SearchNode]
SearchNode := (state:State, parent:SearchNode?, action:Action?, depth:Nat, g:Cost)

03. RELATIONSHIPS
HAS_STATE(StateSpace, State)
HAS_ACTION(StateSpace, Action)
HAS_INITIAL_STATE(StateSpace, State)
HAS_GOAL_STATE(StateSpace, State)
TRANSITIONS_TO(State, Action, State)
REACHABLE_FROM(State, State)
SATISFIES(State, Constraint)
VIOLATES(State, Constraint)
REPRESENTS(SearchNode, State)
EXPANDS(SearchNode, SearchNode)
PRECEDES_ON_PATH(State, State)
ACHIEVES(Path, GoalState)

04. FORMAL SEMANTICS
applicable(a,s) iff exists s' in S : T(s,a,s').
successors(s) = {s' in S | exists a in A : T(s,a,s')}.
Reach_0(s) = {s}.
Reach_(k+1)(s) = Reach_k(s) union union_{x in Reach_k(s)} successors(x).
Reachable(s,t) iff exists k >= 0 : t in Reach_k(s).
Solvable iff exists s0 in S0, g in G : Reachable(s0,g).
ValidPath(p) iff every consecutive transition belongs to T.
Solution(p) iff ValidPath(p) and first(p) in S0 and last(p) in G.
PathCost(p) = sum_{e in p} cost(e), with cost(e) >= 0.
Optimal(p) iff Solution(p) and no solution q has PathCost(q) < PathCost(p).

05. CONSTRAINTS AND INVARIANTS
well_formed(space) requires S0 subset S, G subset S, T subset (S x A x S).
Invariant I is preserved iff forall (s,a,t) in T: I(s) implies I(t).
AdmissibleState(s) iff s in S and forall c in HardConstraints: c(s).
Prune(s) only if its exclusion cannot remove a required solution under the chosen search objective.
Duplicate detection must use a state identity/equivalence relation consistent with future behaviour and goal testing.

06. SEARCH OPERATIONS
INITIALISE: insert search nodes for all s0 in S0 into frontier.
EXPAND(n): enumerate applicable actions and successor states.
GOAL_TEST(n): return true iff n.state in G.
VISIT(n): record state or state-cost label as appropriate.
BACKTRACK(n): reconstruct path via parent links.
BFS: FIFO frontier; complete on finite-branching spaces with a finite-depth solution; optimal in number of edges for unit step costs.
DFS: LIFO frontier; not generally complete in infinite-depth spaces; not generally optimal.
UNIFORM_COST: expand minimum path-cost frontier node; optimal with suitable positive lower-bounded step costs and standard assumptions.
A_STAR: expand minimum f(n)=g(n)+h(n); graph-search optimality requires appropriate handling of reopened states, or a consistent heuristic with standard closed-set handling.

07. INFERENCE RULES
R1: T(s,a,t) => REACHABLE_FROM(t,s).
R2: REACHABLE_FROM(t,s) and T(t,a,u) => REACHABLE_FROM(u,s).
R3: s in S0 and s in G => empty path is a solution of cost 0.
R4: ValidPath(p) and last(p) in G and first(p) in S0 => Solution(p).
R5: I(s0) and I preserved by T => I(t) for all states t reachable from s0.
R6: Solution(p) and forall solutions q: cost(p)<=cost(q) => Optimal(p).
R7: admissible h means forall s: 0<=h(s)<=h*(s), where h*(s) is minimum remaining goal cost when defined.

08. WORKED EXAMPLE: TWO-BIT TOGGLE
S = {00, 01, 10, 11}; A = {toggle_left, toggle_right}.
T(00,toggle_left,10); T(00,toggle_right,01).
T(10,toggle_right,11); T(01,toggle_left,11).
Other transitions follow independent bit toggling.
S0={00}; G={11}; each action costs 1.
Path 00 --toggle_left--> 10 --toggle_right--> 11 is valid.
PathCost=2. No single toggle changes both bits, so 2 is optimal.
Reachable(00,11)=true.

09. COMPLEXITY AND REPRESENTATION
Explicit representation can require O(|S|+|T|) storage.
Implicit successor generation avoids materialising all states.
With branching factor b and depth d, tree search may generate O(b^d) nodes.
A search tree can contain multiple nodes representing the same state; a state graph merges equivalent configurations.
Cycles require visited-state management or another termination strategy.
Worst-case bounds depend on algorithm, transition costs, branching, depth and duplicate handling.

10. SEMANTIC EQUIVALENCE
State equivalence s~t may be defined by identical relevant variables, or behavioural equivalence preserving actions, goals and transition structure.
Never collapse states merely because their human-readable labels match.
STATE_SPACE != SEARCH_TREE.
STATE != SEARCH_NODE.
REACHABILITY != OPTIMALITY.
GOAL_TEST != HEURISTIC_ESTIMATE.

11. VALIDATION TESTS
V01: all initial and goal states belong to S.
V02: every transition has typed source, action and target.
V03: zero-length paths are accepted exactly when initial state is a goal.
V04: computed paths preserve transition adjacency.
V05: reported solution terminates in G.
V06: reported optimality has a justified algorithmic guarantee or certificate.
V07: state equivalence preserves required problem semantics.
V08: invariants hold across all applicable transitions.
V09: graph search handles cycles and improved-cost revisits correctly.
V10: heuristic admissibility claims are checked against defined cost semantics.

12. CONFIDENCE
Formal definitions: HIGH (standard graph/search mathematics).
Algorithm guarantees: CONDITIONAL on stated assumptions.
Page-specific alignment: UNVERIFIED (live source not consulted).

13. FLOW_HASH
Method: SHA-256 over canonical UTF-8 serialisation after normalising line endings, excluding the FLOW_HASH value itself.
Value: COMPUTE_ON_PUBLICATION.

14. UPDATE_MODEL
Version increment: patch for clarifications; minor for compatible additions; major for changed types or semantics.
On update: rerun validation tests, regenerate FLOW_HASH, record provenance and dependent ontology links.

15. AI_CONSUMPTION
mode: typed_semantic_reasoning
parsing: plain_text_utf8
ontology: State Space Ontology
parent: Discrete AI Mathematics
related: Search Tree Ontology; Graph Algorithms Ontology; Constraint Satisfaction Ontology; Algorithm Ontology
reasoning: reachability, planning, search, invariant checking, path validation, optimisation
provenance: Kireth Semantic Library URL above
limitations: symbolic model; empirical performance and source-page correspondence not asserted

END FLOW ALGEBRA