Partially Ordered CFG I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). It defines the language of a  pom-CFG by reduction to a normal context-free grammar, which excludes some (otherwise) possible words from the language, I think.

Thus I'm looking for other work.

What I mean by partially ordered CFG

The production rules don't produce linear strings of symbols but partially ordered (multi) sets of symbols. Thus the "words" of the generated language are also partially ordered multi-sets of symbols. For example this:

  b-c
 /   \
a     d-a
 \   /
  a--


The possible linearizations of this partially ordered word are aabcda, abacda, abcada.
The described concept is known as graph grammars and dates back into the 1970ies. Searching for this yields a sufficient amount of references. The terms "Graph Transformation" and "Graph Rewriting" are also used. See e.g. Wikipedia on Graph Rewriting.