[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #91

Originator: Friedrich Otto [OSKM98]
Date: March 1998

Summary: 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?

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₁a₂⋯ a_n and v:= b₁b₂⋯ b_m, where a₁,…,a_n, b₁,…,b_m∈Σ, then

Now a subset L⊆ Σ^*×Σ^* is called synchronously regular, s-regular for short, if ν(L)⊆ Σ_#^* is accepted by some finite state acceptor (fsa).

An automatic structure for a finitely generated monoid-presentation (Σ;R) consists of a fsa W over Σ, a fsa M₌ over Σ_#, and fsa’s M_a (a∈Σ) over Σ_# satisfying the following conditions:

1. L(W)⊆Σ^* is a complete set of (not necessarily unique) representatives for the monoid M_R presented by (Σ;R), that is, L(W)∩[w]_R≠∅ holds for each w∈Σ^*,
2. L(M₌)={ν(u,v)∣ u,v∈ L(W)   and   u↔_R^* v}, and
3. for all a∈Σ, L(M_a)={ν(u,v)∣ u,v∈ L(W) and ua↔_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 [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 string-rewriting systems, but that are not automatic [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 [OSKM98].

If (W, M₌, M_a (a∈Σ)) is an automatic structure for a monoid-presentation (Σ;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 cross-section 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 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 [Ger92b]. If the language L(W) is a prefix-closed cross-section, then there exists an s-regular convergent prefix-rewriting system P on Σ 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∈Σ)) 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. [BO93], and for the notion of prefix-rewriting systems see e.g. [KM89].

References

[BO93]

R. V. Book and Friedrich Otto. String-Rewriting Systems. Springer-Verlag, 1993.

[CRRT96]

C. M. Campbell, E. F. Robertson, N. Ruskuc, and M. R. Thomas. On subsemigroups and ideals in free products of semigroups. Int. J. of Algebra and Computation, 6:571–591, 1996.

[Eps92]

D. B. A. Epstein. Word Processing In Groups. XJones and Bartlett Publishers, 1992.

[Ger92a]

S. M. Gersten. Dehn functions and l1-norms of finite presentations. In G. Baumslag and C. F. Miller III, editors, Algorithms and Classification in Combinatorial Group Theory, volume 23 of Math. Sciences Research Institute Publ., pages 195–224. Springer-Verlag, 1992.

[Ger92b]

S. M. Gersten. Problems on automatic groups. In G. Baumslag and C. F. Miller III, editors, Algorithms and Classification in Combinatorial Group Theory, volume 23 of Math. Sciences Research Institute Publ., pages 225–232. Springer-Verlag, 1992.

[KM89]

N. Kuhn and Klaus Madlener. A method for enumerating cosets of a group presented by a canonical system. In Proc. ISSAC’89, pages 338–350. ACM, 1989.

[OSKM98]

Friedrich Otto, Andrea Sattler-Klein, and Klaus Madlener. Automatic monoids versus monoids with finite convergent presentations. In Tobias Nipkow, editor, 9th International Conference on Rewriting Techniques and Applications, volume 1379 of Lecture Notes in Computer Science, pages 32–46, Tsukuba, Japan, April 1998. Springer-Verlag.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]