Reference. Context-Free Languages, Coalgebraically

Joost Winter, Marcello M. Bonsangue, Jan Rutten · CALCO · 2011 · parsing coalgebra · DOI
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.

Cite
Cite as @winterCFL (helia, typst) · \cite{winterCFL} (LaTeX)
BibTeX
bibtex · 18 lines
@incollection{winterCFL,
	address = {Berlin, Heidelberg},
	title = {Context-{Free} {Languages}, {Coalgebraically}},
	volume = {6859},
	isbn = {978-3-642-22943-5 978-3-642-22944-2},
	url = {http://link.springer.com/10.1007/978-3-642-22944-2_25},
	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.},
	language = {en},
	urldate = {2025-01-30},
	booktitle = {Algebra and {Coalgebra} in {Computer} {Science}},
	publisher = {Springer Berlin Heidelberg},
	author = {Winter, Joost and Bonsangue, Marcello M. and Rutten, Jan},
	editor = {Hutchison, David and Kanade, Takeo and Kittler, Josef and Kleinberg, Jon M. and Mattern, Friedemann and Mitchell, John C. and Naor, Moni and Nierstrasz, Oscar and Pandu Rangan, C. and Steffen, Bernhard and Sudan, Madhu and Terzopoulos, Demetri and Tygar, Doug and Vardi, Moshe Y. and Weikum, Gerhard and Corradini, Andrea and Klin, Bartek and Cîrstea, Corina},
	year = {2011},
	doi = {10.1007/978-3-642-22944-2_25},
	note = {Series Title: Lecture Notes in Computer Science},
	pages = {359--376},
}
hayagriva YAML (typst)
yaml · 43 lines
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
Download: winterCFL.bib · winterCFL.yml
Cited by (2)

A typed, algebraic approach to parsing krishnaswami_typed_2019PLDI · 2019
In this paper, we recall the definition of the context-free expressions (or µ-regular expressions), an algebraic presentation of the context-free languages. Then, we define a core type system for the context-free expressions which gives a compositional criterion for identifying those context-free expressions which can be parsed unambiguously by predictive algorithms in the style of recursive descent or LL(1). Next, we show how these typed grammar expressions can be used to derive a parser combinator library which both guarantees linear-time parsing with no backtracking and single-token lookahead, and which respects the natural denotational semantics of context-free expressions. Finally, we show how to exploit the type information to write a staged version of this library, which produces dramatic increases in performance, even outperforming code generated by the standard parser generator tool ocamlyacc.
DOI · pldb

Generalizing determinization from automata to coalgebras silva-2013-generalizingLMCS · 2013
The powerset construction is a standard method for converting a nondeterministic automaton into a deterministic one recognizing the same language. In this paper, we lift the powerset construction from automata to the more general framework of coalgebras with structured state spaces. Coalgebra is an abstract framework for the uniform study of different kinds of dynamical systems. An endofunctor F determines both the type of systems (F-coalgebras) and a notion of behavioural equivalence (~_F) amongst them. Many types of transition systems and their equivalences can be captured by a functor F. For example, for deterministic automata the derived equivalence is language equivalence, while for non-deterministic automata it is ordinary bisimilarity. We give several examples of applications of our generalized determinization construction, including partial Mealy machines, (structured) Moore automata, Rabin probabilistic automata, and, somewhat surprisingly, even pushdown automata. To further witness the generality of the approach we show how to characterize coalgebraically several equivalences which have been object of interest in the concurrency community, such as failure or ready semantics.
DOI · arXiv
Cites 18 works (2 here)
With notes (2)

A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events KOZEN1994366I&C · 1994
We give a finitary axiomatization of the algebra of regular events involving only equations and equational implications. Unlike Salomaa′s axiomatizations, the axiomatization given here is sound for all interpretations over Kleene algebras.
DOI

Towards Kleene Algebra with recursion leis_towards_1992CSL · 1992
We extend Kozen’s theory KA of Kleene Algebra to axiomatize parts of the equational theory of context-free languages, using a least fixed-point operator μ instead of Kleene’s iteration operator*.
DOI
External (16)
winterCFL reference entries/refs/winterCFL/winterCFL.hel