Abstract | ||
---|---|---|
The concept of optimal fixpoint was introduced by Manna and Shamir [6, 7] in order to extract the maximum amount of “useful” information from a recursive definition. In this paper, we extend the concept of optimal fixpoint to arbitrary posets and investigate conditions which guarantee their existence. We prove that if a poset is chain-complete and has bounded joins, then every monotonic function has an optimal fixpoint. We also provide a sort of converse which generalizes a Theorem of A. Davis [2]. If a lower semilattice has bounded joins and every monotonic function has a fixpoint, then it is chain-complete. |
Year | DOI | Venue |
---|---|---|
1980 | 10.1007/BF01744296 | Mathematical Systems Theory |
Keywords | Field | DocType |
recursive definitions,fixpoints,optimal fixpoints,lower semilattices | Discrete mathematics,Monotonic function,Converse,Combinatorics,Joins,Fixed point,Semilattice,Partially ordered set,Mathematics,Bounded function,Recursive definition | Journal |
Volume | Issue | ISSN |
13 | 1 | 1433-0490 |
Citations | PageRank | References |
1 | 1.09 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jean H. Gallier | 1 | 749 | 111.86 |