<p>The described concept is known as <strong>graph grammars</strong> 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. <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Graph_rewriting" rel="nofollow">Wikipedia on Graph Rewriting</a>.</p>

CC BY-SA 3.0
2014-07-23T08:23:22.537Z
A graph is not a partially ordered string.
reinierpost
CC BY-SA 3.0
2014-07-23T08:32:01.300Z
@reinierpost A graph can be seen as a generalization of a partial order, as a directed graph can be interpreted as a binary relation.
ziggystar
CC BY-SA 3.0
2014-08-01T16:36:16.413Z
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.
reinierpost
CC BY-SA 2.5
2010-12-16T10:35:10.277Z
2010-12-16T12:32:29.417Z
2010-12-16T12:32:29.417Z
ziggystar
<p>You may be interested in <a href="http://en.wikipedia.org/wiki/Trace_monoid" rel="nofollow">trace theory</a>.</p>

<p>There has also been research on (fully) commutative languages.</p>

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

CC BY-SA 3.0
2012-05-07T14:21:11.130Z
2012-05-07T14:21:11.130Z
reinierpost
<p>I'm looking for work about partially ordered context-free grammars. I've found <a href="http://scholar.google.com/scholar?cluster=2340746033841345494&amp;hl=de&amp;as_sdt=2000&amp;as_vis=1" rel="nofollow">one paper</a>, 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.</p>

<p>Thus I'm looking for other work.</p>

<p><strong>What I mean by partially ordered CFG</strong></p>

<p>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:</p>

<pre><code>  b-c
 /   \
a     d-a
 \   /
  a--
</code></pre>

<p>The possible linearizations of this partially ordered word are aabcda, abacda, abcada.</p>

<reference-request><fl.formal-languages><grammars><partial-order>
Partially Ordered CFG
ziggystar
# Partially Ordered CFG

(Asked by: username_0 on 2010-12-15)

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.

**Tags:** reference-request, fl.formal-languages, grammars, partial-order


---

## 2 answers

### Answer by username_0 on 2010-12-16. Score: 5 | Accepted answer

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](https://secure.wikimedia.org/wikipedia/en/wiki/Graph_rewriting).

> **Comments:**
> **username_1**: A graph is not a partially ordered string.  
> **username_0**: @username_1 A graph can be seen as a generalization of a partial order, as a directed graph can be interpreted as a binary relation.  
> **username_1**: 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.  

---

### Answer by username_1 on 2012-05-07. Score: -1

You may be interested in [trace theory](http://en.wikipedia.org/wiki/Trace_monoid).

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.


---

