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 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,\mathrm{\Sigma },\delta ,I,F)$ and a state-output 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 (state-output 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$.

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