Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{N}$ as:

$ar(a)=2, ar(b)=2, ar(c)=1$.

And Ranked Tree over $\Sigma$ is defined as:

$T_{\Sigma_r}$, the set of ranked trees, is the smallest set of terms $f(t_1,\dots,t_k)$ such that: $f\in\Sigma_r$, $k = ar(f)$, and $t_i\in T_{\Sigma_r}$ for all $1\leq i\leq k$.

The tree in this example looks like:

     /   \
    a     b
   / \   / \
  b   c c   c
 / \
c   c

But what about trees like that?

     /   \
    a     b
   / \   / \
  b   c c   c
  |   |
  c   a

This is also valid tree, but it is obviously is unranked.

My question: do any research regarding unranked alphabet trees exist?

What I've found so far is related only to logic for unranked trees.

  • $\begingroup$ If the arity of a particular symbol varies, then it's not a ranked tree. In a ranked tree the number of children depends only on the symbol. This probably makes things easier, and is "without loss of generality" since you can "annotate" each symbol with its arity. $\endgroup$ – Yuval Filmus Feb 20 '17 at 12:55
  • $\begingroup$ @YuvalFilmus thank you, that what I expected, that with variable arity it is not ranked tree anymore. But what about general theory of tree-automata and tree-grammars? Can I redefine all these things without usage of fixed arity? (I feel I can, I simply do not see any troubles). What kind of difficulties I can meet? $\endgroup$ – Andrey Lebedev Feb 20 '17 at 12:59
  • $\begingroup$ May be it is better to split question on two (first part is already answered by @YuvalFilmus), second part: can we redefine all tree-automata and tree-grammars theory w/o ranked alphabets? $\endgroup$ – Andrey Lebedev Feb 20 '17 at 13:02
  • $\begingroup$ You probably can (as long as the arity is bounded), but there really isn't that much difference. It's equivalent to annotating each vertex with its degree. $\endgroup$ – Yuval Filmus Feb 20 '17 at 13:02
  • $\begingroup$ @YuvalFilmus As I don't want "to invent the bicycle", may be you know any existent attempts (papers) where such definitions w/o ranking are given? Because currently I fill that there are some unknown reasons why ranked trees (only) are used in tree languages theory $\endgroup$ – Andrey Lebedev Feb 23 '17 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.