What is the name of the following data structure: Tree + Transclusion of incomparable nodes.

55 Views Asked by At

This is a followup question to the earlier one. Antichains

What is the name of the following data structure: Tree + Transclusion of incomparable nodes. This can be equivalently stated as Tree + Transclusion of nodes from an antichain.

Example using indentation for the tree and ">" as representing transclusion.

A
  B
  C
    >B
  D
    >B

And if a child element is added to B then the tree would be:

A
  B
    E
  C
    >B
       E
  D
    >B
       E

The obvious use case for this data structure is Knowledge Management where the information held under "B" can be included by reference multiple times. (This kind of transclusion works in Confluence at the page level. Workflowy.com doesn't yet support this, however I believe that Roam Research does).

Back to the example, my intuition is that the only remaining incomparable nodes in the tree are C and D and so C could be transcluded into D or D into C. Let's incorporate C as a part of D:

A
  B
    E
  C
    >B
       E
  D
    >B
       E
    >C
       >B
          E

There are no now incomparable nodes. (Or Any further transclusion would introduce loops into the tree.)

This is an interesting data structure which is a generalisation of the tree and if the base tree is finite, the transclusion operation can only be applied a finite number of times until we run out of incomparable nodes.

Does this data structure have a name and have its properties been studied?

All the best

David