Journal Title
Title of Journal: Appl Categor Struct
|
Abbravation: Applied Categorical Structures
|
Publisher
Springer Netherlands
|
|
|
|
|
|
Authors: E Colebunders S De Wachter M Schellekens
Publish Date: 2013/03/05
Volume: 22, Issue: 1, Pages: 119-136
Abstract
Complexity of a recursive algorithm typically is related to the solution to a recurrence equation based on its recursive structure For a broad class of recursive algorithms we model their complexity in what we call the complexity approach space the space of all functions in X = 0 ∞ Y where Y can be a more dimensional input space The set X which is a dcpo for the pointwise order moreover carries the complexity approach structure There is an associated selfmap Φ on the complexity approach space X such that the problem of solving the recurrence equation is reduced to finding a fixed point for Φ We will prove a general fixed point theorem that relies on the presence of the limit operator of the complexity approach space X and on a given well founded relation on Y Our fixed point theorem deals with monotone selfmaps Φ that need not be contractive We formulate conditions describing a class of recursive algorithms that can be treated in this way
Keywords:
.
|
Other Papers In This Journal:
|