Breadth-first search and the Andrews-Curtis conjecture

Havas, G. and Ramsay, C. (2003) Breadth-first search and the Andrews-Curtis conjecture. International Journal of Algebra And Computation, 13 1: 61-68. doi:10.1142/S0218196703001365

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Havas, G.
Ramsay, C.
Title Breadth-first search and the Andrews-Curtis conjecture
Journal name International Journal of Algebra And Computation   Check publisher's open access policy
ISSN 0218-1967
Publication date 2003-01-01
Sub-type Article (original research)
DOI 10.1142/S0218196703001365
Open Access Status Not yet assessed
Volume 13
Issue 1
Start page 61
End page 68
Total pages 8
Editor J. Rhodes
Place of publication Singapore
Publisher World Scientific
Language eng
Subject C1
280405 Discrete Mathematics
780101 Mathematical sciences
Abstract Andrews and Curtis conjectured in 1965 that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Recent computational work by Miasnikov and Myasnikov on this problem has been based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample.
Keyword Mathematics
Andrews-curtis Conjecture
Trivial Group
Group Presentations
Computer Generated Proofs
Balanced Presentations
Trivial Group
Q-Index Code C1

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 8 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 9 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 15 Aug 2007, 11:57:18 EST