Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-29T05:35:59.215Z Has data issue: false hasContentIssue false
  • English
  • Français

Coset Enumeration Using Prefix Gröbner Bases: An Experimental Approach

Published online by Cambridge University Press:  01 February 2010

Birgit Reinert  and
Dirk Zeckzer
Birgit Reinert
Affiliation:
Fachbereich Informatik, Universität Kaiserslautern, 67663 Kaiserslautern, Germany, [email protected]
Dirk Zeckzer
Affiliation:
Fachbereich Informatik, Universität Kaiserslautern, 67663 Kaiserslautern, Germany, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The authors study a new method for coset enumeration in finitely presented groups. Their method uses prefix Gröbner basis computation in the monoid ring ${\mathbb{K}}[{\cal M}]$, where ${\mathbb{K}}$ is a computable field and ${\cal M}$ a monoid presented by a convergent string-rewriting system. The method is compared to well-known methods for Todd-Coxeter enumeration, using examples from the literature where studies of these methods are reported. New insights into coset enumeration were gained using three different kinds of orderings, combined with new frameworks and strategies implemented in MRC 1.2.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 4 , 2001 , pp. 74 - 134
Copyright
Copyright © London Mathematical Society 2001

References

1.Bosma, W., Cannon, J. and Playoust, C., ‘The Magma algebra system {I}: the user language’, J. Symbolic Comput., 24 (1997) 235–265.CrossRefGoogle Scholar
2.Buch, A. and Hillenbrand, Th., ‘Waldmeister: development of a high performance completion-based theorem prover’, SEKI-ReportSR-96-01, 1996.Google Scholar
3.Buch, A., Fettig, R. and Hillenbrand, Th., ‘On gaining efficiency in completion-based theorem proving’, Proc. RTA 96 (Ed. Ganzinger, Harald , Springer, New Brunswick, NJ, 1996).Google Scholar
4.Buch, A., Fettig, R. and Hillenbrand, Th., Waldmeister: high performance equational theorem proving. Proc. DISCO 96 (Ed. Calmet, Jaques and Limongelli, Carla, Springer, Karlsruhe, 1996).Google Scholar
5.Cannon, J. J., Dimino, L. A., Havas, G. and Watson, J. M., ‘Implementation and analysis of the Todd-Coxeter algorithm’, Math. Comp. 27 (1973) 463–490.CrossRefGoogle Scholar
6.Coxeter, H. S. M., ‘The abstract groups Gm,n,n’, Trans. Amer. Math. Soc. 45 (1939) 73–150.Google Scholar
7.The GAP Group, ‘GAP—Groups, algorithms, and programming’, Version 4.2,2000. http://www-gap.dcs.st-and.ac.uk/~gap.Google Scholar
8.Havas, G., ‘Coset enumeration strategies’, Proc. ISSAC 91 (Ed. Watt, Stephen M., ACM, Bonn, 1991) 191–199.Google Scholar
9.Havas, G. and Ramsey, C., ‘Coset enumeration: ACE version 3’, 1999. http://www.it.uq.edu.au/~havas/ace3.tar.gz.Google Scholar
10.Havas, G. and Ramsey, C., ‘Experiments in coset enumeration’, Technical Report 13, Centre for Discrete Mathematics and Computing, University of Queensland, 1999.Google Scholar
11.Havas, G. and Ramsey, C., ‘The trivial group made easy: a case study in coset enumeration’, Technical Report 15, Centre for Discrete Mathematics and Computing, University of Queensland, 1999.Google Scholar
12.Hillenbrand, H., Buch, A., Vogt, R. and Löchner, B., ‘Waldmeister: high-performance equational deduction’, J. Automat. Reason. 18 (1999); http://www-avenhaus.informatik.uni-kl.de/waldmeister/.Google Scholar
13.Hofbauer, D., Kögl, C., Madlener, K. E., OTTO, F. and Reinert, B., ‘XSSR:an experimental system for string-rewriting—decision problems, algorithms, and implementation’, Federated Logic Conference ‘99 Workshop on Gröbner Bases and Rewriting Techniques (University of Trento, Trento, 1999). http://www-madlener.informatik.uni-kl.de/ag-madlener/research/simplification_en.htmlGoogle Scholar
14.Holt, D. F., ‘KBMAG (Knuth-Bendix in monoids and automatic groups)’, 1996. http://ftp.maths.warwick.ac.uk/people/dfh/kbmag2/kbmag.tar.gz.Google Scholar
15.Leech, J., ‘Coset enumeration on digital computers’, Math. Proc. Cambr. Phil. Soc. 59 (1963) 257–267.CrossRefGoogle Scholar
16.Leech, J., ‘Coset enumeration’, Computational group theory (Academic Press, 1984) 3–18.Google Scholar
17.Linton, S. A., ‘Constructing matrix representations of finitely presented groups’, J. Symbol. Comput. 12 (1991) 427–438.CrossRefGoogle Scholar
18.Macdonald, I. D., ‘On a class of finitely presented groups’, Canad. J. Math. 14 (1962) 602–613.CrossRefGoogle Scholar
19.Madlener, K. and Reinert, B., ‘Computing Gröbner bases in monoid and group rings’, Proc. ISSAC ‘93 (ed. Bronstein, M., ACM, 1993) 254–263.Google Scholar
20.Neübuser, J., ‘An elementary introduction to coset table methods in computational group theory’, Groups St. Andrews 1981, London Math. Soc. Lecture Note Ser. 71 (ed. Campbell, C. M. and Robertson, E. F., Cambridge University Press, 1982) 1–5.Google Scholar
21.Ramsey, C., ‘ACE for amateurs (Version 3.001)’, working draft, Technical Report 14, Centre for Discrete Mathematics and Computing, University of Queensland, 1999.Google Scholar
22.Reinert, B., Observations on coset enumeration, Reports on computer algebra 23 (Centre for Computer Algebra, University of Kaiserslautern, 1998); http://www.mathematik.uni-kl.de/~zca.Google Scholar
23.Reinert, B., MORA, T. and Madlener, K., ‘A note on Nielsen reduction and coset enumeration’, Proc. ISSAC ‘98 (Ed. Gloor, Oliver, ACM, Rostock, 1998).Google Scholar
24.Reinert, B. and Zeckzer, D., MRC—a system for computing Gröbner bases in monoid and group rings, Reports on Computer Algebra 20 (Centre for Computer Algebra, University Kaiserslautern, 1998); http://www.mathematik.uni-kl.de/~zca.Google Scholar
25.Reinert, B. and Zeckzer, D., ‘MRC-data structures and algorithms for computing in monoid and group rings’, Appl. Algebra Engrg. Comm. Comput. 10 (1999) 41–78.CrossRefGoogle Scholar
26.Reinert, B. and Zeckzer, D., Coset enumeration using prefix Gröbner bases in MRC-an experimental approach, Reports on Computer Algebra 25 (Centre for Computer Algebra, University of Kaiserslautern, 1999); http://www.mathematik.uni-kl.de/~zca.Google Scholar
27.Sims, C., ‘The Knuth-Bendix procedure for strings as a substitute for coset enumeration’, J. Symbolic Comput. 12 (1991) 439–442.CrossRefGoogle Scholar
28.Sims, C., Computation with finitely presented groups (Cambridge University Press, 1994).CrossRefGoogle Scholar
29.Todd, J. and Coxeter, H., ‘A practical method for enumerating cosets of a finite abstract group’, Proc. Edinburgh Math. Soc. 5 (1936) 26–34.CrossRefGoogle Scholar
30.Zeckzer, D., ‘Implementation, applications and complexity of prefix Gröbner bases in monoid and group rings’, Ph.D. thesis, University of Kaiserslautern, December 2000.Google Scholar