5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ A graph is not a partially ordered string. $\endgroup$
    – reinierpost
    Jul 23, 2014 at 8:23
  • $\begingroup$ @reinierpost A graph can be seen as a generalization of a partial order, as a directed graph can be interpreted as a binary relation. $\endgroup$
    – ziggystar
    Jul 23, 2014 at 8:32
  • $\begingroup$ I know, but here the objects of interest are not graphs, but traces (which can be regarded as equivalence classes of graphs). I like your idea of using graph grammars, but your opening statement is incorrect: rewriting graphs is not the same thing, as you have to make sure to respect the equivalences. $\endgroup$
    – reinierpost
    Aug 1, 2014 at 16:36
-1
$\begingroup$

You may be interested in trace theory.

There has also been research on (fully) commutative languages.

Not having studied either, I can't give you any more specific references, but Google can.

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.