What's the current state of one-rule semi-Thue system termination problem?

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: [email protected], 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

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$.

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.