Coalgebraic characterizations of context-free languages

DOI10.2168/LMCS-9(3:14)2013zbMATH Open1274.68215arXiv1308.1228OpenAlexW1987150452MaRDI QIDQ2848359FDOQ2848359

Marcello M. Bonsangue, Jan J. M. M. Rutten, Joost Winter

Publication date: 26 September 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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 final coalgebra of all languages with the usual output and derivative operations. The first characterization is based on systems, where each derivative is given as a finite 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) fixed 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.

Full work available at URL: https://arxiv.org/abs/1308.1228

zbMATH Keywords

formal power seriescoalgebracontext-free languagesformal languages

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Cited In (13)

• Coalgebraic semantics for nominal automata
• Companions, Codensity and Causality
• Title not available (Why is that?)
• Characterization of co-observable languages and formulas for their super/sublanguages
• Title not available (Why is that?)
• Product Rules and Distributive Laws
• A new foundation for finitary corecursion and iterative algebras
• A Computational Interpretation of Context-Free Expressions
• Title not available (Why is that?)
• A fixed point characterization of cofinite languages
• Algebra and Coalgebra in Computer Science
• A New Foundation for Finitary Corecursion
• Determinization of inverted grammar programs via context-free expressions

This page was built for publication: Coalgebraic characterizations of context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848359)