On second-order iterative monads
Result description
B. Courcelle studied algebraic trees as precisely the solutions of all recursive program schemes for a given signature in Set. He proved that the corresponding monad is iterative. We generalize this to recursive program schemes over a given unitary endofunctor H of a "suitable" category. A monad is called second-order iterative if every guarded recursive program scheme has a unique solution in it. We construct two second-order iterative monads: one, called the second-order rational monad, S(H), is proved to be the initial second-order iterative monad. The other one, called the context-free monad, C(H), is a quotient of S(H) and in the original case of a polynomial endofunctor H of Set we prove that C(H) is the monad studied by B. Courcelle. The question whether these two monads are equal is left open. (C) 2011 Elsevier B.V. All rights reserved.
Keywords
Algebraic treesRecursive program schemesIdeal theoryMonadsINFINITE-TREESALGEBRASFINITARY
The result's identifiers
Result code in IS VaVaI
Result on the web
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
On second-order iterative monads
Original language description
B. Courcelle studied algebraic trees as precisely the solutions of all recursive program schemes for a given signature in Set. He proved that the corresponding monad is iterative. We generalize this to recursive program schemes over a given unitary endofunctor H of a "suitable" category. A monad is called second-order iterative if every guarded recursive program scheme has a unique solution in it. We construct two second-order iterative monads: one, called the second-order rational monad, S(H), is proved to be the initial second-order iterative monad. The other one, called the context-free monad, C(H), is a quotient of S(H) and in the original case of a polynomial endofunctor H of Set we prove that C(H) is the monad studied by B. Courcelle. The question whether these two monads are equal is left open. (C) 2011 Elsevier B.V. All rights reserved.
Czech name
—
Czech description
—
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Volume of the periodical
412
Issue of the periodical within the volume
38
Country of publishing house
GB - UNITED KINGDOM
Number of pages
20
Pages from-to
4969-4988
UT code for WoS article
000294317000002
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BA - General mathematics
Year of implementation
2011