<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](http://scholar.google.com/scholar?cluster=2340746033841345494&hl=de&as_sdt=2000&as_vis=1), 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.


---

