Name
Abstract | ||
|---|---|---|
We present a novel algorithm for calculating fix-points. The algorithm calculates fix-points of an endo-function f on a distributive lattice, by performing reachability computation a graph derived from the dual of f; this is in comparison to traditional algorithms that are based on iterated application of f until a fix-point is reached. In this paper we cast the problem of calculating fix-points in a categorical frame- work. We first show how fix-points can be expressed as limit constructions within a suitable category (C say). We then transport the fix-point calculation problem to the dual category of C (D, say). Within the dual-category D, the problem gets converted into calculating a co-limit construction. Still working within the dual-category, we show that the co-fix-point object can be calculated using a reachability based iterative algorithm. Finally the resulting dual fix- point object is transported back across the duality to C to give us the fix-point object that we initially wanted to calculate. In this paper, we concentrate on the case where the category C above, is the category of finite distributive lattices with homomorphisms, and the dual category D is the category of finite partial-orders and monotone functions. The rest of the paper is structured as follows: Section 2 gives some back- ground on lattice theory and duality-theory for distributive lattices. Section 3 formulates the notion of fix-points within a categorical setting. Section 4 then transports this calculation to the dual-category, and derives an algorithm for computing the dual-fix-point object. We conclude with some comments about future work in Section 6. |
Year | Venue | Keywords |
|---|---|---|
2006 | Clinical Orthopaedics and Related Research | duality theory,monotone function,lattice theory,distributive lattice,discrete mathematics,partial order,data structure,fixed point,iterative algorithm |
Field | DocType | Volume |
Distributive property,Discrete mathematics,Congruence lattice problem,Combinatorics,Distributive lattice,Complemented lattice,Map of lattices,Birkhoff's representation theorem,Reachability,Duality (optimization),Mathematics | Journal | abs/cs/060 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prahladavaradan Sampath | 1 | 64 | 7.65 |