homomorphism

Updated About encyclopedia.com content Print Article Share Article
views updated

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 fA, while B contains a corresponding operation fB. If h is a homomorphism it must satisfy h(fA(a1,…,ak)) = fB(h(a1),…,h(ak))

for all elements a1,…,ak of A and every “corresponding” pair of operations of A and B.

The idea that fA and fB 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 fA and fB 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 operationsA and ◦B and identity elements eA and eB. Then, rewriting the general condition above, a homomorphism from A to B satisfies h(xA y) = h(x) ◦B h(y) h(eA) = eB

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(s1,…,sn) = h(s1),…,h(sn)

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.