On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)


Unlike monotone single-valued functions, multivalued mappings may have zero, one, or (possibly infinitely) many minimal fixed-points. The contribution of this work is twofold. First, we overview and investigate the existence and computation of minimal fixed-points of multivalued mappings, whose domain is a complete lattice and whose range is its power set. Second, we show how these results are applied to a general form of logic programs, where the truth space is a complete lattice. We show that a multivalued operator can be defined whose fixed-points are in one-to-one correspondence with the models of the logic program.
Original languageUnknown
Pages (from-to)1881-1911
JournalSIAM Journal on Computing (SICOMP)
Issue number5
Publication statusPublished - 1 Jan 2009

Cite this