subsemiautomaton
Just like groups and rings, a semiautomaton can be viewed as an algebraic structure^{}. As such, one may define algebraic constructs such as subalgebras^{} and homomorphisms^{}. In this entry, we will briefly discuss the former.
Definition
A semiautomaton $N=(T,\mathrm{\Gamma},\gamma )$ is said to be a subsemiautomaton of a semiautomaton $M=(S,\mathrm{\Sigma},\delta )$ if
$$T\subseteq S,\mathrm{\Gamma}\subseteq \mathrm{\Sigma},\text{and}\mathit{\hspace{1em}\hspace{1em}}\gamma \subseteq \delta .$$ 
The last inclusion means the following: $\gamma (s,a)=\delta (s,a)$ for all $(s,a)\in T\times \mathrm{\Gamma}$. We write $N\le M$ when $N$ is a subsemiautomaton of $M$.
A subsemiautomaton $N$ of $M$ is said to be proper if $N\ne M$, and is written $$.
Examples. Let $M=(S,\mathrm{\Sigma},\delta )$ be a semiautomaton.

•
$M$ can be represented by its state diagram^{}, which is just a directed graph^{}. Any strongly connected component^{} of the state diagram represents a subsemiautomaton of $M$, characterized as a semiautomaton $({S}^{\prime},\mathrm{\Sigma},{\delta}^{\prime})$ such that any state in ${S}^{\prime}$ can be reached from any other state in ${S}^{\prime}$. In other words, for any $s,t\in {S}^{\prime}$, there is a word $u$ over $\mathrm{\Sigma}$ such that either $t\in {\delta}^{\prime}(s,u)$, where ${\delta}^{\prime}$ is the restriction^{} of $\delta $ to ${S}^{\prime}\times \mathrm{\Sigma}$. A semiautomaton whose state diagram is strongly connected is said to be strongly connected.

•
Suppose $M$ is strongly connected. Then $M$ has no proper subsemiautomaton whose input alphabet is equal to the input alphabet of $M$. In other words, if $N=(T,\mathrm{\Sigma},\gamma )\le M$, then $N=M$. However, proper subsemiautomata of $M$ exist if we take $N=(T,\mathrm{\Gamma},\gamma )$ for any proper subset^{} $\mathrm{\Gamma}$ of $\mathrm{\Sigma}$, provided that $\mathrm{\Sigma}\ge 2$. In this case, $\gamma $ is just the restriction of $\delta $ to the set $T\times \mathrm{\Gamma}$.

•
On the other hand, if $\mathrm{\Sigma}$ is a singleton, and $M$ is strongly connected, then no proper subsemiautomata of $M$ exist. Notice that if the transition function $\delta $ is single valued, then it is just a permutation^{} on $S$ of order $S$.
Specializations to Other Machines
Computing devices derived from semiautomata such as automata and stateoutput machines may too be considered as algebras^{}. We record the definitions of subalgebras of these objects here.
Note: the following notations are used: given an automaton $A=(S,\mathrm{\Sigma},\delta ,I,F)$ and a stateoutput machine $M=(S,\mathrm{\Sigma},\mathrm{\Delta},\delta ,\lambda )$, let ${A}^{\prime}$ and ${M}^{\prime}$ be the associated semiautomaton $(S,\mathrm{\Sigma},\delta )$. So $A$ and $M$ may be written $({A}^{\prime},I,F)$ and $({M}^{\prime},\mathrm{\Delta},\lambda )$ respectively.
Definition (automaton). $A=({A}^{\prime},I,F)$ is a subautomaton of $B=({B}^{\prime},J,G)$ if
$${A}^{\prime}\le {B}^{\prime},I\subseteq J,\text{and}\mathit{\hspace{1em}\hspace{1em}}F\subseteq G.$$ 
Definition (stateoutput machine). $M=({M}^{\prime},\mathrm{\Delta},\lambda )$ is a submachine of $N=({N}^{\prime},\mathrm{\Omega},\pi )$ if
$${M}^{\prime}\le {N}^{\prime},\mathrm{\Delta}\subseteq \mathrm{\Omega},\text{and}\mathit{\hspace{1em}}\lambda \text{is the restriction of}\pi \text{to}S\times \mathrm{\Sigma},$$ 
where $S$ and $\mathrm{\Sigma}$ are the state and input alphabets of $M$.
References
 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
Title  subsemiautomaton 
Canonical name  Subsemiautomaton 
Date of creation  20130322 19:01:03 
Last modified on  20130322 19:01:03 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 20M35 
Classification  msc 03D05 
Classification  msc 68Q45 
Classification  msc 68Q70 
Defines  strongly connected semiautomaton 
Defines  subsemiautomata 
Defines  subautomaton 
Defines  submachine 