#StackBounty: #formal-languages #formal-grammars #trees #tree-grammars Unranked trees grammars?

Bounty: 50

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 : Sigmarightarrowmathcal{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: $finSigma_r$, $k = ar(f)$, and $t_iin T_{Sigma_r}$ for all $1leq ileq k$.

The tree in this example looks like:

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

But what about trees like that?

       b
     /   
    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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.