# Parsing with Traces: An O(n4) Algorithm and a Structural Representation

arXiv: https://arxiv.org/abs/1707.04221 · HTML: https://mlsanity.com/paper/1707.04221/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2017.

## Built on by (most cited first, 1 of 1)

- [Revisiting Absence withSymptoms that *T* Show up Decades Later to Recover Empty Categories](https://mlsanity.com/paper/2412.01109/) (2024)

## Abstract (arXiv)

General treebank analyses are graph structured, but parsers are typically restricted to tree structures for efficiency and modeling reasons. We propose a new representation and algorithm for a class of graph structures that is flexible enough to cover almost all treebank structures, while still admitting efficient learning and inference. In particular, we consider directed, acyclic, one-endpoint-crossing graph structures, which cover most long-distance dislocation, shared argumentation, and similar tree-violating linguistic phenomena. We describe how to convert phrase structure parses, including traces, to our new representation in a reversible manner. Our dynamic program uniquely decomposes structures, is sound and complete, and covers 97.3% of the Penn English Treebank. We also implement a proof-of-concept parser that recovers a range of null elements and trace types.