lautemann_logics_1995:
  type: article
  title: Logics for context-free languages
  author:
  - Lautemann, Clemens
  - Schwentick, Thomas
  - Thérien, Denis
  date: 1995
  editor:
  - Pacholski, Leszek
  - Tiuryn, Jerzy
  page-range: 205-216
  serial-number:
    doi: 10.1007/BFb0022257
    isbn: 978-3-540-49404-1
  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.
  parent:
    type: proceedings
    title: Computer {Science} {Logic}
    publisher:
      name: Springer
      location: Berlin, Heidelberg
    parent:
      type: proceedings
      title: Lecture {Notes} in {Computer} {Science}