Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

Base modules for parametrized iterativity

Adámek J, Milius S, Velebil J (2014)

---

Publication Type: Journal article

Publication year: 2014

Journal

Publisher: Elsevier

Book Volume: 523

Pages Range: 56-85

URI: http://www.sciencedirect.com/science/article/pii/S0304397513009316

DOI: 10.1016/j.tcs.2013.12.019

Abstract

The concept of a base, that is a parametrized finitary monad, which we introduced earlier, followed the footsteps of Tarmo Uustalu in his attempt to formalize parametrized recursion. We proved that for every base free iterative algebras exist, and we called the corresponding monad the rational monad of the base. Here we introduce modules for a base, and we prove that the rational monad of a base gives rise to a canonical module, that is characterized as the free iterative module on the given base. This generalizes the classical, nonparametric case of iterative Σ-algebras whose rational monad is the monad of rational Σ-trees and that was characterized by Calvin Elgot et al. as the free iterative monad on Σ. A basic parametrized example is the base assigning to every parameter set X the monad A → X * ×A whose rational monad is the monad of all right-wellfounded rational binary trees; the rational module for this base is the natural transformation (X * X)× A → * A given by parametrized concatenation. © 2014 Elsevier B.V.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Adámek, J., Milius, S., & Velebil, J. (2014). Base modules for parametrized iterativity. Theoretical Computer Science, 523, 56-85. https://dx.doi.org/10.1016/j.tcs.2013.12.019

MLA:

Adámek, Jiří, Stefan Milius, and Jiří Velebil. "Base modules for parametrized iterativity." Theoretical Computer Science 523 (2014): 56-85.

BibTeX: Download