Homomorphisms of Languages

[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?

 

[economicsnerd]

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

 

[mXSCNT]

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

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?

 

[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.)

 

[CellCoree]

This is an interesting concept and definitely a useful generalization of homomorphisms. I have not specifically heard of this before, but it seems to have applications in various areas of mathematics and computer science. For example, in linguistics, this could potentially be used to study the relationships between different languages and their structures. In computer science, this could be useful for analyzing and comparing programming languages. Overall, this is a valuable tool for understanding and studying the relationships between different languages and their structures.