Press "Enter" to skip to content

Algorithms and Classification in Combinatorial Group Theory by Charles F. Miller III (auth.), Gilbert Baumslag, Charles F.

By Charles F. Miller III (auth.), Gilbert Baumslag, Charles F. Miller III (eds.)

The papers during this quantity are the results of a workshop held in January 1989 on the Mathematical Sciences study Institute. issues lined contain selection difficulties, finitely offered easy teams, combinatorial geometry and homology, and automated teams and comparable subject matters.

Show description

Read or Download Algorithms and Classification in Combinatorial Group Theory PDF

Similar algorithms books

The Nature of Code

How will we catch the unpredictable evolutionary and emergent houses of nature in software program? How can realizing the mathematical rules at the back of our actual global support us to create electronic worlds? This ebook specializes in a variety of programming techniques and methods in the back of laptop simulations of typical structures, from undemanding strategies in arithmetic and physics to extra complex algorithms that let subtle visible effects.

Creating New Medical Ontologies for Image Annotation: A Case Study

Growing New scientific Ontologies for photo Annotation makes a speciality of the matter of the scientific photographs automated annotation technique, that's solved in an unique demeanour via the authors. all of the steps of this method are defined intimately with algorithms, experiments and effects. the unique algorithms proposed by means of authors are in comparison with different effective comparable algorithms.

Algorithms and Models for the Web-Graph: 7th International Workshop, WAW 2010, Stanford, CA, USA, December 13-14, 2010. Proceedings

This ebook constitutes the refereed complaints of the seventh foreign Workshop on Algorithms and versions for the Web-Graph, WAW 2010, held in Stanford, CA, united states, in December 2010, which used to be co-located with the sixth overseas Workshop on web and community Economics (WINE 2010). The thirteen revised complete papers and the invited paper awarded have been rigorously reviewed and chosen from 19 submissions.

Additional resources for Algorithms and Classification in Combinatorial Group Theory

Sample text

Since the word problem for U is unsolvable, it follows that the conjugacy problem for G is unsolvable. In one direction this claim is easy. For observe that U is the homomorphic image of G obtained by mapping each 8i in G to the corresponding 8i in U and mapping all other generators to the identity lu. Denote this homomorphism by ¢. Then if y-1qwy =c q it follows that ¢(y)-l w¢(y) =u 1 and hence w =u 1. For the converse, suppose w =u 1. Then r W =u II X k (8i)-1 Rj~Xk(8i) k=l for suitable words X k in the given generators.

For since G is finitely generated, the entries in its matrices all lie in some finitely generated commutative ring. Now the arithmetic of such a ring is effective and hence such a group has solvable word problem (see [11]). In the group 8L(2, Z) the two matrices (~ i) and (; ~) freely generate a free subgroup of rank 2. Moreover, Sanov [93] has shown that an arbirtary 2 x 2 matrix with integer entries belongs to this subgroup if and only if the following three arithmetic conditions are satisfied: (1) ad - be = 1 (2) a and d are congruent to 1 mod 4 (3) e and b are even.

Then Dehn's conjugacy algorithm solves the conjugacy problem for G. Thus Dehn's algorithm for the word problem always implies that Dehn's conjugacy algorithm solves the conjugacy problem. In terms of R-diagrams this means the following: if the number of regions in a R-diagram which is a disk is bounded by a linear function of the length of the boundary, then the same is true of annular R-diagrams. F. Miller Automatic groups: The notion of an automatic group was introduced in [26]. Another reference is [17].

Download PDF sample

Rated 4.05 of 5 – based on 13 votes