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₁,…,a_k)) = f_B(h(a₁),…,h(a_k))

for all elements a₁,…,a_k of 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₁,…,s_n) = h(s₁),…,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.