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.

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