next up previous
Next: 8. TC in Monoids Up: Observations on Coset Enumeration Previous: 6. Sims' Approach

7. Simulating Todd-Coxeter with Prefix String Rewriting

In this section we want to present a procedure which emulates TC. It is based on the algebraic procedure presented in [14] for simulating TC using prefix Gröbner bases methods.

Informally the procedure works as follows:

The input consists of the group presentation in terms of the sets $\bar{\Sigma}$, $T_I = \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \mid a \in \Sigma \}$ and $T_R = \{ r \longrightarrow\lambda \mid r \in R \}$, and the generators of the subgroup encoded in the set of rules $T_S = \{ s \longrightarrow\lambda \mid s \in S \}$. Additionally we will use the following sets:

The set N, which on termination will contain the coset representatives, is initialized as the set containing the empty string only, which is the coset representative of the subgroup itself. During the computation this set remains prefix-closed. The set B of possible candidates for further cosets is initialized as $B:=\{a\mid a\in\bar{\Sigma}\}$. The set G, which on termination will encode the non-trivial part of the coset table, is computed by prefix interreducing the set $T_I \cup T_R \cup T_S$. Hence, the rules in G can be used to decide the membership for the subgroup of ${\cal F}$ that is generated by $S \cup R$. This completes the initialization phase.

Now as long as there still are candidates for new cosets in B the following actions are performed: We choose and remove the smallest element from B (with respect to the length-lexicographical ordering) and call it $\tau$. If $\tau$ is not prefix-reducible by G, then it is added to N and all elements of the form $\tau a$ are added to B, where $a \in\bar{\Sigma}$. Next $H:=\{\tau \ell \longrightarrow\tau r \mid \ell \longrightarrow r \in T_I \cup T_R\}$ is determined, which in TC corresponds to the process of marking the first and the last slot of each relator table with the newly found coset representative $\tau$. Finally the set $G\cup H$, which corresponds to the subgroup of ${\cal F}$ that is generated by $S \cup
\{\tau \circ r \circ\tau^{-1}\mid \tau \in N, r\in R\}$, is prefix interreduced. Hence, we approximate the potentially infinite generating set of the subgroup $\langle S \cup N(R)\rangle$ of ${\cal F}$. Based on the new set G some elements of N may become prefix reducible. These have to be removed from N, as they are no longer coset representatives. This corresponds to the collapse of cosets in TC.

Given: 		 (

$\bar{\Sigma}, T = T_I \cup T_R)$,

$N := \{ \lambda \}$;

$B:=\{a\mid a\in\bar{\Sigma}\}$;

$G := {\sf prefix.interreduce}(T \cup T_S)$;

$B \neq \emptyset$

$\tau := {\sf min}_{<}(B)$;

$B := B \backslash \{ \tau \}$;
		 if  $\tau$
is not prefix  reducible by G

$N := N \cup \{ \tau \}$;

$B := B \cup \{ \tau a \mid a \in \bar{\Sigma} \}$;

$H := \{ \tau \ell \longrightarrow\tau r \mid \ell \longrightarrow r \in T \}$;

$G := {\sf prefix.interreduce}(G \cup H)$;

$N := N \backslash \{ w \in N \mid w \mbox{ is reducible by } $G$\}$;

The following theorem is a direct conclusion of the results stated in [14].

Theorem 4   Let R and S be as specified above. Procedure GENERALIZED TC SIMULATION terminates iff the subgroup generated by $S \cup N(R)$ has finite index in ${\cal F}$.

Applying this procedure to Example 3 it terminates with 24 cosets in N and the set G encodes the non-trivial part of the coset table.

next up previous
Next: 8. TC in Monoids Up: Observations on Coset Enumeration Previous: 6. Sims' Approach
| ZCA Home | Reports |