> 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
> --
> 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 bacat@googlegroups.com. > To unsubscribe from this group, send email to > bacat+unsubscribe@googlegroups.com <bacat%2Bunsubscribe@googlegroups.com>. > For more options, visit this group at > http://groups.google.com/group/bacat?hl=en.
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.
> 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).
> 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
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?
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:
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).
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.
> 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:
> 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
> --
> 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 bacat@googlegroups.com. > To unsubscribe from this group, send email to > bacat+unsubscribe@googlegroups.com <bacat%2Bunsubscribe@googlegroups.com>. > For more options, visit this group at > http://groups.google.com/group/bacat?hl=en.
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?
> 2009/12/20 Jason Dusek <jason.du...@gmail.com> > 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:
> 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
> --
> 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 bacat@googlegroups.com. > To unsubscribe from this group, send email to bacat+unsubscribe@googlegroups.com > . > For more options, visit this group at http://groups.google.com/group/bacat?hl=en > .
> -- > Thanks, > -Vlad
> --
> 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 bacat@googlegroups.com. > To unsubscribe from this group, send email to bacat+unsubscribe@googlegroups.com > . > For more options, visit this group at http://groups.google.com/group/bacat?hl=en > .
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.
> 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
