<p>You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.</p>

CC BY-SA 3.0
2018-04-21T01:39:03.240Z
2018-04-21T01:39:03.240Z
user53151
<p>Recently I have some dispute with my colleagues and would like to clarify the following question.</p>

<p>It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each symbol in their finite alphabets (terminals and non-terminals resp.) has an <em>arity</em> or "<em>rank</em>", which specifies number of possible children. So for terminals it is always "0", while for non-terminals it is always $\geq 1$.</p>

<p>But what should we consider by "<strong>unranked</strong>" trees?</p>

<p>In my understanding, as some papers state (I don't have references right now), an unranked tree is produced by a tree grammar where there are no restrictions on the rank for non-terminals. I.e. alphabets are not ranked anymore. And that's all (I don't want to go deeper into the formal details and definitions). </p>

<p>Basically in my understanding, each XML document is generally an unranked tree. </p>

<p>So what my colleague states, is that the "<em>unrankness</em>" necessary implies a kind of "unboundness" of children inside each node. In other words, if a tree grammar specifies a certain <strong>finite</strong> set of "ranks" for each non-terminal, then trees produced by such a grammar are <strong>not</strong> <em>unranked</em>. </p>

<p>The difference between my understanding and my opponent's one, is that my definition seems to be more soft and general. So I can say that any XML document is an example of an unranked tree. My colleague's definition restricts it, so not each XML document will be unranked, but only that satisfying an XSD schema which contains some unbounded lists.</p>

<p>So, who is right?</p>

CC BY-SA 4.0
2018-05-21T16:10:16.077Z
This is my bias opinion on the matter. Consider a set of vertex labelled trees. If for every label $l$, each vertex with label $l$ from any tree has the same number of children, then I propose that we call them ranked trees. If for some label $l$, there exist trees $t_1$ and $t_2$ where $t_1$ contains a vertex labelled $l$ with $c_1$ children and $t_2$ contains a vertex labelled $l$ with $c_2$ children where $c_1 \neq c_2$, then I propose that we call them unranked trees.
Michael Wehar
CC BY-SA 4.0
2018-05-21T16:10:43.500Z
If they are unranked trees, but every vertex has a bounded number of children, then I propose that we call them bounded degree unranked trees.
Michael Wehar
CC BY-SA 4.0
2018-05-21T16:10:49.397Z
If they are unranked trees, but every tree is finite, then I propose that we call them finite unranked trees. You could naturally combine these two concepts to define bounded degree finite unranked trees.
Michael Wehar
<tree><definitions>
What are "unranked trees"?
Andrey Lebedev
# What are "unranked trees"?

(Asked by: username_0 on 2018-04-18)

Recently I have some dispute with my colleagues and would like to clarify the following question.

It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each symbol in their finite alphabets (terminals and non-terminals resp.) has an *arity* or "*rank*", which specifies number of possible children. So for terminals it is always "0", while for non-terminals it is always $\geq 1$.

But what should we consider by "**unranked**" trees?

In my understanding, as some papers state (I don't have references right now), an unranked tree is produced by a tree grammar where there are no restrictions on the rank for non-terminals. I.e. alphabets are not ranked anymore. And that's all (I don't want to go deeper into the formal details and definitions).

Basically in my understanding, each XML document is generally an unranked tree.

So what my colleague states, is that the "*unrankness*" necessary implies a kind of "unboundness" of children inside each node. In other words, if a tree grammar specifies a certain **finite** set of "ranks" for each non-terminal, then trees produced by such a grammar are **not** *unranked*.

The difference between my understanding and my opponent's one, is that my definition seems to be more soft and general. So I can say that any XML document is an example of an unranked tree. My colleague's definition restricts it, so not each XML document will be unranked, but only that satisfying an XSD schema which contains some unbounded lists.

So, who is right?

**Tags:** tree, definitions

> **Comments:**
> **username_1**: This is my bias opinion on the matter. Consider a set of vertex labelled trees. If for every label $l$, each vertex with label $l$ from any tree has the same number of children, then I propose that we call them ranked trees. If for some label $l$, there exist trees $t_1$ and $t_2$ where $t_1$ contains a vertex labelled $l$ with $c_1$ children and $t_2$ contains a vertex labelled $l$ with $c_2$ children where $c_1 \neq c_2$, then I propose that we call them unranked trees.  
> **username_1**: If they are unranked trees, but every vertex has a bounded number of children, then I propose that we call them bounded degree unranked trees.  
> **username_1**: If they are unranked trees, but every tree is finite, then I propose that we call them finite unranked trees. You could naturally combine these two concepts to define bounded degree finite unranked trees.  

---

## 1 answers

### Answer by username_2 on 2018-04-21. Score: 2

You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.


---

