4
$\begingroup$

There are many ways of representing binary trees as strings. For example, I could encode a tree as either nil or a pair of trees, such as

(nil, ((nil, nil), nil))

This representation has a simple CFG:

S -> nil
S -> (S, S)

My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language. I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.

Does such a representation exist?

$\endgroup$
  • 1
    $\begingroup$ You have to be careful how to formulate this question. For example, there is a polynomial-time computable one-to-one mapping of all binary trees to the positive integers, and the positive integers (in binary) are certainly a regular language. $\endgroup$ – Peter Shor Jul 10 '11 at 14:22
  • $\begingroup$ @Peter Shor- I apologize if I'm missing something obvious, but what is this mapping? That's pretty much the answer to the question I'm asking. If this is a well-known result, is there a particular reference I should look up for more information? $\endgroup$ – templatetypedef Jul 10 '11 at 17:27
  • 3
    $\begingroup$ You can produce a regular language from any unique encoding of anything to a string. Simply take the lexicographic ordering of the encodings, and let $i$ represent the $i$th encoding in the ordering. This is what Peter meant when he said to be careful about the formulation. With trees, you can even do this in poly time. $\endgroup$ – Dave Jul 10 '11 at 21:36
  • 1
    $\begingroup$ @Peter Shor: There are non-complete trees which have the property that any node has either zero or two children, e.g. $N(N,N(N, N))$. According to Wikipedia, the property you mean is full. (Sorry for nitpicking, but it is of import if we are counting trees.) $\endgroup$ – Raphael Jul 11 '11 at 6:15
  • 1
    $\begingroup$ @Raphael: Indeed, I should have said full. $\endgroup$ – Peter Shor Jul 11 '11 at 10:33
9
$\begingroup$

As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.

On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have rational generating functions.

Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.

(Note that the generating function of arbitrary binary trees is not rational, either.)

$\endgroup$
  • 1
    $\begingroup$ Note that there might be some subtleties here as the number of trees with $n$ leaves need not be the number of encodings of length $n$, even for a valid encoding (due to encoding inner nodes, "management" symbols, ...). As rational functions are stable against coefficient shifts, constant factors and the like, I figure the implication remains valid. Also, the rational function you get for trees with $n$ nodes is not rational, either. $\endgroup$ – Raphael Jul 11 '11 at 6:47
  • $\begingroup$ Peter used the Catalan numbers to demonstrate a regular encoding of full binary trees. Whether the Catalan numbers are regular is no more relevant than whether he used a programming language with matched parentheses to demonstrate how to produce the encoding. $\endgroup$ – Dave Jul 11 '11 at 7:24
  • 1
    $\begingroup$ This would suggest that there is no regular language for the number of binary trees, but does this preclude a regular language for each individual binary tree? $\endgroup$ – templatetypedef Jul 11 '11 at 8:17
  • 1
    $\begingroup$ I think you both misunderstand. I prove that there is no regular language that has as many words of length $n$ as there are (full) binary trees with $n+1$ leaves (and other graph classes/ways of counting). Together with my first comment, I think this proves that there is no suitable regular, bijective encoding of binary trees. Of course, there are bijections between any infinite regular language and the set of all (full) trees as both sets are countable, but wether the resulting bijection is reasonable or even computable remains to be seen. $\endgroup$ – Raphael Jul 11 '11 at 15:48
  • $\begingroup$ By "suitable", I mean something like length blowup by management symbols by a constant factor or the like. Arbitrary bijections might do very weird things. $\endgroup$ – Raphael Jul 11 '11 at 15:49
3
$\begingroup$

Here is what I think is a legitimate encoding of binary trees as strings in $\Sigma^*$ (which is a regular language). Consider a breadth-first enumeration of the nodes in the infinite binary tree. Each node is labeled as a letter or as NIL. The nodes with letters belong to the tree, those labeled NIL do not. The caveat is that a subword of NIL's longer than the prefix preceding it terminates the tree -- meaning that this encoding is not a bijection. For example, the string abc00de encodes the 5-node tree

    a
   / \
  b   c
 / \ / \
0  0 d e

but the sequence a00bcde encodes the 1-node tree

    a
   / \
  0   0

(because 0/NIL cannot have children). Is this what you had in mind?

$\endgroup$
  • $\begingroup$ In my encoding, every string in $\Sigma^*$ encodes some binary tree -- and $\Sigma^*$ is a regular language. $\endgroup$ – Aryeh Jul 10 '11 at 16:42
  • 1
    $\begingroup$ Please give a formal definition of your encoding. $\endgroup$ – Raphael Jul 11 '11 at 6:34
  • $\begingroup$ Note how $a0b$ (and infinitely many more examples) does not encode a full binary tree. I do think, however, that you can interpret any string over $\Sigma \cup \{0\}$ as an unrestricted binary tree. $\endgroup$ – Raphael Jul 11 '11 at 7:08
  • $\begingroup$ indeed -- and I did not think that templatetypedef wanted full binary trees. I think I can prove that there can be no regular encoding of full binary trees; let me know if there is sufficient interest for me to go through the trouble. $\endgroup$ – Aryeh Jul 11 '11 at 10:52
  • $\begingroup$ The OP's grammar explicitly models full trees, so I figure he/she wants those. Salvaging your idea (which still has to be formalised, mind!), you can obtain a regular (non-bijective) encoding by using $(\Sigma^2 | 00)^*$, I guess. $\endgroup$ – Raphael Jul 11 '11 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.