State Machine Ontology

FLOW ALGEBRA
STATE MACHINE ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Automata Theory
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/automata-theory/state-machine-ontology.html
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)
Status: Mathematical synthesis; source page content not independently verified.

1. ONTOLOGY IDENTITY
ontology_id: kireth:discrete-mathematics:automata-theory:state-machine
label: State Machine Ontology
parent: Automata Theory Ontology
scope: Formal state-transition systems, deterministic/nondeterministic and labelled state machines, execution traces, reachability, and behavioural verification.

2. TYPED ENTITIES
StateMachine := (S, I, T, S0, L)
S: Set[State]                   # state space, nonempty
I: Set[Input]                   # input alphabet, possibly empty
T: Relation[S x I x S]          # labelled transition relation
S0: Set[State]                  # initial states, nonempty subset of S
L: Function[S -> Set[AtomicProposition]]  # optional state labelling
State := Identifier | StructuredConfiguration
Input := Symbol | Event
Transition := (source:State, input:Input, target:State)
Trace := Sequence[State]
Run := Sequence[State x Input x State]
ReachableSet := Set[State]
Invariant := Predicate[State]

3. CORE RELATIONSHIPS
HAS_STATE(StateMachine, State)
HAS_INITIAL_STATE(StateMachine, State)
HAS_TRANSITION(StateMachine, Transition)
TRANSITIONS_TO(State, State)
TRIGGERED_BY(Transition, Input)
REACHABLE_FROM(State, State)
SATISFIES(State, Invariant)
REFINES(StateMachine, StateMachine)
EQUIVALENT_BEHAVIOUR(StateMachine, StateMachine)

4. FORMAL OPERATIONS
step(M,s,a) := {t in S | (s,a,t) in T}
post(M,X) := {t in S | exists s in X, a in I: (s,a,t) in T}
pre(M,X) := {s in S | exists t in X, a in I: (s,a,t) in T}
reach_0(M) := S0
reach_(n+1)(M) := reach_n(M) union post(M,reach_n(M))
Reach(M) := union_{n>=0} reach_n(M)
Enabled(M,s) := {a in I | step(M,s,a) != empty}
Deadlock(M,s) := Enabled(M,s) = empty
Deterministic(M) := forall s in S,a in I: |step(M,s,a)| <= 1
InputComplete(M) := forall s in S,a in I: |step(M,s,a)| >= 1

5. SEMANTIC LAWS AND INVARIANTS
L1: S0 subseteq S
L2: T subseteq S x I x S
L3: S0 subseteq Reach(M)
L4: post(M,empty) = empty
L5: X subseteq Y implies post(M,X) subseteq post(M,Y)
L6: Reach(M) = S0 union post(M,Reach(M))
L7: Every finite run starts in S0 and each adjacent step belongs to T.
L8: An invariant P holds globally on reachable states iff forall s in Reach(M): P(s).
L9: Inductive invariant sufficient condition: forall s in S0:P(s), and forall (s,a,t) in T: P(s) implies P(t).
L10: Determinism alone does not imply input completeness or termination.
L11: Reachability does not imply inevitability; possible and necessary future behaviours differ.

6. INFERENCE RULES
R1 [INITIAL_REACHABILITY]: s in S0 => reachable(s).
R2 [TRANSITION_REACHABILITY]: reachable(s) and (s,a,t) in T => reachable(t).
R3 [INDUCTIVE_SAFETY]: P holds on S0 and is transition-preserved => P holds on Reach(M).
R4 [DEADLOCK]: reachable(s) and Enabled(M,s)=empty => reachable_deadlock(s).
R5 [NONDETERMINISM]: exists s,a with two distinct successors => not Deterministic(M).
R6 [TRACE_VALIDITY]: initial state plus valid consecutive transitions => valid finite run.
R7 [COUNTEREXAMPLE]: reachable(s) and not P(s) => global invariant P is false.

7. MODEL VARIANTS
DFA: finite S, deterministic total transition function, designated accepting states.
NFA: finite S, potentially multiple transitions for an input; epsilon transitions require a separate epsilon-labelled extension.
Moore machine: outputs depend on current state.
Mealy machine: outputs depend on state and input/transition.
Kripke structure: transition system labelled by atomic propositions, often with a total successor relation.
Finite-state controller: transitions encode events, guards, and actions with explicitly defined semantics.
Timed or probabilistic machines: extensions requiring clock constraints or probability kernels, not assumed by base model.

8. VALIDATION
V1: Verify state and transition type consistency.
V2: Verify S0 is nonempty and within S.
V3: Verify all transition endpoints are in S and labels in I.
V4: For claimed deterministic models, check successor uniqueness per (s,a).
V5: For claimed complete models, check successor existence per (s,a).
V6: For finite models, compute Reach(M) by fixed-point iteration.
V7: Check safety invariants only on reachable states, or prove inductively.
V8: Report unreachable states, reachable deadlocks, and invalid traces separately.
V9: Distinguish trace equivalence, bisimulation, and structural isomorphism.
V10: For infinite-state systems, do not claim exhaustive reachability without a sound method.

9. SEMANTIC_EQUIVALENCE
aliases: [finite state machine, transition system, state-transition model]
qualification: These are context-dependent near-equivalents; a finite state machine is specifically finite-state, while transition systems may be infinite-state.
not_equivalent: [state, transition, event, Markov chain]
semantic_mapping: state_machine -> transition_system; transition -> labelled_relation; execution -> run; safety -> invariant

10. CONFIDENCE
mathematical_definitions: 0.99
formal_laws: 0.99
source_page_alignment: unverified
confidence_policy: Scores describe confidence in standard mathematical statements, not proof of live-page agreement.

11. FLOW_HASH
hash_algorithm: SHA-256
hash_scope: Canonical UTF-8 serialisation of ontology_id, version, typed entities, operations, laws, and inference rules.
flow_hash: COMPUTE_ON_INGEST
note: Placeholder is deliberate; no digest is claimed without computing the specified canonical serialisation.

12. UPDATE_MODEL
versioning: semantic-versioning
on_change: revalidate types, recompute reachability where finite, rerun invariant checks, update semantic mappings, recompute FLOW_HASH
provenance: retain source URL, change timestamp, author credit and verification status
breaking_changes: changes to state/transition semantics, initial-state interpretation, or accepted trace definition

13. AI_CONSUMPTION
input: StateMachine specification + query + optional constraints
pipeline: PARSE -> TYPE_CHECK -> NORMALISE -> BUILD_TRANSITIONS -> ANALYSE_REACHABILITY -> VERIFY_PROPERTIES -> EXPLAIN
output: typed result, proof or counterexample trace, confidence annotation, provenance, version and hash
safety: Never infer liveness from safety, deterministic behaviour from a single example, or exhaustive verification from incomplete exploration.

14. WORKED EXAMPLE
S={idle,running,done}; I={start,finish}; S0={idle}
T={(idle,start,running),(running,finish,done)}
Reach(M)={idle,running,done}
Deterministic(M)=true; InputComplete(M)=false
Deadlock(M,done)=true
P(s): s in {idle,running,done} is an invariant (trivial state membership).
Trace idle --start--> running --finish--> done is valid.

END FLOW ALGEBRA