EuDML | Browse

It is well known that, given an endofunctor $H$ on a category $ℂ$ , the initial $(A + H -)$ -algebras (if existing), i.e., the algebras of (wellfounded) $H$ -terms over different variable supplies $A$ , give rise to a monad with substitution as the extension operation (the free monad induced by the functor $H$ ). Moss [17] and Aczel, Adámek, Milius and Velebil [2] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete iterativeness),...

Generalizing Substitution

Tarmo Uustalu (2010)

RAIRO - Theoretical Informatics and Applications

It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies A, give rise to a monad with substitution as the extension operation (the free monad induced by the functor H). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete...

Generating Networks of Splicing Processors

Jürgen Dassow, Florin Manea, Bianca Truthe (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational...