5
$\begingroup$

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can find a homomorphisms? And if not that, are there maybe a finite number of families of homomorphisms which divide all regular languages into classes?


My motivation for asking this question is from taking an undergrad course in group theory, and wanting to see if the treatment of polynomials by group theory can be applied to regular languages.

$\endgroup$
  • $\begingroup$ Do you allow deleting homomorphisms? $\endgroup$ – Raphael Feb 19 '16 at 12:45
  • $\begingroup$ Could you be a little clearer about the division into classes you are looking for? Existence of a homomorphism is not a symmetric property, are you thinking about the equivalence relation generated by it? $\endgroup$ – Klaus Draeger Feb 19 '16 at 12:46
  • $\begingroup$ @Raphael since I'm interested in the most general answer, then, sure, (and especially since I think this is going to help to find more homomorphisms) :) $\endgroup$ – wvxvw Feb 19 '16 at 12:48
  • $\begingroup$ @KlausDraeger I have to admit that I didn't consider the asymmetry. I'll need to think about it before I have a good answer. $\endgroup$ – wvxvw Feb 19 '16 at 12:49
  • 1
    $\begingroup$ Are you familiar with the more algebraic side of language theory? Eilenberg's Variety Theorem, for example? (See e.g. coalg.org/calco15/slides/4.pdf) $\endgroup$ – Klaus Draeger Feb 19 '16 at 15:36
5
$\begingroup$

Some examples, to get the discussion going:

  • For an infinite family of languages with no homomorphisms between them, consider the languages $L_k=\{a,a^k\}\subseteq\{a\}^*$ for $k\ge 2$. If $f:L_i\to L_j$ were a homomorphism for $i\neq j$, then $f(a)$ would be either $a$ or $a^j$, and $f(a^i)$ would be $a^i$ or $a^{ij}$, neither of which is in $L_j$.
  • On the other hand, it is easy to find infinite chains of languages with homomorphisms between them, just consider $L_i=\{a^k\ |\ 1\le k\le i\}\subseteq\{a\}^*$ and the inclusion $L_i\to L_j$ for $i<j$.
$\endgroup$
  • 2
    $\begingroup$ OK, I see now. Perhaps a better characteristic then would be, when comparing languages: "how much should be done to fix the language(s) in order for there to be a homomorphism between them?". So that the question would be more of a "how different two languages are?", something like Levenshtein distance. $\endgroup$ – wvxvw Feb 19 '16 at 14:17
  • 1
    $\begingroup$ That does sound like an interesting direction. Of course, getting the details right (so that they also make sense for infinite languages) is the tricky part. $\endgroup$ – Klaus Draeger Feb 19 '16 at 15:22
  • 1
    $\begingroup$ Whatever this turns out with, it is definitely a new question (or three). $\endgroup$ – vonbrand Feb 21 '16 at 17:40

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.