Completely iterative algebras and completely iterative monads
Completely iterative algebras and completely iterative monads
复制标题
DOI：
10.1016/j.ic.2004.05.003
复制
发表时间：
2005-01-10
影响因子：
1
通讯作者：
Milius, S
中科院分区：
文献类型：
--
作者：
Milius, S
卡尔文·埃尔戈特的完全迭代理论将(潜在无限的)计算形式化为递归方程的解。Elget和他的合著者的主要结果之一是无限大树形成了一个自由的完全迭代理论。他们对这一结果的代数证明极其复杂。我们提出了完全迭代代数作为描述自由完全迭代理论的一种新方法。完全迭代代数的例子包括完备度量空间上的代数。证明了函子允许一个初始完全迭代代数当且仅当它有一个最终余代数。证明了由自由完全迭代代数给出的单子是给定内函子上的自由完全迭代单子。这大大简化了以前对这些单子的所有描述。此外，新方法比Elget等人的经典方法更具一般性。证明了自由完全迭代单子存在的一个充要条件。(C)2004 Elsevier Inc.保留所有权利。
Completely iterative theories of Calvin Elgot formalize (potentially infinite) computations as solutions of recursive equations. One of the main results of Elgot and his coauthors is that infinite trees form a free completely iterative theory. Their algebraic proof of this result is extremely complicated. We present completely iterative algebras as a new approach to the description of free completely iterative theories. Examples of completely iterative algebras include algebras on complete metric spaces. It is shown that a functor admits an initial completely iterative algebra iff it has a final coalgebra. The monad given by free completely iterative algebras is proved to be the free completely iterative monad on the given endofunctor. This simplifies substantially all previous descriptions of these monads. Moreover, the new approach is much more general than the classical one of Elgot et al. A necessary and sufficient condition for the existence of a free completely iterative monad is proved. (C) 2004 Elsevier Inc. All rights reserved.