Coalgebraic characterizations of context-free languages

DOI10.2168/LMCS-9(3:14)2013MaRDI QIDQ2848359zbMATH OpenOpenAlexFDO

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

Publication date 26 September 2013

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

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)

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.

Recommendations

• Context-free languages, coalgebraically
• Context-free coalgebras
• Algebra and Coalgebra in Computer Science
• Defining context-free power series coalgebraically
• scientific article; zbMATH DE number 871238

Cited in

(16)

• Companions, codensity and causality
• Defining context-free power series coalgebraically
• Coalgebraic semantics for nominal automata
• Context-free coalgebras
• Characterization of co-observable languages and formulas for their super/sublanguages
• Context-free languages, coalgebraically
• A new foundation for finitary corecursion. The locally finite fixpoint and its properties
• Proper functors and fixed points for finite behaviour
• A new foundation for finitary corecursion and iterative algebras
• A Computational Interpretation of Context-Free Expressions
• scientific article; zbMATH DE number 1254100 (Why is no real title available?)
• A fixed point characterization of cofinite languages
• Algebra and Coalgebra in Computer Science
• Stream differential equations: specification formats and solution methods
• Determinization of inverted grammar programs via context-free expressions
• Product rules and distributive laws

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)