Back to Search Start Over

Compatible Orderings on the Metric Theory of Trees

Authors :
Ralph Tindell
Stephen L. Bloom
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