On Mar 24, 4:16 pm, Virgil <vir...@ligriv.com> wrote: > In article > <ab63154d-ab7e-4a03-be1b-17ac93226...@hd10g2000pbc.googlegroups.com>, > "Ross A. Finlayson" <ross.finlay...@gmail.com> wrote: > > > > > > > > > > > On Mar 24, 2:51 pm, fom <fomJ...@nyms.net> wrote: > > > On 3/24/2013 4:34 PM, WM wrote: > > > > > On 24 Mrz., 21:29, Virgil <vir...@ligriv.com> wrote: > > > >> In article > > > >> <729f073f-8948-4eb9-991a-2bd249ac5...@c6g2000yqh.googlegroups.com>, > > > > >> A binary tree that contains one path of each positive natural number > > > >> length will necessarily also contain exactly one path of infinite length. > > > > > Like the sequence > > > > 0.1 > > > > 0.11 > > > > 0.111 > > > > ... > > > > that necessarily also contains its limit? > > > A binary tree that contains one path, of all zero-branches, of each > > finite length, will necessarily contain a path of 0-branches of > > infinite length. > > Better is > > root > | \ > 0 1 > | \ > 0 1 > | \ > 0 1 > | \ > 0 1 > | \ > 0 1 > | \ > 0 1 > | \ > 0 1 > | \ > > And so on > > --
A binary tree, of all 0's or 1's (0- or 1- branches) with paths of each finite length, has a path of infinite length: that is a subtree of the intersection[*], of the finite paths. A tree with paths of each length n having 0's except the last 1 shows a binary tree with an infinite path: that is a subtree of the union of the finite paths. As a space-complexity problem it's simpler to maintain the intersection[*] than the union.
* [ To be sure, to well-define intersection (i.e. to keep it true), it is as the union where the existence of a disjoint leaves the result undefined. Basically this of the difference among unary and infinitary, and binary and n-ary.]
Basically in entropy coding and Huffman coding there are codes with the prefix property that codes of arbitrary width can be put into a sequence and demarcated courtesy the prefix property. Then, an idea is that with paths as codes with the prefix property and distinct length, there would be in the tree a path of each finite length, but that paths of greater length would have a different prefix than each preceding path.
Then, where Huffman coding is to find the largest alphabet with the prefix property with the least average length of the path, here the idea for dense bounded tree coding is to find an alphabet with the prefix property with one code for each length: with the maximum suffix of the path that is disjoint the other code's paths, that each pair is mutually disjoint.
Basically this is about codes with the prefix property (that there would be a branch from lesser length codes, and the next), the palindrome property, or otherwise with the prefix property, and that the suffix was not following the suffix of another code initial segment, in reverse as it were. Basically it is that the reverse of the code of length n as path, would have the prefix property, to the initial segment of length n of any code of greater length.
Then, saying that there would always be an infinite path in the union of paths of each finite length of the binary tree is that there is no "dense bounded" coding as here. Basically that is a question of what are the most paths and most lengths (and as to complexity and entropy) there can be with the least amount of infinite paths.
Here, again, the intersection[*] of the 0-paths is infinite, the union of the 0*1-paths has a subtree that is infinite, a distinct difference: the least number of finite paths, with an infinite path.
There is a difference among representations, of unary, infinitary, binary, and n-ary (in spaces), structural difference with concomitantly various results, as of their variety.