Motivation:

Hyperedge replacement grammars (HRGs) are used for graph generation. 
Graphs are popular semantic representations.
We have previously shown that contextual HRGs are better at generating semantic graphs that plain HRGs.
The parsing problem for general HRGs is NP-complete.
There are restricted versions of HRGs that have polynomial-time parsing.

Another problem that we have been working on is the N best problem which refers to finding the N structures of best (smallest/largest depending on semiring) weight given a device that generates or recognises such structures.
When the structure type is trees, and the device is weighted tree automata, we can do this in polynomial time using an algorithm which we have developed in previous papers.
When the input to the N best problem is a graph-generating device, we run into problems because of graph isomorphy.
However, if the graphs have unique derivations, i.e., they can only be generated in one particular way, then we can use our N best algorithm for trees since we can view a derivation as a tree.

We want to:
- Add contextuality to the restricted HRGs to see if the polynomial-time parsing is kept.
or
- Solve the N best problem for one type of restricted HRG. For this, we need to check if there are unique derivations for this grammar type, and if not, if we can mitigate this.

bio16mrt
id19spn
hed19cnn
c19chd
c19abd
hed19phm
c19anm
c19nhd
tm12jkn
c19ehn
c19red
id19msh
ens18ssd
id19abn
id14fbk
ens08ran
id19mlr
c19hln
c19elm
id19tbm
hed19jln
c19tmy
id19eln

bio17abn@cs.umu.se
c18mwj@cs.umu.se
dv16dsm@cs.umu.se
ens17sln@cs.umu.se
et16cpn@cs.umu.se
tfy14jmk@cs.umu.se
tfy15odn@cs.umu.se
tfy16lga@cs.umu.se
tfy16mlm@cs.umu.se
tfy16pdg@cs.umu.se
tfy16san@cs.umu.se
tfy16shr@cs.umu.se
tfy17afn@cs.umu.se
tfy17aht@cs.umu.se
tfy17alr@cs.umu.se
tfy17amn@cs.umu.se
tfy17ceo@cs.umu.se
tfy17eon@cs.umu.se
tfy17esd@cs.umu.se
tfy17fen@cs.umu.se
tfy17fln@cs.umu.se
tfy17fnn@cs.umu.se
tfy17hbn@cs.umu.se
tfy17ils@cs.umu.se
tfy17jbg@cs.umu.se
tfy17jen@cs.umu.se
tfy17jfg@cs.umu.se
tfy17jsg@cs.umu.se
tfy17ksi@cs.umu.se
tfy17lan@cs.umu.se
tfy17msg@cs.umu.se
tfy17ngv@cs.umu.se
tfy17nhn@cs.umu.se
tfy17obg@cs.umu.se
tfy17oll@cs.umu.se
tfy17rvd@cs.umu.se
tfy17scn@cs.umu.se
tfy17snn@cs.umu.se
tfy17sri@cs.umu.se
tfy17whd@cs.umu.se
tfy18msn@cs.umu.se