OKlibrary  0.2.1.6
Groupoids.hpp File Reference

Plans related to the search for (certain) groupoids. More...

Go to the source code of this file.


Detailed Description

Plans related to the search for (certain) groupoids.

Todo:
Encodings
  • For a natural number n, the groupoid structures on {1,...,n} are captured by the n^2 variables c_{i,j}, i,j in {1,...,n} with value-domains {1,...,n} (the value of c_{i,j} is the composition of i and j). The two most basic constraints are:
    • Commutativity: c_{i,j} = c_{j,i} (for i <> j). Are there interesting active clause-sets? Seems to be completely straight-forward, and only a question of appropriate data structures.
    • Associativity: Much less straight-forward, and active-clause-sets could be very interesting.
Todo:
Quasigroups
Todo:
Literature surview
  • We need overview on the literature.
  • Searching for interesting problems.
  • Searching for interesting algorithms.
Todo:
Discrete groupoids
  • I (OK) call a groupoid discrete if x * y in {x,y} is always the case (are there notions for that in the literature?). Discrete groupoids are idempotent, and can be represented by n^2 - n many boolean variables (for each pair (i,j) with (i,j) the variables states whether the composition is i or j).
  • Are there interesting problems?
    • For a start, one could just search for non-commutative discrete semigroups (while the commutative discrete semigroups correspond 1-1 to the linear orders on the ground set --- composition is min (or max)).
    • Stronger would be to count all discrete semigroups (on {1,...,n}). For that we need the active clause-set for associativity from above to work with these special variables.

Definition in file Groupoids.hpp.