6
$\begingroup$

What's the current state of one-rule semi-Thue system termination problem? Search produces a lot of references, but it's hard to find out if decidability of this problem has been proven or not.

$\endgroup$
3
  • $\begingroup$ It's probably worth mentioning that it was Martin Greendlinger who told his students about this problem long ago. To be precise, he was talking about termination of one-rule Markov algorithm: en.wikipedia.org/wiki/Markov_algorithm $\endgroup$
    – TT_
    Sep 16, 2014 at 23:04
  • $\begingroup$ Speaking of word problem for 1-relator monoid, I'd like to add the reference to a paper by Victor Guba: mathnet.ru/php/… $\endgroup$
    – TT_
    Sep 24, 2014 at 18:46
  • $\begingroup$ See also S.A.Osipov "Termination problem for Markov algorithm" : cheb.tsput.ru/… $\endgroup$
    – TT_
    Oct 30, 2014 at 18:58

3 Answers 3

4
$\begingroup$

It's still (personal experience) agonisingly difficult. The advance using automata was done by Hans Zantema and his friends for some classes of one-rule systems. Also there is a long paper by Kobayashi and some other guys where they develop the whole theory about termination for complicated classes of 1-rule systems based on splitting words in certain way (and in which it is made more explicit the old proof of Senizerques about termination of the systems of the form $0^p1^q\to 1^r0^s$).

Also in the paper of Victor Guba (that famous 1998 paper about one-relator semigroups) there sits inside the proof of the main theorem where he associates another presentation for the group generated by prefixes, that we have a rewriting system (not necessarily 1-rule) and the question is whether it will terminate. May be something can be squized from there but I failed.

Well, the situation is very strange with 1-rule systems. For some time it was beleived that non-termination happens if we can spot loops. But there are examples showing that shortest possible loops to appear we have to wait superexponentially long (in input of the 1-rule system). It's all wild.

In general it's very good such brave people still exist who are interested in this difficult problem. Just in case my e-mail: victor.maltcev@gmail.com, please do contact me and we could talk more

P.S.: About word problem for 1-relators, it's a mystery. Yet, good people believe that Dehn function for 1-relator semigroups have to be polynomial, and for guys like $\langle a,b:aUb=b\rangle$ even at most quadratic. We've got some examples of 1-relator semigroups which we (unproved) believe cannot admit finite complete rewriting systems

$\endgroup$
1
  • $\begingroup$ Also thank you for mentioning Victor Guba's paper (I believe you meant year 1997). I have to spend some weekends and read it carefully. $\endgroup$
    – TT_
    Sep 27, 2014 at 16:09
3
$\begingroup$

An important part of this problem is, as Ben points out in his answer, the word problem for one-relation monoids. This problem is still open, but it has been reduced to a number of special cases. I'll summarise these developments; there are a few gaps in proofs floating around, so sometimes one sees claims that cases are solved when they remain open. Here's an overview.

Consider the one-relation monoid $M = \operatorname{Mon}\langle A \mid U = V \rangle$.

The case $U=1$ is called the special case, and was solved in 1960 by Adjan [1] (sometimes this proof is attributed to his famous 1966 monograph, in which the proof also appears). He reduces the word problem in such monoids to the group case $\operatorname{Gp}\langle A \mid U=1 \rangle$, in which the word problem is famously decidable by Magnus. In fact, Adjan's student Makanin extended this result in his 1966 PhD thesis, and proved that the word problem in $k$-relator special monoids reduces to the word problem in $k$-relator groups.

A word is called hypersimple if it is self-overlap free, e.g. $abb$ is hypersimple but $aba$ is not. In our one-relation monoid, if the relation $U=V$ is of the form $\alpha U \alpha = \alpha V \alpha$ or $\alpha U \alpha = \alpha$ for some hypersimple word $\alpha \in A^\ast$, then we say that the relation $U=V$ is compressible with respect to $\alpha$. To every compressible one-relation monoid $M$ there is an associated one-relation monoid $M'$ with a shorter defining relation. Adjan and his student Oganesjan [2] proved in 1978 that the word problem in a compressible one-relation monoid $M$ reduces to the word problem for $M'$.

Further reductions are possible. Adjan [3] showed in 1960 that our one-relation monoid $M$ above is cancellative if and only if $U$ and $V$ have different initial and different final letters (this is an obvious necessary condition), and that in this case $M$ embeds in the group $\operatorname{Gp}\langle A \mid U=V \rangle$. Thus in this case the word problem is again decidable by Magnus' result. As with the special case, this result is also occasionally incorrectly attributed to the 1966 monograph.

Thus the word problem for one-relation monoids can be reduced to the case when the words $U = V$ either begin in the same letter or end in the same letter (but not both, as otherwise it is not hard to see that we could compress).

This leaves us with the right-cancellative cases $\operatorname{Mon}\langle A \mid aUb = aVa \rangle$ and $\operatorname{Mon}\langle A \mid aUb = a \rangle$, as well as the symmetrical left-cancellative cases $\operatorname{Mon}\langle A \mid aUb = bVb \rangle$ and $\operatorname{Mon}\langle A \mid aUb = b \rangle$. It is not difficult to consider all words in reverse and reduce the left-cancellative to the right-cancellative case, and vice versa.

In 1987, Adjan and Oganesjan [4] (note that this paper is named very similarly to the 1978 paper, both in the original Russian as well as the English translation!) reduced these remaining cases to the two-generated case (in the excellent survey [5], this is incorrectly attributed to the 1978 paper [3]). Thus the remaining cases are

$$ \operatorname{Mon}\langle a,b \mid aUb = aVa \rangle \qquad \text{and} \qquad \operatorname{Mon}\langle a,b \mid aUb = a \rangle. $$

In 1982, Oganesjan [6] claimed a proof that the word problem is decidable in $\operatorname{Mon}\langle a,b \mid aUb = a \rangle$, i.e. the second of the cases above. However, this proof depends on a result by O. A. Sarkisjan (another one of Adjan's students, as you might have guessed at this point) from the year before [7]. She claimed to have proved that the left and right divisibility problems are decidable in all cancellative one-relation monoids. However, Adjan discovered a gap in this proof in the 90s, and the gap remains unfilled. I am not certain what the gap is. In any case, this gap means Oganesjan's result is not yet proved (though apparently Adjan believed that the result was nevertheless correct).

Thus we are up to speed -- those two cases remain the open ones. If the word problem is decidable in the two classes specified above, then it is decidable for all one-relation monoids. A number of special cases are known to be decidable of the above (and, in fact, it is known that almost all, in a well-defined sense, one-relation monoids have decidable word problem), but writing out all the known partial cases would be a bit ridiculous for the scope of this answer.

Even small cases can cause large headaches. For example, even the "tiny" case $\operatorname{Mon}\langle a,b \mid abaab = a \rangle$ was beyond the reach of the methods of Howie and Pride [8], though this, as it turns out, can be solved using Adjan's pseudo-algorithm $\mathfrak{A}$ for solving the right divisibility problem (in this case $\mathfrak{A}$ turns out to be an algorithm) -- but that's a topic for a different post/question!

References:

[1] Adjan, S. I. The problem of identity in associative systems of a special form. Dokl. Akad. Nauk SSSR 135 (1960), 1297–1300.

[2] Adjan, S. I.; Oganesjan, G. U. On problems of equality and divisibility in semigroups with a single defining relation. Izv. Akad. Nauk SSSR Ser. Mat. 42 (1978), no. 2, 219–225, 469.

[3] Adjan, S. I., On the embeddability of semigroups in groups, Dokl. Akad. Nauk SSSR 133 (1960), 255–257.

[4] Adjan, S. I.; Oganesjan, G. U.; On the word and divisibility problems for semigroups with one relation. Mat. Zametki 41 (1987), no. 3, 412–421, 458.

[5] Adjan, S. I.; Durnev, V. G.; Algorithmic problems for groups and semigroups., Uspekhi Mat. Nauk 55 (2000), no. 2(332), 3–94.

[6] Oganesjan, G. U.; Semigroups with one relation and semigroups without cycles., Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 1, 88–94, 191.

[7] O. A. Sarkisjan; On the word and divisibility problems in semigroups and groups without cycles, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), 1424–1440.

[8] Howie, James; Pride, Stephen J.; The word problem for one-relator semigroups. Math. Proc. Cambridge Philos. Soc. 99 (1986), no. 1, 33–44.

$\endgroup$
1
  • $\begingroup$ I wonder if (positive) solution for the word problem for one-relation monoids would really help to solve termination problem? Of course the methods could be similar or even the same, but mere fact that the WP is solvable does not seem to imply the TP solution. $\endgroup$
    – TT_
    Jan 20, 2021 at 23:18
2
$\begingroup$

The word problem for one-relator monoids is still open. Adjan solved the problem for relations of the form $w=1$. There are many reductions in the literature most by Adjan and coworkers. For instance it is reduced to relations of the form $bua=bvc$ where $a\neq c$.

$\endgroup$
3
  • $\begingroup$ The case $bua = b$ also remains open; there is a gap in Oganesjan's old proof of the decidability of such one-relator monoids. $\endgroup$ Jan 19, 2021 at 15:45
  • $\begingroup$ @Carl-FredrikNybergBrodda I didn't realize that. $\endgroup$ Jan 19, 2021 at 17:41
  • 2
    $\begingroup$ To be clear, the gap is in a proof by O. A. Sarkisjan (another one of Adjan's students, like Oganesjan) that the left+right divisibility problems are decidable in group-embeddable one-relation monoids. Oganesjan uses this result in his proof. I'll write an answer summarising some of these developments soon; it is a bit tricky navigating some of these old papers. $\endgroup$ Jan 19, 2021 at 19:34

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.