0
$\begingroup$

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the following finite tree:

        f       /  \      a    g          / \         b   c 

Rational trees are now the terms that emerge when we look at a diagram as above and drop the restriction that it must be a finite tree. So if we allow graphs. Here is an example of a rational tree:

       _       / \      /   s     /   / \    /   s   0    \_/  \          1 

Since its possible to lexically order finite trees, can we also put rational trees into a strict total order? What is a natural one that is closest to the lexical order?

Best Regards

P.S.: The above rational tree is a counter example that shows that a lexical order is not always possible, communicated by Mats Carlsson. Take A=s(B,0), B=s(A,1), then the assumption AA, and vice versa.

  • 0
    Yes, roots are important. T = s(s(T,1),0) is not the same as S = s(s(S,0),1).2012-10-10

1 Answers 1

1

Since lexicographic order is looking for a difference with a depth-first search (which can look arbitrarily far down one branch without going into any of the others), why not look for a difference with a breadth-first search ?

More precisely, define $A_n$, the $n$th truncation of a term $A$ as only the first $(n+1)$ levels in the tree. On your counterexample with $A = s(s(A,1),0)$, the $0$th truncation of $A$ is $s$, the $1$st truncation is $s(s,0)$, then $s(s(s,1),0)$ etc. Put any orders $<_n$ you want on the sets of $n$ levelled trees (for example, lexicographical), then define $A' = (A_0,A_1,A_2,\ldots)$ and define the order by $A < B \iff A' <_{lex} B' \iff \exists n. (\forall m. m

If $A$ and $B$ are the same at every level, I think you would agree that they are the same trees, so this order is total, and transitivity follows from that of $<_{lex}$ and $<_n$

  • 1
    If two trees are distincts then there is a level that distinguishes them, and so you don't need to look infinitely far down the tree to decide how they are ordered. You just need to check level after level until you find the difference. So it boils down to deciding equality among rational trees2012-10-12