Context-free languages via coalgebraic trace semantics

I. Hasuo, B.P.F. Jacobs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)


We show that, for functors with suitable mild restrictions, the initial algebra in the category of sets and functions gives rise to the final coalgebra in the (Kleisli) category of sets and relations. The finality principle thus obtained leads to the finite trace semantics of non-deterministic systems, which extends the trace semantics for coalgebras previously introduced by the second author. We demonstrate the use of our technical result by giving the first coalgebraic account on context-free grammars, where we obtain generated context-free languages via the finite trace semantics. Additionally, the constructions of both finite and possibly infinite parse trees are shown to be monads. Hence our extension of the application domain of coalgebras identifies several new mathematical constructions and structures.
Original languageEnglish
Title of host publicationAlgebra and Coalgebra in Computer Science (Proceedings First International Conference, CALCO 2005, Swansea, UK, September 3-6, 2005)
EditorsJ.L. Fiadeiro, N. Harman, M. Roggenbach, J. Rutten
Place of PublicationBerlin
ISBN (Print)3-540-28620-9
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Context-free languages via coalgebraic trace semantics'. Together they form a unique fingerprint.

Cite this