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 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,\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). 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 },\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.