6533b861fe1ef96bd12c5793

RESEARCH PRODUCT

Logics for context-free languages

Clemens LautemannDenis ThérienThomas Schwentick

subject

Discrete mathematicsRange (mathematics)Class (set theory)Quantifier (logic)Symbol (programming)Context-free languageAbstract family of languagesOrder (group theory)Of the formAlgorithmMathematics

description

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.

yearjournalcountryeditionlanguage
1995-01-01
https://doi.org/10.1007/bfb0022257