Finite State Machine ontology

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: http://onto.vaimee.com/fsm#AcceptingState

A member of the set F of final or accepting states.

Sub-class of	`fsm:State`
In the range of	`fsm:hasAcceptingState`

Acceptor

IRI: http://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 of	`fsm:FiniteStateMachine`
In the domain of	`fsm:acceptsInput` `fsm:rejectsInput`

Alphabet

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

The finite non-empty set Sigma of input symbols for an FSM.

Super-class of	`fsm:OutputAlphabet`
In the domain of	`fsm:hasSymbol`
In the range of	`fsm:hasAlphabet`

Configuration

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

A runtime configuration of an FSM, commonly including the current state and unread input.

In the domain of fsm:hasCurrentState
fsm:hasInputString

Deterministic finite state machine

IRI: http://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 of fsm:FiniteStateMachine

Deterministic transition

IRI: http://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 of fsm:Transition

Finite state machine

IRI: http://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 of	`fsm:Acceptor` `fsm:DeterministicFiniteStateMachine` `fsm:NonDeterministicFiniteStateMachine` `fsm:Transducer`
In the domain of	`fsm:hasAcceptingState` `fsm:hasAlphabet` `fsm:hasInitialState` `fsm:hasState` `fsm:hasTransition` `fsm:hasTransitionFunction`

Initial state

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

The distinguished initial state s0 of an FSM.

Sub-class of	`fsm:State`
In the range of	`fsm:hasInitialState`

Input string

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

A finite sequence of input symbols consumed by an FSM.

In the domain of	`fsm:stringValue`
In the range of	`fsm:acceptsInput` `fsm:hasInputString` `fsm:rejectsInput`

Mealy machine

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

A transducer whose output depends on the current state and input symbol.

Sub-class of fsm:Transducer

Moore machine

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

A transducer whose output depends only on the current state.

Sub-class of fsm:Transducer

Nondeterministic finite state machine

IRI: http://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 of fsm:FiniteStateMachine

Output alphabet

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

The finite non-empty set Gamma of output symbols for a finite-state transducer.

Sub-class of	`fsm:Alphabet`
In the range of	`fsm:hasOutputAlphabet`

State

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

An element of the finite non-empty state set S of an FSM.

Super-class of	`fsm:AcceptingState` `fsm:InitialState`
In the domain of	`fsm:stateName` `fsm:stateOutputSymbol`
In the range of	`fsm:fromState` `fsm:hasCurrentState` `fsm:hasState` `fsm:toState`

Symbol

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

An element of an input or output alphabet.

In the domain of	`fsm:symbolValue`
In the range of	`fsm:emitsSymbol` `fsm:hasSymbol` `fsm:onSymbol` `fsm:stateOutputSymbol`

Transducer

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

An FSM that produces output symbols while processing input symbols.

Sub-class of	`fsm:FiniteStateMachine`
Super-class of	`fsm:MealyMachine` `fsm:MooreMachine`
In the domain of	`fsm:hasOutputAlphabet`

Transition

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

A concrete transition relation entry representing delta(source state, input symbol) = target state.

Super-class of	`fsm:DeterministicTransition`
In the domain of	`fsm:emitsSymbol` `fsm:fromState` `fsm:onSymbol` `fsm:toState`
In the range of	`fsm:hasTransition`

Transition function

IRI: http://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 of fsm:hasTransitionFunction

Object Properties

accepts input

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

Relates an acceptor to an input string that it accepts.

Domain includes	`fsm:Acceptor`
Range includes	`fsm:InputString`

emits symbol

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

The output symbol emitted by a transition, typically for Mealy machines.

Domain includes	`fsm:Transition`
Range includes	`fsm:Symbol`

from state

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

The source state of a transition.

Domain includes	`fsm:Transition`
Range includes	`fsm:State`

has accepting state

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

Relates an FSM to a member of its final/accepting state set F.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:AcceptingState`

has alphabet

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

Relates an FSM to its input alphabet Sigma.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:Alphabet`

has current state

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

Relates a runtime configuration to the current state of the FSM.

Domain includes	`fsm:Configuration`
Range includes	`fsm:State`

has initial state

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

Relates an FSM to its unique initial state s0.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:InitialState`

has input string

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

Relates a runtime configuration to an input string.

Domain includes	`fsm:Configuration`
Range includes	`fsm:InputString`

has output alphabet

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

Relates a transducer to its output alphabet Gamma.

Domain includes	`fsm:Transducer`
Range includes	`fsm:OutputAlphabet`

has state

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

Relates an FSM to a member of its state set S.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:State`

has symbol

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

Relates an alphabet to one of its symbols.

Domain includes	`fsm:Alphabet`
Range includes	`fsm:Symbol`

has transition

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

Relates an FSM to a concrete transition in its transition relation/function.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:Transition`

has transition function

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

Relates an FSM to its transition function delta.

Domain includes	`fsm:FiniteStateMachine`
Range includes	`fsm:TransitionFunction`

on symbol

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

The input symbol that triggers a transition.

Domain includes	`fsm:Transition`
Range includes	`fsm:Symbol`

rejects input

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

Relates an acceptor to an input string that it rejects.

Domain includes	`fsm:Acceptor`
Range includes	`fsm:InputString`

state output symbol

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

The output symbol associated with a state, typically for Moore machines.

Domain includes	`fsm:State`
Range includes	`fsm:Symbol`

to state

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

The target state reached by a transition.

Domain includes	`fsm:Transition`
Range includes	`fsm:State`

Datatype Properties

state name

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

Human-readable state name.

Domain includes	`fsm:State`
Range includes	`xsd:string`

string value

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

A compact lexical representation of an input string.

Domain includes	`fsm:InputString`
Range includes	`xsd:string`

symbol value

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

Lexical value used to identify a symbol.

Domain includes	`fsm:Symbol`
Range includes	`xsd:string`

`fsm:`	`http://onto.vaimee.com/fsm#`
`xsd:`	`http://www.w3.org/2001/XMLSchema#`

Version	`1.0.25`
Version IRI	`http://onto.vaimee.com/fsm/1.0.25`

Introduction

Namespaces

Version