You are here
Homesubsemiautomaton
Primary tabs
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,\Gamma,\gamma)$ is said to be a subsemiautomaton of a semiautomaton $M=(S,\Sigma,\delta)$ if
$T\subseteq S,\qquad\Gamma\subseteq\Sigma,\qquad\mbox{and}\qquad\gamma\subseteq\delta.$ 
The last inclusion means the following: $\gamma(s,a)=\delta(s,a)$ for all $(s,a)\in T\times\Gamma$. We write $N\leq M$ when $N$ is a subsemiautomaton of $M$.
A subsemiautomaton $N$ of $M$ is said to be proper if $N\neq M$, and is written $N<M$.
Examples. Let $M=(S,\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}},\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 $\Sigma$ such that either $t\in\delta^{{\prime}}(s,u)$, where $\delta^{{\prime}}$ is the restriction of $\delta$ to $S^{{\prime}}\times\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,\Sigma,\gamma)\leq M$, then $N=M$. However, proper subsemiautomata of $M$ exist if we take $N=(T,\Gamma,\gamma)$ for any proper subset $\Gamma$ of $\Sigma$, provided that $\Sigma\geq 2$. In this case, $\gamma$ is just the restriction of $\delta$ to the set $T\times\Gamma$.

On the other hand, if $\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,\Sigma,\delta,I,F)$ and a stateoutput machine $M=(S,\Sigma,\Delta,\delta,\lambda)$, let $A^{{\prime}}$ and $M^{{\prime}}$ be the associated semiautomaton $(S,\Sigma,\delta)$. So $A$ and $M$ may be written $(A^{{\prime}},I,F)$ and $(M^{{\prime}},\Delta,\lambda)$ respectively.
Definition (automaton). $A=(A^{{\prime}},I,F)$ is a subautomaton of $B=(B^{{\prime}},J,G)$ if
$A^{{\prime}}\leq B^{{\prime}},\qquad I\subseteq J,\qquad\mbox{and}\qquad F% \subseteq G.$ 
Definition (stateoutput machine). $M=(M^{{\prime}},\Delta,\lambda)$ is a submachine of $N=(N^{{\prime}},\Omega,\pi)$ if
$M^{{\prime}}\leq N^{{\prime}},\qquad\Delta\subseteq\Omega,\qquad\mbox{and }% \quad\lambda\mbox{ is the restriction of }\pi\mbox{ to }S\times\Sigma,$ 
where $S$ and $\Sigma$ are the state and input alphabets of $M$.
References
 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
Mathematics Subject Classification
20M35 no label found03D05 no label found68Q45 no label found68Q70 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections