Recursive Program Schemes and Context-Free Monads
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Recursive Program Schemes and Context-Free Monads
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Recursive Program Schemes and Context-Free Monads
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Electronic Notes in Theoretical Computer Science
ISSN
1571-0661
e-ISSN
—
Svazek periodika
2010
Číslo periodika v rámci svazku
264
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
21
Strana od-do
—
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—