Date: Mar 24, 2013 7:48 PM Author: ross.finlayson@gmail.com Subject: Re: Matheology § 224 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.

https://en.wikipedia.org/wiki/Prefix_code

https://en.wikipedia.org/wiki/Huffman_coding

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.

Regards,

Ross Finlayson