Semigroups icon indicating copy to clipboard operation
Semigroups copied to clipboard

Free band elements by graph representation

Open reiniscirpons opened this issue 5 years ago • 0 comments

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|*N where V is the number of vertices of the graph, N is 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

reiniscirpons avatar Jul 07 '20 17:07 reiniscirpons