Straccia U., Ojeda-Aciego M., Damasio C. V. On fixed-points of multivalued functions on complete lattices and their application to generalized logic programs. In: Siam Journal on Computing, vol. 38 (5) pp. 1881 - 1911. SIAM - Society for Industrial and Applied Mathematics, 2009. |

Abstract (English) |
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. | |

URL: | http://siamdl.aip.org/dbt/dbt.jsp?KEY=SMJCAT&Volume=LASTVOL&Issue=LASTISS | |

DOI: | 10.1137/070695976 | |

Subject | Fixed-points Multivalued functions Complete lattices Logic programming F.1.1 Models of Computation 47H10, 06B23, 68N17, 68Q55 |

1) Download Document PDF |

Open access Restricted Private