Information About

Todd-coxeter Algorithm
  CATEGORIES ABOUT TODD-COXETER ALGORITHM
   
algorithms
   
computational group theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



One implementation of the algorithm proceeds as follows. Define X' to be the set of generators X and their inverses. Let H = \langle h_1, h_2, \ldots, h_s angle where the h_i are words of elements of X' . There are three types of tables that will be used: a coset table, a relation table for each relation in R , and a subgroup table for each generator h_i of H . Information is gradually added to these tables, and once they are filled in, all cosets have been enumerated and the algorithm terminates.

The coset table is used to store the relationships between the known cosets when multiplying by a generator. It has rows representing cosets of H and a column for each element of X' . Let C_i denote the coset of the ''i''th row of the coset table, and let g_j \in X' denote generator of the ''j''th column. The entry of the coset table in row ''i'', column ''j'' is defined to be (if known) ''k'', where ''k'' is such that C_k = C_ig_j .

The relation tables are used to detect when some of the cosets we have found are actually equivalent. One relation table for each relation in R is maintained. Let 1 = g_{n_1} g_{n_2} \cdots g_{n_t} be a relation in R , where g_{n_i} \in X' . The relation table has rows representing the cosets of H , as in the coset table. It has ''t'' columns, and the entry in the ''i''th row and ''j''th column is defined to be (if known) ''k'', where C_k = C_i g_{n_1} g_{n_2} \cdots g_{n_j} . In particular, the ''it''th entry is initially ''i'', since g_{n_1} g_{n_2} \cdots g_{n_t} = 1.

Finally, the subgroup tables are similar to the relation tables, except that the keep track of possible relations of the generators of H . For each generator h_n = g_{n_1} g_{n_2} \cdots g_{n_t} of H , with g_{n_i} \in X' , we create a subgroup table. It has only one row, corresponding to the coset of H itself. It has ''t'' columns, and the entry in the ''j''th column is defined (if known) to be ''k'', where C_k = H g_{n_1} g_{n_2} \cdots g_{n_j} .

When a row of a relation or subgroup table is completed, a new piece of information C_i = C_j g , g \in X' , is found. This is known as a ''deduction''. From the deduction, we may be able to fill in additional entries of the relation and subgroup tables, resulting in possible additional deductions. We can fill in the entries of the coset table corresponding to the equations C_i = C_j g and C_j = C_i g^{-1} .

However, when filling in the coset table, it is possible that we may already have an entry for the equation, but the entry has a different value. In this case, we have discovered that two of our cosets are actually the same, known as a ''coincidence''. Suppose C_i = C_j , with i < j . We replace all instances of ''j'' in the tables with ''i''. Then, we fill in all possible entries of the tables, possibly leading to more deductions and coincidences.