What kind of algorithm is used to search sentence representations in working memory during online sentence processing? The alternatives we consider are (i) a serial algorithm that searches the sentence representation by traversing its graph structure and (ii) a parallel algorithm that queries the entire representation at once. The experiments and computational model described here provides evidence that contributes to this debate. We exploit a grammatical constraint in Brazilian Portuguese that requires a specific long-distance structural relation between a null subject and its antecedent. Whether an algorithm is serial or parallel has consequences for the kinds of relations that the algorithm is sensitive to. Long-distance relations – c-command, in particular – may be problematic for a parallel algorithm, but not a serial algorithm. In the case of locating a null subject’s antecedent, an algorithm’s sensitivity to long-distance structure should determine whether it considers a structurally ineligible subject as a possible antecedent. A serial algorithm should not consider the structurally ineligible subject, while a parallel algorithm, which is potentially blind to long-distance relations, should show signs of having considered the ineligible subject during the retrieval.

In three experiments and a computational model, we present evidence from null subject licensing and agreement processing that the human sentence processor has available to it both kinds of algorithm and is selective in its choice of algorithm. We also present evidence that a computational model which assumes a parallel algorithm cannot capture the fallibility profiles seen in humans even when given potentially unreasonable help in the form of relational cues.