Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homomorphisms of Languages

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

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

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

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

    What do you think? Have you heard of this?
    Last edited: Jul 31, 2013
  2. jcsd
  3. Aug 1, 2013 #2
    If I'm not mistaken, this is related to the notion of a homomorphism as it appears in model theory.
  4. Aug 1, 2013 #3
    Yeah, it is just like that. Thanks!

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

    Stephen Tashi

    User Avatar
    Science Advisor

    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.)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook