Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

EDIT: The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.

  • $\begingroup$ Ever heard the phrase "forgetful functor" before? $\endgroup$ – Pseudonym Jun 20 '15 at 23:54

If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \{w\mid h(x) = w\}$ is only defined (nonempty) when $w\in\delta^*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse is a substitution, mapping the letter $\delta$ to the set $\Sigma$ and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one [meaning single valued], an inverse homomorphism in many cases is one-to-many [many-valued]. (If the inverse morphism is one-to-at-most-one [injective] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").

  • $\begingroup$ My mind must have been totally blown away, thank you. $\endgroup$ – Kyselejsyreček Jun 20 '15 at 12:52

The expression "closed under inverse homomorphism" is often used in formal languages: see for instance this question and this needs a clarification. As Hendrik Jan pointed out in his answer, a homomorphism is a map, but an "inverse homomorphism" is usually not.

To make the definition of "inverse" correct, one needs to view a homomorphism $h : A^* \to B^*$ as a relation on $A^* \times B^*$, whose graph is $$ \{(x, h(x)) \in A^* \times B^*\mid x \in A^*\} $$ Now, the inverse of $h$ as a relation is the relation $h^{-1}$ defined by its graph as follows $$ \{(h(x), x) \in B^* \times A^* \mid x \in A^*\} $$ and hence, for $y \in B^*$, $h^{-1}(y) = \{x \in A^* \mid h(x) = y \}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.