The Compressed Word Problem for Groups |
|
Author:
| Lohrey, Markus |
Series title: | SpringerBriefs in Mathematics Ser. |
ISBN: | 978-1-4939-0748-9 |
Publication Date: | Apr 2014 |
Publisher: | Springer
|
Book Format: | Ebook |
List Price: | USD $54.99 |
Book Description:
|
The Compressed Word Problem for Groups provides a detailed exposition of known results on the compressed word problem, emphasizing efficient algorithms for the compressed word problem in various groups.nbsp;The authornbsp;presents the necessary background along with the most recent results on the compressed word problem to create a cohesive self-contained book accessible to computer scientists as well as mathematicians. Readers will quickly reach the frontier ofnbsp;current research...
More DescriptionThe Compressed Word Problem for Groups provides a detailed exposition of known results on the compressed word problem, emphasizing efficient algorithms for the compressed word problem in various groups.nbsp;The authornbsp;presents the necessary background along with the most recent results on the compressed word problem to create a cohesive self-contained book accessible to computer scientists as well as mathematicians. Readers will quickly reach the frontier ofnbsp;current research which makes the book especially appealing for students looking for a currently active research topic at thenbsp;intersection of group theory and computer science. The word problem introduced in 1910 by Max Dehnnbsp;is one of the most important decision problems in group theory. For many groups, highly efficient algorithms for the word problem exist. In recent years, a new technique based on data compression for providing more efficient algorithms for word problems, has been developed, by representing long words over group generators in a compressed form using a straight-line program. Algorithmic techniques used for manipulating compressed words has shown that the compressed word problem can be solved in polynomial time for a large class of groups such as free groups, graph groups and nilpotent groups. These results have important implications for algorithmic questions related to automorphism groups.