TODO examples for the combinatorialist?
- Dominant language
- Haskell
- Stars
- 19
- Forks
- 3
- PR merge metrics
- No merged PRs in 30d
Description
I was hoping you could annotate the TODO with examples of what efficient implementations of Nominal Sets give you for the combinatorialist? I'm most curious if Nominal Sets reach the Holy Grail of cranking the exact combinatorial complexity of semigroup operations like Boolean matrix-matrix multiply.
When you iterate an element of the full transformation semigroup (functions on a finite set) you blow away things in the range then enter into a cycle. If you graph of the full transformation semigroup under iteration you get several connected components with a group-like center and trees feeding into them. You can partition the set for a given transformation by how things are blown away and eventually end up in cycles. Blog post I did a few years back with pictures: http://chadbrewbaker.github.io/combinatorics/transformations/permutations/2014/08/07/endo.html
Back when working on symmetries in lattice protein folding models I figured out an optimal black box algorithm using prime cycle decompositions to test non-trivial members of the symmetric group:
https://oeis.org/A186202
I submitted it for publication, but it was rejected by Laci Babai. Laci must have forgot about it, because he used the less efficient brute force enumeration in his Graph Isomorphism paper:
https://arxiv.org/pdf/1512.03547.pdf
JD Mitchell's library of finite semigroup algorithms: https://james-d-mitchell.github.io/libsemigroups/
Munro's paper on succinct transformation semigroup operations:
https://arxiv.org/pdf/1108.1983.pdf
Tell me if I am totally wrong, but it is my understanding that given two members of the full transformation semigroup say $h$ and $g$, efficent Nominal Sets help you use the set partition formed by iterating $h$, and the set partition formed by iterating $g$ so that you only have to crunch within partitions that overlap when doing operations that involve $h$ and $g$? You could then feed in a concrete finite semigroup and get exact bounds for the complexity of compute required to do a multiplication/composition in it?
Contributor guide
No contributing guide indexed for this repository
Research direction
Locate the TODO referenced in the issue, then read the surrounding Nominal Sets implementation and its existing documentation. Compare the requested examples and complexity claims with the linked semigroup references; done means the TODO contains accurate, repository-supported examples rather than unresolved speculation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- documentation
- Issue type
- Documentation
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 15/100