<p>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.</p>
<p>In the edge-labelled framework, the empty tree is simply a root node with no edge, hence no label, and everything is naturally defined.</p>
<p>Unfortunately, we took the bad habit of labelling nodes instead of edges, artificially creating this kind of problem. We would like composition to be &quot;branch the marked leaves of the first tree to the root of the second one&quot;, 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.</p>
<p>Because of this, most works prefer to discard the empty tree, as it would be the source of unnecessary and cumbersome special cases.</p>
<p>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 <a href="https://antonio-casares.github.io/Publications/Casares23-PhDThesis.pdf" rel="noreferrer">Antonio Casares' PhD thesis</a> for argumentations on this.</p>

CC BY-SA 4.0
2024-05-10T14:05:56.720Z
2024-05-10T14:33:19.763Z
2024-05-10T14:33:19.763Z
Denis
<p>I've found the paper:</p>
<p>John Doner, &quot;Tree acceptors and some of their applications&quot;, Journal of Computer and System Sciences, Volume 4, Issue 5, 1970, Pages 406-451,</p>
<p>Which treats trees as associations of characters from an alphabet to prefix-closed sets of words, and includes mention of the empty tree, denoted <span class="math-container">$\Lambda$</span>.</p>

CC BY-SA 4.0
2024-05-20T19:14:24.660Z
2024-05-20T19:14:24.660Z
TomKern
<p>Are there references that consider the &quot;empty tree-word&quot; as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word?</p>
<p>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.</p>
<p>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-<span class="math-container">$\square$</span>-label replacement-concatenation with the empty tree <span class="math-container">$T \cdot_\square \varepsilon$</span> to simply remove leaves labeled with <span class="math-container">$\square$</span>s, as this makes several regular expressions much simpler. For instance, the set of all trees with nodes that just have the label <span class="math-container">$b$</span> can be described as:
<span class="math-container">$$\bigg(\varepsilon + b(\square, \square)\bigg)^{*,\square}\cdot_{\square} b$$</span></p>
<p>Versus</p>
<p><span class="math-container">$$\bigg(b(\square,) + b(,\square) + b(\square,\square)\bigg)^{*,\square} \cdot_{\square} b$$</span></p>
<p>where:</p>
<ul>
<li><span class="math-container">$b(\square,)$</span> is the 2-node tree with root labeled <span class="math-container">$b$</span> and left-child labeled <span class="math-container">$\square$</span>,</li>
<li><span class="math-container">$b(,\square)$</span> is its mirror,</li>
<li>and <span class="math-container">$b(\square,\square)$</span> is the 3-node tree with root labeled <span class="math-container">$b$</span>, and left and right child labeled <span class="math-container">$\square$</span>.</li>
</ul>
<p>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.</p>

<reference-request><automata-theory><regular-language><binary-trees>
The empty tree-word for regular tree languages
TomKern
# The empty tree-word for regular tree languages

(Asked by: username_0 on 2024-05-10)

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.

**Tags:** reference-request, automata-theory, regular-language, binary-trees


---

## 2 answers

### Answer by username_1 on 2024-05-10. Score: 6

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](https://antonio-casares.github.io/Publications/Casares23-PhDThesis.pdf) for argumentations on this.


---

### Answer by username_0 on 2024-05-20. Score: 0

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$.


---

