# 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.

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 state-output 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 state-output 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 (state-output 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).
 Title subsemiautomaton Canonical name Subsemiautomaton Date of creation 2013-03-22 19:01:03 Last modified on 2013-03-22 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