
arXiv: 1706.08188
Lists of equivalence classes of words under rotation or rotation plus reversal (i.e., necklaces and bracelets) have many uses, and efficient algorithms for generating these lists exist. In combinatorial group theory elements of a group are typically written as words in the generators and their inverses, and necklaces and bracelets correspond to conjugacy classes and relators respectively. We present algorithms to generate lists of freely and cyclically reduced necklaces and bracelets in free groups. Experimental evidence suggests that these algorithms are CAT -- that is, they run in constant amortized time.
Reduced word, Conjugacy class, Free group, CAT algorithm, 2604 Applied Mathematics, Necklace, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Bracelet, 2605 Computational Mathematics, 2602 Algebra and Number Theory
Reduced word, Conjugacy class, Free group, CAT algorithm, 2604 Applied Mathematics, Necklace, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Bracelet, 2605 Computational Mathematics, 2602 Algebra and Number Theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
