Logics For Context-Free Languages

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.

Authors

• Clemens Lautemann
• Thomas Schwentick
• Denis Thérien

Keywords

No keywords are indexed for this paper.