On Wed, 22 Oct 2014, Nathann Cohen wrote:
given a Poset, how can you detect if this poset is a meet semilattice ?
For sure we need a function for that ! And it seems that this function
is exactly what join_matrix does.
Of course one can try to build a [semi]lattice and see if it works or not.
But is there some faster way? For a distributive lattice there is, see
http://www.lirmm.fr/~nourine/Papiers/dist-recognition.ps . It links to
http://download.springer.com/static/pdf/172/chp%253A10.1007%252F3-540-10854-8_14.pdf?auth66=1414046623_37fe0879bd09fb6dd923acdc2237f214&ext=.pdf
which says that detecting if a poset is lattice can be done on O(n^2.5).
My way of doing that (what would yours be?) to:
1) Have a FinitePoset.is_meet_semilattice() function that would try to
build that matrix and answer yes/no accordingly. The matrix, when built,
would be cached somewhere.
2) Move Poset.join_matrix() to FiniteMeetSemiLattice
The good thing is that if you:
a) Build a Poset
b) Notice it is a MeetSemiLattice by calling .is_meet_semilattice (which
builds the matrix)
c) Build the MeetSemiLattice from the poset
Then step c should not re-build the matrix as the matrix is currently a
lazy attribute of the hasse diagram, which has no reason to be changed
by those commands.
Yes. This way user can say somewhat more naturally
if P.is_lattice(): LatticePoset(P).do_something()
and not
try: L=LatticePoset(P)... except...
2) Would it be useful to have join() function taking more than two
arguments? And if so, should then also L.join(x) return x if x in L, and
maybe even L.join() return L.top()? Or could join take a list as argument,
so that both L.join(x,y) and L.join([x,y]) would work and latter one be
possible to extend to L.join([x,y,z,...])?
+1
Ok. To have join(a,b,c,...) or join([a,b,c,...])?
--
Jori Mäntysalo
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
