BECNBIC, Número 3(Artículo 5), 2001

BOLETÍN ELECTRÓNICO CIENTÍFICO
DEL NODO BRASILERO
DE INVESTIGADORES COLOMBIANOS
Número 3(Artículo 5), 2001

TÍTULO
AN EFFICIENT STRATEGY FOR WORD-CYCLE COMPLETION IN FINITELY PRESENTED GROUPS

TIPO: Dissertação de Mestrado com publicação

AUTOR: Luiz M. R. Gadelha Jr gadelha@cic.unb.br,lgadelha@certisign.com.br

IDIOMA: Portugués e Inglês

DIRECCIÓN PARA CONTACTO
CertiSign Certificadora Digital, Rua Lauro Müller, 116 - Gr. 2705,
22290-160 Rio de Janeiro, RJ - Brasil.

ORIENTADOR: Mauricio Ayala-Rincón ayala@mat.unb.br
DIRECCIÓN PARA CONTACTO
Departamento de Matemática
Universidade de Brasília
70910-900 Brasília, DF - Brasil

FECHA DE LA DEFENSA: 18 de dezembro de 2001

ENTIDADES QUE FINANCIARON LA INVESTIGACIÓN: CNPq, CAPES

INSTITUCIÓN QUE OTORGÓ EL TÍTULO
Departamento de Ciência de Computação
Universidade de Brasília
70910-900 Brasília, DF - Brasil

KEYWORDS: String-Rewriting Systems, Knuth-Bendix Completion, Word Problem in Finitely Presented Groups

ABSTRACT

The analysis of combinatorial properties of algebraic structures such as monoids and groups has been of fundamental relevance in the development of the theory of computation. Two examples that illustrate this fact are

the nice relations between formal language theory, the theory of automata, the word problem for groups and string-rewriting systems and
the classical connections between decidability of problems over algebraic structures and of fundamental computational problems.

More specifically,

the first kind of relations could be illustrated with well-known results such as the regularity of the language given by the word problem of finitely presented groups that are finite and the polynomial construction of finite-state acceptors for the set of reducible and irreducible strings using a finite string-rewriting system [7,10].
A relevant illustration of the second kind of connections is the well-known proof of the undecidability of the Post Correspondence Problem, that is based on the undecidability of the word problem in monoids as presented in many fundamental books on formal language, automata and computational theory (see for example [11]).

Knuth-Bendix completion has been used to compute, from a (string-)rewriting system

and a reduction ordering

, a rewriting system $R_\infty$ that defines the same equational theory as

being compatible with the reduction ordering, and hence noetherian or terminating, and that is confluent [6]. Additionally, if the reduction ordering is total, then this procedure terminates successfully if and only if a finite system $R_\infty$ with these properties exists. For a group

presented by $\langle \Sigma;R\rangle$ , where $\Sigma$ is a finite alphabet and

a set of equational relations between words over these alphabet, the word problem is effectively reducible to the membership problem for the congruence class $[\epsilon]_R$ of the empty string, $\epsilon$ . Even for small systems

that result in small systems $R_\infty$ intermediate sets of rules can become arbitrarily large, and in particular in the setting of group completion, each intermediate rule induces several other rules based on the group axioms. This makes space efficient methods for group completion extremely relevant. In the setting of presentations of groups from each rule its cyclic permutations, its inverse and the cyclic permutations thereof are induced by this symmetrization process. To save space this information can be stored in a word-cycle. In [3] a completion procedure that uses word-cycles was introduced. This procedure is presented as a set of four inference rules that are applied to a set of word-cycles. When the procedure terminates for a given input

, it generates a finite set of word-cycles $Z^\infty$ that describes the same congruence as

. This set of word-cycles can be converted into a confluent string-rewriting system and consequently, if it is also terminating, it corresponds to a (convergent system or an effective) solution for the word problem of the group. Although this method represents an important improvement on space-complexity its practical time performance is very bad for simple groups as the dihedral and Fibonacci groups. Here we present an efficient strategy for applying the inference rules of the Cremanns-Otto procedure, that is complete in the sense that the set of persistent word-cycles corresponds to a (possibly infinite) solution for the reduced word problem of the given group. The results presented here are part of the first author master's thesis [4] and will appear in [5].

To our knowledge [8], our implementation of the Cremanns-Otto procedure for completing finitely presented groups was the first one given and our experimental work pointed out practical problems in the straightforward application of the inference rules introduced in [3]. In particular, we detected that uncontrolled application of the rules gives rise to an explosion on the running time making inefficient the procedure and therefore non competitive with the classical application of Knuth-Bendix completion over strings. This was checked for very simple but relevant examples as the ones of the dihedral groups, generated by $D_{2n}=\langle a,b\;\vert\;a^n,b^2,b^{-1}aba\rangle$ for which the input set of word-cycles corresponds to $Z_0=\{[a^n]_\approx,[b^2]_\approx,[Baba]_\approx\}$ (

, for instance, is the group of symmetries of the square). Mainly, three inefficiency problems were detected and solved in our completion strategy:

non-deterministic application of the inference rules ${\cal P}1, {\cal P}2$ and ${\cal P}3$ (that is, of the procedure ${\cal I}$ nterreduce) gives rise to redundant application of these rules on the same word-cycles;
uncontrolled application of the inference rules ${\cal P}3$ and ${\cal P}4$ gives rise to repetitive and redundant application of these rules on the same pairs of word-cycles and
inference of new word-cycles by applying rule ${\cal P}4$ and further application of these inference rule on the non simplified new word-cycles propagates inefficiently generation of redundant non interreduced word-cycles.

Our completion strategy was proved to be fair and in fact a completion procedure. From the practical point of view, its implementation results competitive with the application of Knuth-Bendix completion over strings for very important examples as the dihedral groups. But for simple examples as the Fibonacci groups Knuth-Bendix completion over strings results too much better than completion over word-cycles. The Fibonacci groups are defined as

$\langle x_0, ..., x_{k-1} \; \vert \; x_{(i \; \mbox{mod} \; k)} x_{(i+1 \; \mbox{mod} \; k)} = x_{(i+2 \; \mbox{mod} \; k)},$ for $0 \leq i \leq k-1\rangle$ . Although for the very small Fibonacci groups as

$\langle a,b,c \;\vert\; ab=c,\; bc=a,\; ca=b\rangle$ , the implementation runs for hours before stopping giving a correct answer. As further work, additional improvements could be incorporated to our strategy. For example, since word-cycles are combinatorial data structures, matching and unification could be specialized. Well-known linear string pattern matching algorithms can be adapted for detecting all possible applications of the inference rules ${\cal P}3$ and ${\cal P}4$ on a pair of word-cycles in linear time. This improvement was not crucial for our experiments since, for our input groups, the size of the persistent word-cycles was relatively small. Additionally, to validate this kind of completion procedures, the determination of particular groups for which the computational space is critical and consequently Cremanns-Otto style of Knuth-Bendix completion over word-cycles is better than Knuth-Bendix completion over strings is an essential work to be done.

BIBLIOGRAPHY

1: F. Baader and T. Nipkow.
Term-Rewriting and All That.
Cambridge University Press, 1998.
2: R. Book and F. Otto.
String-Rewriting Systems.
Springer-Verlag, 1993.
3: R. Cremanns and F. Otto.
A completion procedure for finitely presented groups that is based on word cycles.
Technical report, Universität Gesamthochschule Kassel, 1998.
4: L. M. R. Gadelha Jr.
Aplicações de Técnicas de Reescrita ao Problema da Palavra em Teoria dos Grupos.
Master's thesis, Departamento de Ciência da Computação, Universidade de Brasília, December 2000.
In Portuguese.
5: L. M. R. Gadelha and M. Ayala-Rincón.
An Efficient Strategy for Word-Cycle Completion in Finitely Presented Groups.
In XXI International Conference of the Chilean Computer Science Society, Arica, Chile. IEEE Computer Press, November 2001.
6: D. Knuth and P. Bendix.
Simple word problems in universal algebra.
In J. Leech, editor, Computational Problems in Abstract Algebra, pages 263-297. Pergamon Press, 1970.
7: F. Otto.
On the connections between rewriting and formal language theory.
In 10th International Conference on Rewriting Techniques and Applications, volume 1631 of Lecture Notes in Computer Science, pages 332-355, Trento, Italy, 1999. Springer-Verlag.
8: F. Otto.
Personal communication.
2000.
9: C. Sims.
Computation with Finitely Presented Groups, volume 48 of Encyclopedia of Mathematics and its Applications.
Cambridge University Press, 1994.
10: I. A. Stewart and R. M. Thomas.
Formal Languages and the Word Problem for Groups.
In Groups St Andrews 1997 in Bath, II, volume 2 of London Mathematical Society Lecture Note Series, pages 689-700. Cambridge University Press, 1999.
11: T. Sudkamp.
Languages and Machines: An Introduction to the Theory of Computer Science.
Addison-Wesley, 1997.

BECNBIC,3(5)2001

De vuelta al ÍNDICE