Istituto di Scienza e Tecnologie dell'Informazione     
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.
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

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional