In this article, we provide three coalgebraic characterizations of the class of context-free languages, each based on the idea of adding coalgebraic structure to an existing algebraic structure by specifying output-derivative pairs. Final coalgebra semantics then gives an interpretation function into the nal coalgebra of all languages with the usual output and derivative operations. The rst characterization is based on systems, where each derivative is given as a nite language over the set of nonterminals; the second characterization on systems where derivatives are given as elements of a term-algebra; and the third characterization is based on adding coalgebraic structure to a class of closed (unique) xed point expressions. We prove equivalences between these characterizations, discuss the generalization from languages to formal power series, as well as the relationship to the generalized powerset construction.
Additional Metadata
Keywords coalgebra, context-free languages, behavioural differential equations
THEME Software (theme 1)
Publisher Int. Fed. of Computational Logic
Persistent URL dx.doi.org/10.2168/LMCS-9(3:14)2013
Journal Logical Methods in Computer Science
Project Coinductive Calculi of Regular Expression
Citation
Winter, J, Bonsangue, M.M, & Rutten, J.J.M.M. (2013). Coalgebraic Characterizations of Context-free Languages. Logical Methods in Computer Science, 9(3). doi:10.2168/LMCS-9(3:14)2013