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,\mathrm{\Sigma},\delta )$ to a semiautomaton $N=(T,\mathrm{\Gamma},\gamma )$ is a pair of maps $h:=(f:S\to T,g:\mathrm{\Sigma}\to \mathrm{\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(\mathrm{\Sigma}),{\gamma}^{\prime})$ of $N$, where ${\gamma}^{\prime}$ is the restriction^{} of $\gamma $ to $f(S)\times g(\mathrm{\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 $\mathrm{\Sigma},\mathrm{\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 $\mathrm{\Delta}:=\mathrm{\Sigma}\cup \mathrm{\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}:\mathrm{\Delta}\to \mathrm{\Delta}$ given by ${g}^{\prime}(a)=g(a)$ if $a\in \mathrm{\Sigma}$, and ${g}^{\prime}(a)=a$ if $a\in \mathrm{\Gamma}\mathrm{\Sigma}$. Routine verification shows that ${h}^{\prime}$ is indeed a homomorphism: if $a\in \mathrm{\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 \mathrm{\Gamma}\mathrm{\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,\mathrm{\Sigma},\delta )$ and $(T,\mathrm{\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 stateoutput 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,\mathrm{\Sigma},\delta ,I,F)$ and a stateoutput 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). 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 (stateoutput machine). Given stateoutput machines $M=({M}^{\prime},\mathrm{\Delta},\lambda )$ and $N=({N}^{\prime},\mathrm{\Omega},\pi )$. Then
$$\varphi =(h,k):M\to N$$ 
is a homomorphism if

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

•
$k:\mathrm{\Delta}\to \mathrm{\Omega}$, such that
$$k(\lambda (s,a))=\pi (f(s),g(a)),$$ for all $(s,a)\in S\times \mathrm{\Sigma}$, where $S$ and $\mathrm{\Sigma}$ are the state and input alphabets of $M$.
A homomorphism $\varphi :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  20130322 19:01:07 
Last modified on  20130322 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 