1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook