Back to Search
Start Over
Compatible Orderings on the Metric Theory of Trees
- Source :
- SIAM Journal on Computing. 9:683-691
- Publication Year :
- 1980
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 1980.
-
Abstract
- 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 $?
Details
- ISSN :
- 10957111 and 00975397
- Volume :
- 9
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Computing
- Accession number :
- edsair.doi...........53656c42971845b1d0f8900e7d0f6e89