winterCFL:
  type: anthos
  title: Context-{Free} {Languages}, {Coalgebraically}
  author:
  - Winter, Joost
  - Bonsangue, Marcello M.
  - Rutten, Jan
  date: 2011
  editor:
  - Hutchison, David
  - Kanade, Takeo
  - Kittler, Josef
  - Kleinberg, Jon M.
  - Mattern, Friedemann
  - Mitchell, John C.
  - Naor, Moni
  - Nierstrasz, Oscar
  - Pandu Rangan, C.
  - Steffen, Bernhard
  - Sudan, Madhu
  - Terzopoulos, Demetri
  - Tygar, Doug
  - Vardi, Moshe Y.
  - Weikum, Gerhard
  - Corradini, Andrea
  - Klin, Bartek
  - Cîrstea, Corina
  page-range: 359-376
  url:
    value: http://link.springer.com/10.1007/978-3-642-22944-2_25
    date: 2025-01-30
  serial-number:
    doi: 10.1007/978-3-642-22944-2_25
    isbn: 978-3-642-22943-5 978-3-642-22944-2
  note: 'Series Title: Lecture Notes in Computer Science'
  abstract: 'We give a coalgebraic account of context-free languages using the functor D(X) = 2 × XA for deterministic automata over an alphabet A, in three different but equivalent ways: (i) by viewing context-free grammars as D-coalgebras; (ii) by defining a format for behavioural differential equations (w.r.t. D) for which the unique solutions are precisely the context-free languages; and (iii) as the D-coalgebra of generalized regular expressions in which the Kleene star is replaced by a unique fixed point operator. In all cases, semantics is defined by the unique homomorphism into the final coalgebra of all languages, paving the way for coinductive proofs of context-free language equivalence. Furthermore, the three characterizations can serve as the basis for the definition of a general coalgebraic notion of context-freeness, which we see as the ultimate long-term goal of the present study.'
  parent:
    type: anthology
    title: Algebra and {Coalgebra} in {Computer} {Science}
    publisher:
      name: Springer Berlin Heidelberg
      location: Berlin, Heidelberg
    volume: 6859