4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    May 21, 2018 at 16:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    May 21, 2018 at 16:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    May 21, 2018 at 16:10

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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