(2018) since, as in other transition-based parsers such as (Covington, 2001;Gómez-Rodríguez and Nivre, 2010), cycles can be incrementally identified in amortized constant time by keeping track of connected components using path compression and union by rank.
the left-to-right algorithm requires n steps to produce a parse.