1
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2018 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$ Jun 13, 2018 at 22:07

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Jun 15, 2018 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, 2018 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$ Jun 17, 2018 at 0:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .