Least Reflexive Points of Relations |
| |
Authors: | Jules Desharnais Bernhard Möller |
| |
Affiliation: | (1) Département d’Informatique, Université Laval, Québec, QC, G1K 7P4, Canada;(2) Institut für Informatik, Universität Augsburg, D-86135 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.This research is supported by a grant from NSERC (Natural Sciences and Engineering Research Council of Canada). |
| |
Keywords: | least reflexive point greatest reflexive point fixed point lattice partial order relation inflationary relation |
本文献已被 SpringerLink 等数据库收录! |
|