LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Buckley, David John
Languages: English
Types: Doctoral thesis
Subjects: QA

Classified by OpenAIRE into

arxiv: Mathematics::Group Theory
This thesis describes a number of algorithms and properties relating to Gromov’s\ud word-hyperbolic groups. A fuller outline of the thesis is given, and a number of\ud basic concepts relating to metric spaces, hyperbolicity and automaticity are first\ud briefly detailed in Chapter 1. Chapter 2 then details a solution to the conjugacy\ud problem for lists of elements in a word-hyperbolic group which can be run in linear\ud time; this is an improvement on a quadratic time algorithm for lists which contain\ud an infinite order element. Chapter 3 provides a number of further results and\ud algorithms which build upon this result to efficiently solve problems relating to quasiconvex\ud subgroups of word-hyperbolic groups – specifically, the problem of testing\ud if an element conjugates into a quasiconvex subgroup, and testing equality of double\ud cosets. In Chapter 4, a number of properties of certain coset Cayley graphs are\ud studied, in particular showing that graph morphisms which preserve edge labels and\ud directions and map a quasiconvex subset to a single point also preserve a variety of\ud other properties, for instance hyperbolicity. Finally, Chapter 5 gives a proof that all\ud word-hyperbolic groups are 14-hyperbolic with respect to some generating set.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1 Introduction 1 1.1 A Note on Computational Complexity . . . . . . . . . . . . . . . . 3 1.2 Metric Spaces and Paths . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 X-graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 More about X-words . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Hyperbolicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6 FSAs, DFAs and Automatic Groups . . . . . . . . . . . . . . . . . 11 1.7 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
    • 2 The Conjugacy Problem for Lists 17 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 The Infinite Order Case . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.1 Results From [8] . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Finding Long Powers of Infinite Order Elements . . . . . . 25 2.3.3 Conjugating by a Power of a Short-lex Straight Word . . . . 31 2.3.4 Testing Conjugacy by Short-lex Straight Words . . . . . . . 38 2.3.5 Testing Conjugacy of A and B . . . . . . . . . . . . . . . . 41 2.4 Conjugacy of General Lists . . . . . . . . . . . . . . . . . . . . . . 44
    • 4 X-graphs and Hyperbolicity 81 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3 A Tighter Bound on the Thinness of Triangles . . . . . . . . . . . . 86 4.4 Ball Morphisms and Loops . . . . . . . . . . . . . . . . . . . . . . 96 4.5 IB(25δ) implies IB(∞) . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.6 Torsion-free Subgroups have GIB(∞) . . . . . . . . . . . . . . . . . 104 4.7 Geodesic Path Labels Under IB . . . . . . . . . . . . . . . . . . . . 106 4.8 Conclusion and Possible Further Work . . . . . . . . . . . . . . . . 107
    • [10] Z. Galil. Real-time algorithms for string-matching and palindrome recognition. In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 161-173. ACM New York, NY, USA, 1976.
    • [11] S.M. Gersten and H.B. Short. Rational subgroups of biautomatic groups. The Annals of Mathematics, 134(1):125-158, 1991.
    • [12] M. Gromov. Hyperbolic groups. Essays in group theory, 8:75-263, 1987.
    • [13] D.F. Holt. Word-hyperbolic groups have real-time word problem. International Journal of Algebra and Computation, 10(2):221-228, 2000.
    • [14] D.F. Holt, B. Eick, and E.A. O'Brien. Handbook of computational group theory. CRC Press, 2005.
    • [15] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article