Higher-Order and Symbolic Computation, 18(1/2)
Least Reflexive Points of RelationsJules Desharnais, Departement d'Informatique, Universite Laval, Quebec, Canada
Bernhard Möller, Institut für Informatik, Universität Augsburg, Germany
|
Abstract: Assume a partially ordered set (S,≤) and a
relation R on S. We consider various sets of conditions in order to
determine whether they ensure the existence of a least reflexive
point, that is, a least x such that xRx. This is a generalization of
the problem of determining the least fixed point of a function and the
conditions under which it exists. To motivate the investigation we
first present a theorem by Cai and Paige giving conditions under which
iterating R from the bottom element necessarily leads to a minimal
reflexive point; the proof is by a concise relation-algebraic
calculation. Then, we assume a complete lattice and exhibit
sufficient conditions, depending on whether R is partial or not, for
the existence of a least reflexive point. Further results concern the
structure of the set of all reflexive points; among other results we
give a sufficient condition that these form a complete lattice, thus
generalizing Tarski's classical result to the nondeterministic case.
Keywords: Least reflexive point, greatest reflexive point, fixed point, lattice, partial order, relation, inflationary relation. |
This article is not yet available.
![[picture of journal cover]](../LISP.JPG)