We performed a beam search by carrying out a K-best search through the set of possible sequences of actions as proposed by Johansson and Nugues (2006).
in Nivre's parsing algorithm the dependency graph can be viewed as a graph resulting from a set of parsing decisions (in this case Shift, Reduce , Left & Right) made, starting with the initial configuration (nil, W, ∅) .