# subsemiautomaton

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

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