[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 
Originator: Friedrich Otto [OSKM98]
Date: March 1998
Summary: Does every automatic group have a presentation through some finite convergent stringrewriting system?Does every automatic monoid have an automatic structure such that the set of representatives is a prefixclosed crosssection?
For a finite alphabet Σ, we define the padded extension Σ_{#} of Σ as
Σ_{#}:=((Σ⋃{#})×(Σ⋃{#}))∖ {(#,#)}, 
where # is an additional symbol.
A mapping ν:Σ^{*}×Σ^{*}→Σ_{#}^{*} is then used
to encode pairs of strings from Σ^{*} as strings from Σ_{#}^{*}
as follows:
if u:=a_{1}a_{2}⋯ a_{n} and v:= b_{1}b_{2}⋯ b_{m}, where
a_{1},…,a_{n}, b_{1},…,b_{m}∈Σ, then
ν(u,v):=  ⎧ ⎪ ⎨ ⎪ ⎩ 

Now a subset L⊆ Σ^{*}×Σ^{*} is called synchronously regular, sregular for short, if ν(L)⊆ Σ_{#}^{*} is accepted by some finite state acceptor (fsa).
An automatic structure for a finitely generated monoidpresentation (Σ;R) consists of a fsa W over Σ, a fsa M_{=} over Σ_{#}, and fsa’s M_{a} (a∈Σ) over Σ_{#} satisfying the following conditions:
A monoidpresentation 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 [Eps92], while the automatic monoids have been investigated only recently [CRRT96]. It is known that there exists monoids (in fact, groups) that can be presented through finite convergent stringrewriting systems, but that are not automatic [Ger92a].
QUESTION 1: Does every automatic group have a presentation through some finite convergent stringrewriting system?
For monoids in general the answer is negative as proved by an example given in [OSKM98].
If (W, M_{=}, M_{a} (a∈Σ)) is an automatic structure for a monoidpresentation (Σ;R), then the language L(W) contains one or more strings from every congruence class [w]_{R} (w∈Σ^{*}). Actually, it can be required without loss of generality that L(W) is a crosssection for (Σ;R), that is, it contains exactly one string from every congruence class [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 prefixclosed. 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 prefixclosed crosssection?
Gersten stated this question for the special case of groups [Ger92b]. If the language L(W) is a prefixclosed crosssection, then there exists an sregular convergent prefixrewriting system P on Σ such that the rightcongruence 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 monoidpresentation admits an sregular convergent prefixrewriting system, then it has an automatic structure (W, M_{=}, M_{a} (a∈Σ)) such that the set L(W) is a prefixclosed crosssection. Thus, QUESTION 2 can be reformulated as follows.
QUESTION 2 (restated): Does every finitely presented automatic monoid admit an sregular convergent prefixrewriting system?
For additional information on monoidpresentations and convergent stringrewriting systems see e.g. [BO93], and for the notion of prefixrewriting systems see e.g. [KM89].
[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 