## homomorphism

## homomorphism

**homomorphism** A structure-preserving mapping between algebras. A homomorphism allows the modeling, simulation, or representation of the structure of one algebra within another, possibly in a limited form. Let *A* and *B* be algebras and *h* a function from *A* to *B*. Suppose that *A* contains an *n*-ary operation *f*_{A}, while *B* contains a corresponding operation *f*_{B}. If *h* is a homomorphism it must satisfy *h*(*f*_{A}(*a*_{1},…,*a _{k}*)) =

*f*

_{B}(

*h*(

*a*

_{1}),…,

*h*(

*a*))

_{k}for all elements

*a*

_{1},…,

*a*of

_{k}*A*and every “corresponding” pair of operations of

*A*and

*B*.

The idea that

*f*

_{A}and

*f*

_{B}are “corresponding” operations is made precise by saying that

*A*and

*B*are algebras over the same signature Σ, while

*f*is an operation symbol in Σ with which

*A*and

*B*associate the operations

*f*

_{A}and

*f*

_{B}respectively. A homomorphism from

*A*to

*B*is any function

*h*from

*A*to

*B*that satisfies the condition given above for each

*f*in Σ. As applications of this idea, the semantic functions involved in denotational semantics can be viewed as homomorphisms from algebras of syntax to algebras of semantic objects. Usually, to define a semantic function by induction on terms is to define a homomorphism on a term algebra. In several important cases, compilers can be designed as homomorphisms between two algebras of programs.

Special cases of this general definition occur when

*A*and

*B*belong to one of the familiar classes of algebraic structures. For example, let

*A*and

*B*be monoids, with binary operations ◦

_{A}and ◦

_{B}and identity elements

*e*

_{A}and

*e*

_{B}. Then, rewriting the general condition above, a homomorphism from

*A*to

*B*satisfies

*h*(

*x*◦

_{A}

*y*) =

*h*(

*x*) ◦

_{B}

*h*(

*y*)

*h*(

*e*

_{A}) =

*e*

_{B}

A further specialization from formal language theory arises with monoids of words, where the binary operation is concatenation and the nullary operation is the empty word. Let

*S*and

*T*be alphabets, and let

*h*be a function from

*S*to

*T**, i.e. a function that gives a

*T*-word for each symbol in

*S*. Then

*h*can be extended to

*S*-words, by concatenating its values on individual symbols:

*h*(

*s*

_{1},…,

*s*) =

_{n}*h*(

*s*

_{1}),…,

*h*(

*s*)

_{n}This extension of

*h*gives a monoid homomorphism from

*S** to

*T**. Such an

*h*is said to be Λ-

*free*if it gives a nonempty

*T*-word for each symbol in

*S*.

*h*can be further extended to a mapping on languages, giving, for any subset

*L*of

*S**, its

*homomorphic image h*(

*L*):

*h*(

*L*) = {

*h*(

*w*) |

*w ∈ L*}

Similarly the

*inverse homomorphic image*of

*L*⊆

*T** is

*h*

^{–1}(

*L*) = {

*w*|

*h*(

*w*) ∈

*L*}

These language-mappings are also homomorphisms, between the monoids of languages over

*S*and over

*T*, the binary operation being concatenation of languages.