Songbird syntax is generally thought to be simple, in particular lacking long-distance dependencies in which one element affects choice of another occurring considerably later in the sequence. Here, we test for long-distance dependencies in the sequences of songs produced by song sparrows (Melospiza melodia). Song sparrows sing with eventual variety, repeating each song type in a consecutive series termed a 'bout'. We show that in switching between song types, song sparrows follow a 'cycling rule', cycling through their repertoires in close to the minimum possible number of bouts. Song sparrows do not cycle in a set order but rather vary the order of song types from cycle to cycle. Cycling in a variable order strongly implies long-distance dependencies, in which choice of the next type depends on the song types sung over the past cycle, in the range of 9-10 bouts. Song sparrows also follow a 'bout length rule', whereby the number of repetitions of a song type in a bout is positively associated with the length of the interval until that type recurs. This rule requires even longer distance dependencies that cross one another; such dependencies are characteristic of more complex levels of syntax than previously attributed to non-human animals.
Keywords: animal communication; birdsong; language evolution; song; syntax.