FrontPage SiteMap RecentChanges HowTo Blog

Matching Pages:

RSS

TreeVsSemiLattice

in french: ArbreVsSemiTreillis


Here is a diagram to illustrate the difference between a tree and a semi-lattice. (See PlanetMath:tree and PlanetMath:semilattice for a more formal discussion.)

            TREE                         SEMI LATTICE

	     |				      |		 
	 +---+----+		      +-------+----+	 
     V 	 | W   	X |    Y	  V   |	   W  X	   |  Y	 
     +---+-+    +-+----+	  +---+----+  +----+--+	 
     |     |   	|      |	  |    	   |  |	      |	 
   +-+-+ +-++  ++--+ +-+--+  	+-++-+   +-+-++-+  +--+-+
   |   | |  |  |   | |	  |	|  | |   |   |	|  |	|
   A   B C  D  E   F G    H     A  B C   D   E  F  G    H

The important thing to notice is that in a tree, nodes have only one parent. In a semi-lattice, there can be more. In the diagram, the nodes D, E, and F have more than one parent.

The real-life application of this is illustrated in Christopher Alexander’s essay A City is Not a Tree [1]: Think of the bottom nodes (the leaves) as individual houses, and the nodes further up would represent “local centers”: shopping centers, schools, public libraries. If a city were organized like a tree, then people in houses A and B would use the same shopping center (V) and the same school (W). Christopher Alexander argues this is not the case: Much like houses D, E, and F in the semi-lattice, they some will choose this school (V), some will choose another (X). Similarly, some will go shopping here (W), some there (Y).


Your diagram confuses me a little. In the semi-lattice, what are the “parents” representing? I assume the common ground (technically, the intersection) between their children? – ChrisPurcell

Better now? :)AlexSchroeder


christopher alexander does not speak against the tree structure, his semi-lattices also consist of trees. he speaks against the one-sided, forcible use (misuse) of the tree structur in urban planning.
i’ll assemble a few excerpts i’ve found:
It’s a very illuminating book I think, but it doesn’t really put generative power in people’s hands. Without the help of architects or planners, hundreds of people together can create a town, which is alive and vibrant, peaceful and relaxed, a town as beautiful as any town in history.if you are working in the timeless way, the idea is that a town will grow under your hands, as naturally as the flowers in your garden.
but how can we do it? not alone through a FOAF structure, but instead through cooperation with our wiki tree as the reversal of the hierarchy. --sigi


Parents don’t represent the intersection between sets- those things actually appear lower on the semilattice.

The parents represent the supersets.

Drawn like a tree:

      ABCDEFGHIJ
        /    \
    ABCDEF  EFGHIJ
         \  /
          EF

Drawn like sets:

			@@@@@@@@@@@
	    @@@@@@@@@@@@@@@@@	   @@@@
	 @@@		       	       @@@@
       @@@		       	       	  @@@@@@
     @@@	@@@@@@@@@@@@			@@@@@
    @@	     @@@	   @@@			    @
   @@	    @@		      @			     @@@
   @	    @	ABCDEF	       @@   @@@@	    	@ @
   @	    @	      	    @@@@@@ @	@@ @@@	    	   @
   @	    @	       	 @@@   	@@	       @@@@@	    @@@
   @	     @@	       	@@	 @@		   @@@	       @@
   @	      @@       	@  	  @		      @@	 @@
   @		@@@    @@   EF	  @		       @	  @@
   @		   @@@@@     	  @		       @	   @
   @		     @@@@@@  	@@@		    	@	    @
   @		    @@	   @@@@@@		    	@	    @
   @		  @@	      			       @	    @
    @		  @	       	  EFGHIJ	      @@	    @
    @@		  @@				     @@		    @
     @		   @@				  @@@		    @
     @		    @@@@		       @@@  		   @@
      @			@ @@@	     @@@ @@@@@@	    		  @@
       @		     @@@@@@@@@		    		 @@
	@@					    		@@
	 @@					    	       @@
	   @@					    	      @
	     @@@@			ABCDEFGHIJ  	    @@
		 @@@@@@					 @@@
		      @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

At the top of the page, we have divorce attorney

                                              |
                                      +-------+----+
                                  V   |    W  X    |  Y
                                  +---+----+  +----+--+
                                  |        |  |       |
                                +-++-+   +-+-++-+  +--+-+
                                |  | |   |   |  |  |    |
                                A  B C   D   E  F  G    H

Which can be drawn as sets like so:

                       @@@@@@@@@@@@@@@@@@@@@@@
                  @@@@@@                      @@@@@@@@@@
                @@                                     @@@@@
                @                                          @@@@
             @@@                                              @@
        @@@ @@                                    Y             @@
       @@                                                         @
      @@               X               @@@@@@@@@@@@@@@@@@@@@@@     @@
     @@                               @@                     @@     @@
     @       @@@@@@@@@@@@@@@       @@@                        @@@    @
    @@      @@             @@@@@@ @@                            @@    @
    @      @@                   @@@@@                            @    @
    @      @                     @  @@@@@@                       @@    @
    @      @      (A)            @       @@@@          (H)        @     @
    @      @                     @  Z       @@                    @     @
    @      @@        (B)         @            @  (G)              @      @
     @      @@                   @       (E)  @                   @
     @@      @@          (C)     @  (D)        @                  @       @
      @       @@@                @          (F) @                @@       @
       @         @@              @@             @                @        @
        @@         @@@             @@           @                @        @
         @@@         @@@@@@@        @@@       @@@              @@        @@
           @@              @@@@@@@@@@@@@@@@@@@@              @@@         @
             @@                         @@@@@@            @@@@          @@
               @@                            @@@@@@@@@@@@@@            @@
                 @@                                                  @@@
                   @@@                                              @@
                      @@@                                       @@@@
                         @@@@@                              @@@@
                             @@@@ @ @ @@@          @@@ @@@@@
                                         @@@@@@@@@@

Which we can turn back into tree shapes…

            U                           ABCDEFGH
           / \     ...or perhaps         /   \
          X   Y         even...      ABCDEF   DEFGH
         / \ / \                     /   \   /   \
        /   Z   \                 A,B,C   DEF    G,H
       /    |    \                         |
   A,B,C  D,E,F  G,H                     D,E,F     ...which I prefer.

Now: why in the world are we having this discussion?

As far as I can tell, Christopher Alexander made a mistake in drawing attention to the notion of a SemiLattice?. (Is he infalliable?)

ChristopherAlexander is saying that if you district places in a city as “residential” or “industrial” or “commercial,” then you get all sorts of crazy effects. You get things like tax dollars coming in from one place (that can’t use it) and few tax dollars from other places (that really need them,) and no ability to commincate between the two of them. He’s saying that we need to think about our cities organically, and to organize our institutions to work like that.

You don’t need the word “semilattice” to say it, I feel.

I don’t see what the word “semilattice” has bought us, beyond confusion.

LionKimbro

why the grumbling, and the exasperated “why in the world”? is there suddenly something wrong with having a conversation? if you don’t care to talk about trees vs semi-lattices, then don’t, ok?

i find the distinction incredibly useful because it shows to me why so many attempts to create vibrant communities fail. beyond that i think christopher alexander points out the dangers of over-simplification, and of forcing a one-size-fits all solution across a complex domain. since that’s a hobby horse of mine, of course i’ll like talking about it.

heh. :)

If it’s just “Trees vs. Semi-Lattices” in the abstract, that’s fine by me. I can start writing about how the Semi-Lattice conditions are similar to set-based Topology descriptions. Great.

I just don’t like “Semi-Lattices” in the conversation about the growth of wikis and cities, because it’s not helping. We don’t need “Semi-Lattice” to talk about the dangers of over-simplification, or PlatonicCategories.

I mean, look at the dialog at the top of the page. Yeech.

This is all my fault…

Actually, no… I’m in the wrong; I’m being too forceful.

I’m just on a PlainTalk kick right now. Maybe been reading too many W3C documents or something like that.

I do believe that we (and that’s a pretty big “we”- I mean pretty much the entire Internet society that I interact with) need to focus on PlainTalk.

I just need to be less forceful when complaining about it.

 ***   alex & chris
   * & lion & pir
     & sigi
  ** → language:sprache ; develop:entwickeln

you can derive PlainTalk from semi-lattice if you introduce connection symbols everyone understands. these connection symbols form a logical system that can be handeled by a computer, thus we can solve all our technical wiki problems. --sigi

lion – maybe you’ll just need to talk even plainer, snicker. it didn’t occur to me that you were bothered by the word “semi-lattice” itself, rather than the concept. i’m with you regarding plain talk in general. however, i don’t think i want to completely separate it from specialized language – i envision instead an introduction for a concept in plain talk, and then at the end a section where more specialized terms are named funny quotes, so people acquire new vocabulary with which to search for further information. woops. this last part should probably mosey on over to PlainTalk.

The sounds “semi-lattice” don’t bother me. The meaning of the word “semi-lattice” doesn’t bother me. The existence of advanced mathematics doesn’t bother me.

What bothers me, is that this word is completely unnecessary for our conversations.

What have we bought with this word? Only confusion.

I’ve been heavy handed in saying this, and I shouldn’t have been. But the point remains.

We can carry the rest of the conversation on PlainTalk; I’ll copy your text to over there in a moment.

Perhaps surprisingly, I agree with Lion

By the way, the definition of semilattice in A CITY IS NOT A TREE appears to be wrong. If the semilattice operation is set intersection, then the empty set has to be included (because the (lower) semilattice condition applied to a set of sets says that the greatest lower bound for any two sets, which is the set intersection, has to itself be in the set of sets).

Alexander’s axiom:

A collection of sets forms a semilattice if and only if, when two overlapping sets belong to the collection, the set of elements common to both also belongs to the collection.

would not require the empty set to be in the collection. The word “overlapping” should be dropped.

I thought this was a minor mistake but a mathematician/professor I know thought it was serious enough to render the connection to the mathematical idea of “semilattice” nonsensical.

In addition, it should be noted that (as far as I can tell) Alexander’s statement of the axiom only includes some things that would mathematically be called semilattices – it is a special case of the usual definition (although this “special case” is what I think of as a canonical example of “semilattice”; it captures the feel of it pretty well, I think).

For similar reasons I think this diagram from above is not a semilattice:

                                              T
                                              |
                                      +-------+----+
                                  V   |    W  X    |  Y
                                  +---+----+  +----+--+
                                  |        |  |       |
                                +-++-+   +-+-++-+  +--+-+
                                |  | |   |   |  |  |    |
                                A  B C   D   E  F  G    H

but this one from above is:

            U    
           / \     
          X   Y        
         / \ / \     
        /   Z   \        
       /    |    \           
   A,B,C  D,E,F  G,H         

why? well, to be a semilattice you must be either an upper or a lower semilattice. A lower semilattice says that any two nodes have a greatest lower bound. This is certainly not true for either of these diagrams, because the any pair of the nodes at the bottom doesn’t have a lower bound at all.

An upper semilattice has to have a least upper bound for any two nodes. So, in the top diagram, what is the least upper bound of D and E? They don’t have one. Their upper bounds are {W,X,T}; but none of these is less than or equal to the rest.


As far as I can see this topic is also related to http://www.oddmuse.org/cgi-bin/wiki/Hierarchic_Linking_Module_Proposal as one node can have also more than one parent. --TonyArmani

To me it seems to be s t r o n g l y related.


CategoryHierarchy funny jokeshilarious quotes dental implants

Define external redirect: SemiLattice

EditNearLinks: ChristopherAlexander

Languages: