# semiautomaton homomorphism

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

## Definition

A homomorphism from a semiautomaton $M=(S,\Sigma,\delta)$ to a semiautomaton $N=(T,\Gamma,\gamma)$ is a pair of maps $h:=(f:S\to T,g:\Sigma\to\Gamma)$ such that

 $f(\delta(s,a))=\gamma(f(s),g(a))$

The image of the homomorphism $h$ is the subsemiautomaton $h(M):=(f(S),g(\Sigma),\gamma^{\prime})$ of $N$, where $\gamma^{\prime}$ is the restriction of $\gamma$ to $f(S)\times g(\Sigma)$, also known as the homomorphic image of $M$ under $h$.

In general, a semiautomaton $N$ is said to be a homomorphic image of a semiautomaton $M$, if there is a homomorphism $h$ such that $h(M)=N$.

When comparing two semiautomata $M,N$, it is customary to identify the two corresponding input alphabets $\Sigma,\Gamma$, especially when one wants to study the interaction between the states of $M$ and the states of $N$. This can be done by taking $\Delta:=\Sigma\cup\Gamma$, and extend the corresponding transition functions so that they are identities on the extended portions of the input alphabets. Call the extended semiautomata $M^{\prime},N^{\prime}$.

If $h:M\to N$ is a homomorphism, then $h^{\prime}:M^{\prime}\to N^{\prime}$ extends $h$ in a natural way: $f^{\prime}=f$, and $g^{\prime}:\Delta\to\Delta$ given by $g^{\prime}(a)=g(a)$ if $a\in\Sigma$, and $g^{\prime}(a)=a$ if $a\in\Gamma-\Sigma$. Routine verification shows that $h^{\prime}$ is indeed a homomorphism: if $a\in\Sigma$,

 $f^{\prime}(\delta^{\prime}(s,a))=f(\delta^{\prime}(s,a))=f(\delta(s,a))=\gamma% (f(s),g(a))=\gamma^{\prime}(f(s),g(a))=\gamma^{\prime}(f^{\prime}(s),g^{\prime% }(a)),$

and if $a\in\Gamma-\Sigma$, then

 $f^{\prime}(\delta^{\prime}(s,a))=f(\delta^{\prime}(s,a))=f(s)=\gamma^{\prime}(% f(s),a)=\gamma^{\prime}(f^{\prime}(s),a)=\gamma^{\prime}(f^{\prime}(s),g^{% \prime}(a)).$

A homomorphism $h=(f,g):M\to N$ is an isomorphism if both $f$ and $g$ are bijections. As discussed above, if we identify the input alphabets of $M$ and $N$, and treat $g$ as the identity map on the input alphabet, then $(S,\Sigma,\delta)$ and $(T,\Sigma,\gamma)$ are isomorphic if there is a bijection $f:S\to T$ such that $f(\delta(s,a))=\gamma(f(s),a)$.

## Specializations to Other Machines

Computing devices derived from semiautomata such as automata and state-output machines may also be considered as algebras. We record the definitions of homomorphisms with respect to these objects here.

We adopt the following notations: 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). Given automata $A=(A^{\prime},I,F)$ and $B=(B^{\prime},J,G)$. Then

 $h=(f,g):A\to B$

is a homomorphism if

• $h:A^{\prime}\to B^{\prime}$ is a semiautomaton homomorphism, such that

• $f(I)\subseteq J$, and $f(F)\subseteq G$.

A homomorphism $h:A\to B$ is an isomorphism if $h:A^{\prime}\to B^{\prime}$ is an isomorphism such that $f(I)=J$ and $f(F)=G$.

Definition (state-output machine). Given state-output machines $M=(M^{\prime},\Delta,\lambda)$ and $N=(N^{\prime},\Omega,\pi)$. Then

 $\phi=(h,k):M\to N$

is a homomorphism if

• $h:M^{\prime}\to N^{\prime}$ is a semiautomaton homomorphism, and

• $k:\Delta\to\Omega$, such that

 $k(\lambda(s,a))=\pi(f(s),g(a)),$

for all $(s,a)\in S\times\Sigma$, where $S$ and $\Sigma$ are the state and input alphabets of $M$.

A homomorphism $\phi:A\to B$ is an isomorphism if $h:M^{\prime}\to N^{\prime}$ is an isomorphism and $k$ is a bijection.

## References

• 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
 Title semiautomaton homomorphism Canonical name SemiautomatonHomomorphism Date of creation 2013-03-22 19:01:07 Last modified on 2013-03-22 19:01:07 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 7 Author CWoo (3771) Entry type Definition Classification msc 68Q45 Classification msc 20M35 Classification msc 03D05 Classification msc 68Q70 Defines homomorphism Defines homomorphic image Defines isomorphism Defines automaton homomorphism Defines machine homomorphism