We present a family of encodings for sequence labeling dependency parsing, based on the concept of hierarchical bracketing. We prove that the existing 4-bit projective encoding belongs to this family, but it is suboptimal in the number of labels used to encode a tree. We derive an optimal hierarchical bracketing, which minimizes the number of symbols used and encodes projective trees using only 12 distinct labels (vs. 16 for the 4-bit encoding). We also extend optimal hierarchical bracketing to support arbitrary non-projectivity in a more compact way than previous encodings. Our new encodings yield competitive accuracy on a diverse set of treebanks.

We revisit hierarchical bracketing encodings from a practical perspective in the context of dependency graph parsing.The approach encodes graphs as sequences, enabling lineartime parsing with n tagging actions, and still representing reentrancies, cycles, and empty nodes.Compared to existing graph linearizations, this representation substantially reduces the label space while preserving structural information.We evaluate it on a multilingual and multi-formalism benchmark, showing competitive results and consistent improvements over other methods in exact match accuracy.

Various linearizations have been proposed to cast syntactic dependency parsing as sequence labeling.However, these approaches do not support more complex graph-based representations, such as semantic dependencies or enhanced universal dependencies, as they cannot handle reentrancy or cycles.By extending them, we define a range of unbounded and bounded linearizations that can be used to cast graph parsing as a tagging task, enlarging the toolbox of problems that can be solved under this paradigm.Experimental results on semantic dependency and enhanced UD parsing show that with a good choice of encoding, sequencelabeling dependency graph parsers combine high efficiency with accuracies close to the state of the art, in spite of their simplicity.