The old Google Groups will be going away soon, but your browser is incompatible with the new version.
A rose bush by any other name...
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 11 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Dec 19 2009, 6:59 pm
From: Jason Dusek <jason.du...@gmail.com>
Date: Sat, 19 Dec 2009 15:59:12 -0800
Local: Sat, Dec 19 2009 6:59 pm
Subject: A rose bush by any other name...
Consider finite trees that have variable numbers of nodes --
"rose bushes" -- what distinguishes these trees from other
posets?

Is it that every subset of a such a tree has a supremum?

--
Jason Dusek

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 1:00 am
Date: Sat, 19 Dec 2009 22:00:26 -0800
Local: Sun, Dec 20 2009 1:00 am
Subject: Re: A rose bush by any other name...

a *tree* is a partially ordered
set<http://en.wikipedia.org/wiki/Partially_ordered_set> (poset)
(*T*, <) such that for each *t* ∈ *T*, the set {*s* ∈ *T* : *s* < *t*} is
well-ordered <http://en.wikipedia.org/wiki/Well-ordered> by the relation <
(wiki)

2009/12/19 Jason Dusek <jason.du...@gmail.com>

--
Thanks,

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 1:00 am
From: HeXXiiiZ <hexxi...@gmail.com>
Date: Sat, 19 Dec 2009 22:00:38 -0800
Local: Sun, Dec 20 2009 1:00 am
Subject: Re: A rose bush by any other name...

Trees in general, fixed or variably branching, are posets that have suprema
for any subset of nodes, but only infimums for sets of nodes that occupy a
chain. They are clearly omega-complete because every chain has a supremum
(moreover every subset). Trees are generally non-strict, but interestingly a
bottom element could simply be formed by connecting all leaves to an
element.

A more general poset can have non-trivial meets in it; branches can converge
downward in multiple ways. Furthermore, I think that trees, which can always
be ordered/graded in levels (traversals down from the root) satisfy such a
property occupied by certain but not all posets; generally, if there are two
paths upward to get from one node to another they do not necessarily have
the same number of steps. If graded somehow, posets can skip steps. Suppose
in a poset with elements A, B, C, D, and E, that   A < B, A < C, C < D, D <
E, and B < E. Since (B, C) and (B, D) are not ordered the grade of B cannot
be uniquely defined with respect to C and D. Does anybody know if there is a
name for this property, being graded or having levels?

One example that comes to mind is inheritance. In Java and similar languages
inheritances form rose bushes (sans interfaces/protocols etc...), but in C++
there are non-trivial meets in multiple inheritances. Furthermore, since C++
does not have an 'Object' class, two classes can inherit from the same pair
of classes which having no join and hence generally have no supremum.
Inheritance in OOP must enforce partial ordering so objects do not inherit
themselves.

Chris

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 4:17 am
From: Jason Dusek <jason.du...@gmail.com>
Date: Sun, 20 Dec 2009 01:17:04 -0800
Local: Sun, Dec 20 2009 4:17 am
Subject: Re: A rose bush by any other name...
2009/12/19 HeXXiiiZ <hexxi...@gmail.com>:

> Trees in general, fixed or variably branching, are posets that
> have suprema for any subset of nodes, but only infimums for sets
> of nodes that occupy a chain. They are clearly omega-complete
> because every chain has a supremum (moreover every subset).

Thanks for filling in a piece I was missing.

> Trees are generally non-strict...

Non-strict?

--
Jason Dusek

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 4:30 am
From: Mikael Vejdemo-Johansson <m...@stanford.edu>
Date: Sun, 20 Dec 2009 10:30:36 +0100
Local: Sun, Dec 20 2009 4:30 am
Subject: Re: [SPAM:#] Re: A rose bush by any other name...
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Dec 20, 2009, at 10:17 AM, Jason Dusek wrote:

> 2009/12/19 HeXXiiiZ <hexxi...@gmail.com>:
>> Trees in general, fixed or variably branching, are posets that
>> have suprema for any subset of nodes, but only infimums for sets
>> of nodes that occupy a chain. They are clearly omega-complete
>> because every chain has a supremum (moreover every subset).

>  Thanks for filling in a piece I was missing.

I don't think I get the connection trees <-> posets - are we viewing
the trees as rooted, root upwards, and as the Hasse diagrams of
themselves-as-posets?

In other words, with the 'standard' Haskell data type for rooted trees:
data Tree a = Leaf a | Node a [Tree]
do we consider a given (Node x subtrees) to be stating a covering
relation (smallest comparable) where x ≥ anything in the subtrees?

Mikael Vejdemo-Johansson, Dr.rer.nat
Postdoctoral researcher
m...@math.stanford.edu

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)

iEYEARECAAYFAkst7sMACgkQtUmpDMB8zM0t7wCfQITc5DTF10Qja6RDuOkhh5gt
v8MAn0/PKyPDyk1W9OQsCbizt7V7dKaY
=lzAm
-----END PGP SIGNATURE-----

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 11:44 am
From: Jason Dusek <jason.du...@gmail.com>
Date: Sun, 20 Dec 2009 08:44:34 -0800
Local: Sun, Dec 20 2009 11:44 am
Subject: Re: [SPAM:#] Re: A rose bush by any other name...
2009/12/20 Mikael Vejdemo-Johansson <m...@stanford.edu>:

> I don't think I get the connection trees <-> posets - are we
> viewing the trees as rooted, root upwards, and as the Hasse
> diagrams of themselves-as-posets?

> In other words, with the 'standard' Haskell data type for
> rooted trees:

> data Tree a = Leaf a | Node a [Tree]

> do we consider a given (Node x subtrees) to be stating a
> covering relation (smallest comparable) where x ≥ anything in
> the subtrees?

Yes.

--
Jason Dusek

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 5:05 pm
From: Jason Dusek <jason.du...@gmail.com>
Date: Sun, 20 Dec 2009 14:05:05 -0800
Local: Sun, Dec 20 2009 5:05 pm
Subject: Re: [SPAM:#] Re: A rose bush by any other name...
Of course, if you've got other ideas about how to approach a
category of trees and tree morphisms that would be great.

What I'm looking for is a way to characterize morphisms that
embed one tree in another in such a way that I can recover the
old tree. So we have morphisms in a category of trees and
tree morphisms:

embed : SmallerTree → LargerTree
unembed : LargerTree → SmallerTree

unembed ∘ embed = id

Oh, for a day when we can render TeX in our mail readers.

Allowing that the morphisms are all homomorphisms, the only way
we can get the inversion is if `embed` preserves all the
structure of `SmallerTree` and not a penny more. However, it
may be impossible to allow `unembed` in general; I'm not sure
how to do it. Maybe I need another category with weaker
constraints on the morphisms?

The application area is distributed version control; I'm
thinking about how to rename revisions when merging them in
from a foreign source (instead of using hashes for rev names).

--
Jason Dusek

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 20 2009, 11:07 pm
Date: Sun, 20 Dec 2009 20:07:10 -0800
Local: Sun, Dec 20 2009 11:07 pm
Subject: Re: [SPAM:#] Re: A rose bush by any other name...

When studying this, why do you focus specifically on trees? Try posets. What
does it take for a poset monomorphism to have a left inverse? I believe it
is enough if the arrow component has a left inverse; that can probably be
achieved if we assume the axiom of choice.

Have to check one more time, of course.

2009/12/20 Jason Dusek <jason.du...@gmail.com>

--
Thanks,

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 21 2009, 2:26 am
From: Mikael Vejdemo-Johansson <m...@stanford.edu>
Date: Mon, 21 Dec 2009 08:26:37 +0100
Local: Mon, Dec 21 2009 2:26 am
Subject: Re: A rose bush by any other name...
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

- -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Dec 21, 2009, at 5:07 AM, Vlad Patryshev wrote:

> When studying this, why do you focus specifically on trees? Try
> posets. What does it take for a poset monomorphism to have a left
> inverse? I believe it is enough if the arrow component has a left
> inverse; that can probably be achieved if we assume the axiom of
> choice.

> Have to check one more time, of course.

Vlad has a good point here. What you're trying to model, in DCVS-
world, is the relation 'revised from', right?

Now, you have a poset if you have a relation ≤ such that:
x ≤ x                        (no revision is a revision)
x ≤ y and y ≤ x => x = y     (revisions change stuff)
x ≤ y and y ≤ z => x ≤ z     (chain of revisions is a revision)

Instead of having a tree structure

r0 - r1 - r5
+ r2 - r6
|  +-- r3
+----- r4

say, you'd be talking about a poset where

r0 ≤ r1 ≤ r5
r0 ≤ r2 ≤ r6
r0 ≤ r2 ≤ r3
r0 ≤ r4

are the chains.

Benefit of changing your language? There's a body of work you can lean
on. For posets I like, very much, Stanley: Enumerative Combinatorics,
vol 1. (http://www-math.mit.edu/~rstan/ec/) though it may well be
slightly too fixated on combinatorial issues rather than computational
ones.

NOW the point Vlad has been making while I've been sleeping is that
once you've gone for the poset mental model, you can use poset
language to talk about morphism. What's a poset monomorphism? It's a
order-preserving injection of sets, it turns out. When does it split?
Once you start understanding the category of posets, what's the
coproduct? Is the coproduct enough, or do you need a bigger limit to
capture the things you want to do with your changesets?

// Mikael

- -----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)

iEYEARECAAYFAksvIwwACgkQtUmpDMB8zM0FHgCePXaQuBVP+728mJoMhbbALrku
b5QAni59rHyX/2iGiThOVtjvJ8sAmxLY
=Lpwn
- -----END PGP SIGNATURE-----
Mikael Vejdemo-Johansson, Dr.rer.nat
Postdoctoral researcher
m...@math.stanford.edu

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)

iEYEARECAAYFAksvIy4ACgkQtUmpDMB8zM1HYQCfUmwFpZDpEQDwV2XRlW6qCNqd
iPMAniLsZn6KnDhl/WF12yQrD5Fqv4cX
=Nvul
-----END PGP SIGNATURE-----

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2009, 4:29 pm
From: Jason Dusek <jason.du...@gmail.com>
Date: Mon, 28 Dec 2009 13:29:17 -0800
Local: Mon, Dec 28 2009 4:29 pm
Subject: Re: A rose bush by any other name...
2009/12/20 Mikael Vejdemo-Johansson <m...@stanford.edu>:

> On Dec 21, 2009, at 5:07 AM, Vlad Patryshev wrote:
> > When studying this, why do you focus specifically on trees?
> > Try posets. What does it take for a poset monomorphism to
> > have a left inverse? I believe it is enough if the arrow
> > component has a left inverse; that can probably be achieved
> > if we assume the axiom of choice.

> Vlad has a good point here. What you're trying to model, in
> DCVS- world, is the relation 'revised from', right?

Well, I think you guys are right when you say I can look at
posets for my morphisms.

However, trees have an important property: it's easy to make
tree data structures that are correct by construction; whereas
posets (DAGs) force you to do cycle checking. Why is that?
Well, adding an edge and adding a node are the same operation
in a tree; whereas in a poset, we can add nodes and then add
edges between them later. It's easy to make an API for adding
nodes/edges to a distributed tree that never introduces
cycles. (I've seen an ADT for correct DAGs with six
constructors but that paper is a little hard to follow.)

In a fully featured version control system we would actually
want posets, so as to model merges. However, that is not
relevant to the question of "What version is this diff
against?". It may be best to think of ≤ in this context as
"in-reply-to", like in mailing list archive browsers. The
well as queues of diffs; it is useful in engineering many
tools in distributed systems (distributed STM, replicated
message queues, &c.).

If I stick with a category of trees that is a full subcategory
of some category of posets then what I say about the poset
morphisms applies to the tree morphisms; but clearly trees
have other structure to them, like a distinguished root.

--
Jason Dusek

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2009, 6:51 pm
From: Mikael Vejdemo-Johansson <m...@stanford.edu>
Date: Tue, 29 Dec 2009 00:51:34 +0100
Local: Mon, Dec 28 2009 6:51 pm
Subject: Re: A rose bush by any other name...
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Dec 28, 2009, at 10:29 PM, Jason Dusek wrote:

Do note, first of all, that a poset is not obviously a DAG. They end
up being similar - especially in the sense that any DAG _generates_ a
poset - but they're not the same thing.

The main reason that trees are easy to make correct by construction,
whereas posets requires all sorts of checking is that trees don't
impose relations, while posets do. And equationally imposed relations
correspond, categorically, roughly to non-product limits (non-
coproduct colimits), and thus to things that require higher power from
your specification language to be able to formulate.

In the language of MATH198: a tree can be formulated as an algebra
over an endofunctor, whereas posets require more things than that. I
haven't checked, but I suspect it might be difficult to produce posets
as algebras even over monads - their structure is more than a kind of
associativity, and thus the monad doesn't provide enough structure.

>  In a fully featured version control system we would actually
>  want posets, so as to model merges. However, that is not
>  relevant to the question of "What version is this diff
>  against?". It may be best to think of ≤ in this context as
>  "in-reply-to", like in mailing list archive browsers. The
>  well as queues of diffs; it is useful in engineering many
>  tools in distributed systems (distributed STM, replicated
>  message queues, &c.).

>  If I stick with a category of trees that is a full subcategory
>  of some category of posets then what I say about the poset
>  morphisms applies to the tree morphisms; but clearly trees
>  have other structure to them, like a distinguished root.

A distinguished root in a tree corresponds, cleanly, to the beginnings
of a lattice structure for the poset: specifically the existence of a
global meet.

Mikael Vejdemo-Johansson, Dr.rer.nat
Postdoctoral researcher
m...@math.stanford.edu

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)

iEYEARECAAYFAks5RIwACgkQtUmpDMB8zM38OgCfTCRhe+/P0JRso8pfbRKgcDpV
/5EAniI1cNp6K6dcqSTmHCtnJWa9AycY
=Xfyr
-----END PGP SIGNATURE-----