5
$\begingroup$

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word?

The sources I've looked into seem to not allow it, which makes sense in the context of ranked alphabets, but even Downey and Fellows, which considers arbitrary labelings of finite rooted trees with bounded fanin, does not seem to allow it.

I'm looking into regular expressions for regular tree-languages consisting of labeled binary rooted tree (every node is either a left-child or a right-child), and it is very tempting to define the leaf-with-a-$\square$-label replacement-concatenation with the empty tree $T \cdot_\square \varepsilon$ to simply remove leaves labeled with $\square$s, as this makes several regular expressions much simpler. For instance, the set of all trees with nodes that just have the label $b$ can be described as: $$\bigg(\varepsilon + b(\square, \square)\bigg)^{*,\square}\cdot_{\square} b$$

Versus

$$\bigg(b(\square,) + b(,\square) + b(\square,\square)\bigg)^{*,\square} \cdot_{\square} b$$

where:

  • $b(\square,)$ is the 2-node tree with root labeled $b$ and left-child labeled $\square$,
  • $b(,\square)$ is its mirror,
  • and $b(\square,\square)$ is the 3-node tree with root labeled $b$, and left and right child labeled $\square$.

My primary interest in regular languages of these sorts of trees is to set up for the equivalence with WS2S, and I suspect this is also a situation where the empty tree makes sense.

$\endgroup$

2 Answers 2

5
$\begingroup$

I believe this is one of the many cases where it becomes clear that labelling nodes is a bad choice, and we should be labelling edges instead.

In the edge-labelled framework, the empty tree is simply a root node with no edge, hence no label, and everything is naturally defined.

Unfortunately, we took the bad habit of labelling nodes instead of edges, artificially creating this kind of problem. We would like composition to be "branch the marked leaves of the first tree to the root of the second one", so you need a root of the second tree even when it's empty, but you don't want to be forced to label this root.

Because of this, most works prefer to discard the empty tree, as it would be the source of unnecessary and cumbersome special cases.

Same goes for acceptance conditions of automata on infinite structures (typically infinite words and trees), they are historically put on states although they should be put on transitions. See section VI of Antonio Casares' PhD thesis for argumentations on this.

$\endgroup$
0
$\begingroup$

I've found the paper:

John Doner, "Tree acceptors and some of their applications", Journal of Computer and System Sciences, Volume 4, Issue 5, 1970, Pages 406-451,

Which treats trees as associations of characters from an alphabet to prefix-closed sets of words, and includes mention of the empty tree, denoted $\Lambda$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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