While studying a bit of Joachim Lambek's calculus and some other applications of formal languages to the study of the structure of human language, I have come accross a reference to what authors like André Lentin has developed for the study of word combinations, namely, the so-called equations on the free monoid.

Could anyone explain me what those equations on the free monoid are?

Best regards and thanks in advance.

  • $\begingroup$ Formally just a pair of elements, and is said to hold via an interpretation in a monoid if both elements mapped to the same. $\endgroup$ – Berci Jun 13 '18 at 22:00
  • $\begingroup$ Could you please be more specific? Isnt the term "equations" taken there in its proper sense?? I thought there would be some underlying equations or anything of that sort..... $\endgroup$ – Javier Arias Jun 13 '18 at 22:07

You can find the definition and a presentation of the main results in the Wikipedia entry Équation entre mots which apparently has not been translated in any other language.

Let $A$ be a finite set of constants and let $\Xi$ be a finite set of variables. A word equation is a pair $(u, v)$ of words of $(A \cup \Xi)^*$. A solution is a map $f:\Xi \to A^*$, which extends uniquely to a monoid homomorphism from $(A \cup \Xi)^*$ to $A^*$, such that $f(u) = f(v)$.

Quoting Wikipedia, the map $f(T) = bab$, $f(X) = abb$, $f(Y) = ab$, $f(Z) = ba$ is a solution of the equation $$ XaTZaT=YZbXaabY $$ since $(abb)a(bab)(ba)a(bab) = (ab)(ba)b(abb)aab(ab)$.

Makanin's theorem states that deciding whether a given equation has a solution is decidable.

  • $\begingroup$ Well, I guess the next question is. What advantages does the usage of such conceptual machinery and formalism bring? I mean, in which way does the study of grammar and / or formal language benefit from that? $\endgroup$ – Javier Arias Jun 15 '18 at 17:21
  • $\begingroup$ Do not take it in bad part, but I can hardly answer this further question within a three line comment. $\endgroup$ – J.-E. Pin Jun 15 '18 at 20:06
  • $\begingroup$ Ok. But you can try to provide an answer pretty along the lines you provided above. Anyway, you are welcome, even if you prefer not to. $\endgroup$ – Javier Arias Jun 17 '18 at 0:29

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.