@inproceedings{lautemann_logics_1995,
 title = {Logics for context-free languages},
 author = {Lautemann, Clemens and Schwentick, Thomas and Thérien, Denis},
 year = {1995},
 isbn = {978-3-540-49404-1},
 doi = {10.1007/BFb0022257},
 booktitle = {Computer {Science} {Logic}},
 series = {Lecture {Notes} in {Computer} {Science}},
 editor = {Pacholski, Leszek and Tiuryn, Jerzy},
 pages = {205--216},
 publisher = {Springer},
 address = {Berlin, Heidelberg},
 language = {en},
 abstract = {We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.}
}