# semiautomaton homomorphism

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