The paper deals with the oscilation complexity OSC introduced in [W 79] for context-free languages. It is known that CF $$CF \subseteq OSC\left( {log} \right)$$ OSC(log), but it was an open question whether there exist context-free languages requiring logarithmic oscilation. We exhibit a language L ∈ CF for which a logarithmic lower bound on its oscilation complexity is established.
As a consequence we can conclude that the Dyck language D2 requires logarithmic oscilation.
Our proof method is a rather involved counting argument which exploits specific properties of L.