Does every automatic group have a presentation through some finite convergent string-rewriting system? Does every automatic monoid have an automatic structure such that the set of representatives is a prefix-closed cross-section?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

For a finite alphabet $\Sigma$, we define the padded extension $\Sigma_\#$ of $\Sigma$ as

$$\Sigma_\#:=((\Sigma\cup\{\#\})\times(\Sigma\cup\{\#\}))\setminus \{(\#,\#)\},$$

where $\#$ is an additional symbol. A mapping $\nu:\Sigma^*\times\Sigma^*\to\Sigma^*_\#$ is then used to encode pairs of strings from $\Sigma^*$ as strings from $\Sigma^*_\#$ as follows:\ if $u:=a_1a_2\cdots a_n$ and $v:= b_1b_2\cdots b_m$, where $a_1,\ldots,a_n, b_1,\ldots,b_m\in\Sigma$, then

$$\nu(u,v):= \left\{ \begin{array}{ll} (a_1,b_1)(a_2,b_2)\cdots(a_m,b_m)(a_{m+1},\#)\cdots(a_n,\#), & \mathrm{if} \; m<n,\\ (a_1,b_1)(a_2,b_2)\cdots(a_m,b_m), & \mathrm{if} \; m=n,\\ (a_1,b_1)(a_2,b_2)\cdots(a_n,b_n)(\#,b_{n+1})\cdots(\#,b_m), & \mathrm{if} \; m>n. \end{array} \right.$$

Now a subset $L\subseteq \Sigma^*\times\Sigma^*$ is called synchronously regular, s-regular for short, if $\nu(L)\subseteq \Sigma^*_\#$ is accepted by some finite state acceptor (fsa).

An automatic structure for a finitely generated monoid-presentation $(\Sigma;R)$ consists of a fsa $W$ over $\Sigma$, a fsa $M_=$ over $\Sigma_\#$, and fsa's $M_a$ $(a\in\Sigma)$ over $\Sigma_\#$ satisfying the following conditions:

1. $L(W)\subseteq\Sigma^*$ is a complete set of (not necessarily unique) representatives for the monoid $M_R$ presented by $(\Sigma;R)$, that is, $L(W)\cap[w]_R\not=\emptyset$ holds for each $w\in\Sigma^*$,

2. $L(M_=)=\{\nu(u,v)\mid u,v\in L(W) \; \mathrm{and} \; u\leftrightarrow^*_R v\}$, and

3. for all $a\in\Sigma$, $L(M_a)=\{\nu(u,v)\mid u,v\in L(W)$ and $ua\leftrightarrow^*_R v\}$.

A monoid-presentation is called automatic if it admits an automatic structure, and a monoid is called automatic if it has an automatic presentation.

Groups with automatic structure have been investigated thoroughly [Otto, 1998], while the automatic monoids have been investigated only recently [Otto, 1998]. It is known that there exists monoids (in fact, groups) that can be presented through finite convergent string-rewriting systems, but that are not automatic [Otto, 1998].

QUESTION 1: Does every automatic group have a presentation through some finite convergent string-rewriting system?

For monoids in general the answer is negative as proved by an example given in [Otto, 1998].

If $(W, M_=, M_a (a\in\Sigma))$ is an automatic structure for a monoid-presentation $(\Sigma;R)$, then the language $L(W)$ contains one or more strings from every congruence class $[w]_R (w\in\Sigma^*)$. Actually, it can be required without loss of generality that $L(W)$ is a cross-section for $(\Sigma;R)$, that is, it contains exactly one string from every congruence class [Otto, 1998].

Instead of requiring uniqueness one can also transform the given automatic structure in such a way as to obtain one for which the set of representatives is prefix-closed. However, the following question is still open.

QUESTION 2: Does every automatic monoid have an automatic structure such that the set of representatives is a prefix-closed cross-section?

Gersten stated this question for the special case of groups [Otto, 1998]. If the language $L(W)$ is a prefix-closed cross-section, then there exists an s-regular convergent prefix-rewriting system $P$ on $\Sigma$ such that the right-congruence generated by $P$ coincides with the congruence generated by $R$, and $L(W)$ coincides with the set of irreducible strings mod $P$. Conversely, if a monoid-presentation admits an s-regular convergent prefix-rewriting system, then it has an automatic structure $(W, M_=, M_a (a\in\Sigma))$ such that the set $L(W)$ is a prefix-closed cross-section. Thus, QUESTION 2 can be reformulated as follows.

QUESTION 2 (restated): Does every finitely presented automatic monoid admit an s-regular convergent prefix-rewriting system?

For additional information on monoid-presentations and convergent string-rewriting systems see e.g.\ [Otto, 1998], and for the notion of prefix-rewriting systems see e.g.\ [Otto, 1998].