# Homomorphisms of Languages

1. Jul 31, 2013

### mXSCNT

Hey, I was thinking of this generalization of homomorphisms. You have a language $L_1 = (A, B)$ where $A$ is a set of symbols and $B$ is a set of sequences of symbols in $A$. Given languages $L_1 = (A, B)$ and $L_2 = (C, D)$ a function $f: A \rightarrow C$ is defined to be a homomorphism of languages if, given any sequence $a_1 a_2 ... a_n \in B$, we have $f(a_1) f(a_2) ... f(a_n) \in D$.

This is seen as a generalization. For example, if $A$ is a set of group elements, and $B$ is a set of sentences of the form "$a_1 a_2 a_3$" (the multiplication table, $a_1 * a_2 = a_3$), then every homomorphism of languages from $A$ to the alphabet of another language set up like this corresponds to a group homomorphism.

Another example: if $A$ is a set of ring elements together with special elements * + =, and $B$ is a set of sentences of the form "$a_1 * a_2 = a_3$" (the multiplication table), unioned with a set of sentences of the form "$a_1 + a_2 = a_3$" (the addition table), then homomorphisms of languages that map * to * and + to + and = to = correspond to ring homomorphisms.

To look at it in general, $A$ is a set of objects, and $B$ is a set of true statements about elements of $A$. A homomorphism of languages $f : A \rightarrow C$ induces a map from statements in $B$ to corresponding statements in $D$ that "maps truth to truth" (doesn't generate false statements, i.e. strings outside of $D$).

What do you think? Have you heard of this?

Last edited: Jul 31, 2013
2. Aug 1, 2013

### economicsnerd

If I'm not mistaken, this is related to the notion of a homomorphism as it appears in model theory.

3. Aug 1, 2013

### mXSCNT

Yeah, it is just like that. Thanks!

Another note. $f : A \rightarrow C$ induces a map $h : B \rightarrow D$. Specifically, $h$ takes in a string in $B$ and maps each character in the string to another single character, such that the result is always in $D$. I wonder if we can generalize further, to other kinds of functions $h$. For instance, maybe there is something interesting if we consider functions $h : B \rightarrow D$ where the mapping of $h$ is given by an arbitrary finite state transducer (with outputs always in $D$). What parts of the structure of $B$ would such a mapping preserve?

4. Aug 2, 2013

### Stephen Tashi

I think of the idea of "homomorphism" as implicitly involving the ideas of "kernel" and "quotient". If we have a mapping between "things" that "preserves" operations but the things don't necessarily have an implementation of an "identity" thing, is there a name for such a mapping other than "homomorphism"? (I suppose one could resort to the "functor" of category theory.)