Search

In many studies of computation which make use of rooted labeled trees a partial ordering is usually imposed on the trees in the following way. A particular label, say $ \bot _0 $, is distinguished and identified with the atomic tree whose only vertex is a leaf labeled $ \bot _0 $. A tree f is then defined to be less than a tree A tree g if g can be obtained from f by attaching some new trees to leaves of f labeled $ \bot _0 $.This paper answers the following questions. What is the significance of the tree $ \bot _0 $ in this ordering? Can other nonatomic and perhaps infinite trees $ \bot $ be used to define a partial ordering on the trees in the same way? If so, what if anything distinguishes the partial ordering defined via the atomic tree $ \bot _0 $?