
The Library
Coset enumeration as closure computation
Tools
Beynon, Meurig (1982) Coset enumeration as closure computation. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-042.pdf - Requires a PDF viewer. Download (12Mb) | Preview |
Abstract
Procedures for coset enumeration have been the subject of considerable attention since the first machine programs were developed in the early 60's. Most of these procedures, like the original Todd-Coxeter procedure from which they derived, are expressed in terms of operations on integer arrays whose entries denote coset representatives. The first formal justification of a coset enumeration procedure [T] is also expressed in terms of such a representation.
As the study of computer algorithms has often shown, there are disadvantages in formulating algorithmic processes in terms of a particular data representation. For instance, it can make a precise description unnecessarily complicated, and a formal verification more obscure. An abstract description, which makes no assumption about how data is represented, usually has conceptual disadvantages, and can be more simply prescribed and verified. The purpose of this paper is to describe and justify abstract formulations of coset enumeration procedures closely related to the original Todd-Coxeter procedure (see [TC] Or D.] Ch. 6), and Trotter's modified version CT].
It may be of interest that the arguments presented here are only sufficient to guarantee termination of the original Todd-Coxeter procedure when enumerating the cosets of a normal subgroup of finite index under modest additional hypotheses on the form of relations used.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Group theory | ||||
Series Name: | Department of Computer Science Research Report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Place of Publication: | Coventry, UK | ||||
Official Date: | September 1982 | ||||
Dates: |
|
||||
Number: | Number 42 | ||||
Number of Pages: | 19 | ||||
DOI: | CS-RR-042 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year