Semigroups
Semigroups copied to clipboard
Free band elements by graph representation
This PR adds some functions for creating and manipulating free band elements in a graph representation. This representation has benefits in comparison to the current tree based rep, and even a possible word based one.
- [ ] Actually describe what the structure and algorithms are
- [x] Come up with representation description
- [x] Make structure mutable
- [x] Allow reusing memory
- [x] Make the graph irredundant (each node represents a single free band element)
- [ ] Add methods to initialize
FreeBandElementByGraph- [x] Initialize from word
- [ ] Initialize from tree-rep
- [ ] Initialize from graph
- [ ] Multiplication
- [x] Multiply by single letter
- [ ] Figure out how to multiply two elements in graph-rep
- [x] Equality checking
- [x] Canonical word
- [x] Exponential canon. word
- [x] A shorter word-rep due to @tomcontileslie
- [x] Making a copy (to support immutable operations)
- [x] DotString for visualizing the structure
- [ ] Iterators (?)
- [ ] Collections of elements
- [ ] Reuse element code to make collection, redefine elements be specified by a collection and node in collection
- [ ] Write up a proof for certain results
- [ ]
V <= |A|*NwhereVis the number of vertices of the graph,Nis the length of the shortest word representation and|A|is the size of the alphabet - [ ] The right multiplication by letter algorithm is correct
- [ ] The canonical word algorithm actually produces the shortest possible word
- [ ]