Recursive Program Schemes and Context-Free Monads

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F10%3A00169189" target="_blank" >RIV/68407700:21230/10:00169189 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Recursive Program Schemes and Context-Free Monads

Original language description

Solutions of recursive program schemes over a given signature were characterized by Bruno Courcelle as precisely the context-free (or algebraic) Sigma-trees. These are the finite and infinite Sigma-trees yielding, via labelling of paths, context-free languages. Our aim is to generalize this to finitary endofunctors H of general categories: we construct a monad C^H generated by solutions of recursive program schemes of type H, and prove that this monad is ideal. In case of polynomial endofunctors of Set our construction precisely yields the monad of context-free Sigma-trees of Courcelle. Our result builds on a result by N. Ghani et al on solutions of algebraic systems.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2010

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Electronic Notes in Theoretical Computer Science

ISSN

1571-0661

e-ISSN

—

Volume of the periodical

2010

Issue of the periodical within the volume

264

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

21

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—