Supplementary Material: Strongly Incremental Constituency Parsing with Graph Neural Networks

The root node must be an internal node. Now we are ready to state and prove Theorem 1 and Theorem 2 in the main paper. We prove the correctness of Algorithm 1 by induction on the sentence length n . " to denote the execution trace taking the Case 1-1-- last_leaf has siblings, and last_subtree is the root node. We have last_subtree = last_leaf (the first conditional statement).