\documentclass{rtaloop}
\rtalabel{auto-groups-present}


\begin{document}
\begin{problem}{Friedrich Otto}{\cite{otto:rta98}}{March 1998}

\begin{abstract}
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?
\end{abstract}

For a finite alphabet $\Sigma$, 
we define the {\em 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,\#), & {\rm if} \;
m<n,\\
(a_1,b_1)(a_2,b_2)\cdots(a_m,b_m), & {\rm if} \; m=n,\\
(a_1,b_1)(a_2,b_2)\cdots(a_n,b_n)(\#,b_{n+1})\cdots(\#,b_m), & {\rm if} \;
m>n.
\end{array} \right. \]
Now a subset $L\subseteq \Sigma^*\times\Sigma^*$ is called
{\em synchronously regular}, {\em s-regular\/} for short, 
if $\nu(L)\subseteq \Sigma^*_\#$ is 
accepted by some finite state acceptor (fsa).

An {\em 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:
\begin{enumerate}
\item
$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^*$,
\item
 $L(M_=)=\{\nu(u,v)\mid u,v\in L(W) \; {\rm and} \;
u\leftrightarrow^*_R v\}$, and 
\item
for all $a\in\Sigma$, $L(M_a)=\{\nu(u,v)\mid u,v\in L(W)$ and 
$ua\leftrightarrow^*_R v\}$.
\end{enumerate}

A monoid-presentation is called {\em automatic\/} if it admits an
automatic structure, and a monoid is called {\em automatic\/} if it has
an automatic presentation.

Groups with automatic structure have been investigated thoroughly
\cite{Eps92}, while
the automatic monoids have been investigated only recently \cite{CRRT96}.
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 \cite{Ger92a}.

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 \cite{otto:rta98}.

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 {\em cross-section\/} for $(\Sigma;R)$, that is, it contains
exactly one string from every congruence class \cite{Eps92}.

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 \cite{Ger92b}.
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.
\vspace{+0.2cm}

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.\ \cite{BoOt93},
and for the notion of prefix-rewriting systems see e.g.\ \cite{KuMa89}.




\end{problem}
\end{document}