Ontology for representing finite-state machines using the standard mathematical model M = (Sigma, S, s0, delta, F), where Sigma is the input alphabet, S is the finite set of states, s0 is the initial state, delta is the transition function, and F is the set of final/accepting states.

This document is a work in progress

Introduction

"Ontology for representing finite-state machines using the standard mathematical model M = (Sigma, S, s0, delta, F), where Sigma is the input alphabet, S is the finite set of states, s0 is the initial state, delta is the transition function, and F is the set of final/accepting states."

Axiomatization

Classes

Accepting state

IRI: https://onto.vaimee.com/fsm#AcceptingState

A member of the set F of final or accepting states.
Sub-class ofState
In the range ofhas accepting state

Acceptor

IRI: https://onto.vaimee.com/fsm#Acceptor

An FSM that accepts or rejects an input sequence depending on whether computation ends in an accepting state.
Sub-class ofFinite state machine
In the domain ofaccepts input
rejects input

Alphabet

IRI: https://onto.vaimee.com/fsm#Alphabet

The finite non-empty set Sigma of input symbols for an FSM.
Super-class ofOutput alphabet
In the domain ofhas symbol
In the range ofhas alphabet

Configuration

IRI: https://onto.vaimee.com/fsm#Configuration

A runtime configuration of an FSM, commonly including the current state and unread input.
In the domain ofhas current state
has input string

Deterministic finite state machine

IRI: https://onto.vaimee.com/fsm#DeterministicFiniteStateMachine

An FSM where each state and input symbol pair has at most one next state. This ontology records that intention, but full per-machine transition uniqueness is usually enforced with SHACL or application logic.
Sub-class ofFinite state machine

Deterministic transition

IRI: https://onto.vaimee.com/fsm#DeterministicTransition

A transition entry intended for deterministic automata. For strict DFA validation, use SHACL to enforce at most one target state for each machine, source state, and input symbol.
Sub-class ofTransition

Finite state machine

IRI: https://onto.vaimee.com/fsm#FiniteStateMachine

A mathematical model of computation that can be in exactly one state at a time and changes state through transitions triggered by input symbols.
Super-class ofAcceptor
Deterministic finite state machine
Nondeterministic finite state machine
Transducer
In the domain ofhas accepting state
has alphabet
has initial state
has state
has transition
has transition function

Initial state

IRI: https://onto.vaimee.com/fsm#InitialState

The distinguished initial state s0 of an FSM.
Sub-class ofState
In the range ofhas initial state

Input string

IRI: https://onto.vaimee.com/fsm#InputString

A finite sequence of input symbols consumed by an FSM.
In the domain ofstring value
In the range ofaccepts input
has input string
rejects input

Mealy machine

IRI: https://onto.vaimee.com/fsm#MealyMachine

A transducer whose output depends on the current state and input symbol.
Sub-class ofTransducer

Moore machine

IRI: https://onto.vaimee.com/fsm#MooreMachine

A transducer whose output depends only on the current state.
Sub-class ofTransducer

Nondeterministic finite state machine

IRI: https://onto.vaimee.com/fsm#NonDeterministicFiniteStateMachine

An FSM where a state and input symbol pair may lead to zero, one, or multiple next states.
Sub-class ofFinite state machine

Output alphabet

IRI: https://onto.vaimee.com/fsm#OutputAlphabet

The finite non-empty set Gamma of output symbols for a finite-state transducer.
Sub-class ofAlphabet
In the range ofhas output alphabet

State

IRI: https://onto.vaimee.com/fsm#State

An element of the finite non-empty state set S of an FSM.
Super-class ofAccepting state
Initial state
In the domain ofstate name
state output symbol
In the range offrom state
has current state
has state
to state

Symbol

IRI: https://onto.vaimee.com/fsm#Symbol

An element of an input or output alphabet.
In the domain ofsymbol value
In the range ofemits symbol
has symbol
on symbol
state output symbol

Transducer

IRI: https://onto.vaimee.com/fsm#Transducer

An FSM that produces output symbols while processing input symbols.
Sub-class ofFinite state machine
Super-class ofMealy machine
Moore machine
In the domain ofhas output alphabet

Transition

IRI: https://onto.vaimee.com/fsm#Transition

A concrete transition relation entry representing delta(source state, input symbol) = target state.
Super-class ofDeterministic transition
In the domain ofemits symbol
from state
on symbol
to state
In the range ofhas transition

Transition function

IRI: https://onto.vaimee.com/fsm#TransitionFunction

The function delta that maps a state and input symbol pair to a next state, or to a set of next states for nondeterministic FSMs.
In the range ofhas transition function

Object Properties

accepts input

IRI: https://onto.vaimee.com/fsm#acceptsInput

Relates an acceptor to an input string that it accepts.
Domain includesAcceptor
Range includesInput string

emits symbol

IRI: https://onto.vaimee.com/fsm#emitsSymbol

The output symbol emitted by a transition, typically for Mealy machines.
Domain includesTransition
Range includesSymbol

from state

IRI: https://onto.vaimee.com/fsm#fromState

The source state of a transition.
Domain includesTransition
Range includesState

has accepting state

IRI: https://onto.vaimee.com/fsm#hasAcceptingState

Relates an FSM to a member of its final/accepting state set F.
Domain includesFinite state machine
Range includesAccepting state

has alphabet

IRI: https://onto.vaimee.com/fsm#hasAlphabet

Relates an FSM to its input alphabet Sigma.
Domain includesFinite state machine
Range includesAlphabet

has current state

IRI: https://onto.vaimee.com/fsm#hasCurrentState

Relates a runtime configuration to the current state of the FSM.
Domain includesConfiguration
Range includesState

has initial state

IRI: https://onto.vaimee.com/fsm#hasInitialState

Relates an FSM to its unique initial state s0.
Domain includesFinite state machine
Range includesInitial state

has input string

IRI: https://onto.vaimee.com/fsm#hasInputString

Relates a runtime configuration to an input string.
Domain includesConfiguration
Range includesInput string

has output alphabet

IRI: https://onto.vaimee.com/fsm#hasOutputAlphabet

Relates a transducer to its output alphabet Gamma.
Domain includesTransducer
Range includesOutput alphabet

has state

IRI: https://onto.vaimee.com/fsm#hasState

Relates an FSM to a member of its state set S.
Domain includesFinite state machine
Range includesState

has symbol

IRI: https://onto.vaimee.com/fsm#hasSymbol

Relates an alphabet to one of its symbols.
Domain includesAlphabet
Range includesSymbol

has transition

IRI: https://onto.vaimee.com/fsm#hasTransition

Relates an FSM to a concrete transition in its transition relation/function.
Domain includesFinite state machine
Range includesTransition

has transition function

IRI: https://onto.vaimee.com/fsm#hasTransitionFunction

Relates an FSM to its transition function delta.
Domain includesFinite state machine
Range includesTransition function

on symbol

IRI: https://onto.vaimee.com/fsm#onSymbol

The input symbol that triggers a transition.
Domain includesTransition
Range includesSymbol

rejects input

IRI: https://onto.vaimee.com/fsm#rejectsInput

Relates an acceptor to an input string that it rejects.
Domain includesAcceptor
Range includesInput string

state output symbol

IRI: https://onto.vaimee.com/fsm#stateOutputSymbol

The output symbol associated with a state, typically for Moore machines.
Domain includesState
Range includesSymbol

to state

IRI: https://onto.vaimee.com/fsm#toState

The target state reached by a transition.
Domain includesTransition
Range includesState

Datatype Properties

state name

IRI: https://onto.vaimee.com/fsm#stateName

Human-readable state name.
Domain includesState
Range includeshttp://www.w3.org/2001/XMLSchema#string

string value

IRI: https://onto.vaimee.com/fsm#stringValue

A compact lexical representation of an input string.
Domain includesInput string
Range includeshttp://www.w3.org/2001/XMLSchema#string

symbol value

IRI: https://onto.vaimee.com/fsm#symbolValue

Lexical value used to identify a symbol.
Domain includesSymbol
Range includeshttp://www.w3.org/2001/XMLSchema#string