A rose bush by any other name...

[Jason Dusek]

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

[Vlad Patryshev]

a tree is a partially ordered set (poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <

(wiki)

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

--

You received this message because you are subscribed to the Google Groups "Bay Area Categories And Types" group.
To post to this group, send email to ba...@googlegroups.com.
To unsubscribe from this group, send email to bacat+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/bacat?hl=en.

--
Thanks,
-Vlad

[HeXXiiiZ]

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

[Jason Dusek]

2009/12/19 HeXXiiiZ <hexx...@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

[Mikael Vejdemo-Johansson]

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

On Dec 20, 2009, at 10:17 AM, Jason Dusek wrote:
> 2009/12/19 HeXXiiiZ <hexx...@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-----

[Jason Dusek]

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

[Jason Dusek]

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

[Vlad Patryshev]

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...@gmail.com>

--

You received this message because you are subscribed to the Google Groups "Bay Area Categories And Types" group.
To post to this group, send email to ba...@googlegroups.com.
To unsubscribe from this group, send email to bacat+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/bacat?hl=en.

--
Thanks,
-Vlad

[Mikael Vejdemo-Johansson]

-----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)

So, you could think about this being about posets rather than trees.
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-----

[Jason Dusek]

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
"in-reply-to" relation is helpful for queues of requests as
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

[Mikael Vejdemo-Johansson]

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

On Dec 28, 2009, at 10:29 PM, Jason Dusek wrote:
> 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.)
>

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
> "in-reply-to" relation is helpful for queues of requests as
> 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-----