  We study the problem of enumerating Tarski fixed points, focusing on the
relational lattices of equivalences, quasiorders and binary relations. We
present a polynomial space enumeration algorithm for Tarski fixed points on
these lattices and other lattices of polynomial height. It achieves polynomial
delay when enumerating fixed points of increasing isotone maps on all three
lattices, as well as decreasing isotone maps on the lattice of binary
relations. In those cases in which the enumeration algorithm does not guarantee
polynomial delay on the three relational lattices on the other hand, we prove
exponential lower bounds for deciding the existence of three fixed points when
the isotone map is given as an oracle, and that it is NP-hard to find three or
more Tarski fixed points. More generally, we show that any deterministic or
bounded-error randomized algorithm must perform a number of queries
asymptotically at least as large as the lattice width to decide the existence
of three fixed points when the isotone map is given as an oracle. Finally, we
demonstrate that our findings yield a polynomial delay and space algorithm for
listing bisimulations and instances of some related models of behavioral or
role equivalence.
