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

uncategorised

Authors

Umberto Straccia

Manuel Ojeda-Aciego

Carlos Viegas Damásio

Published

1 January 2009

Publication details

{SIAM} J. Comput. vol. 38 (5), pages 1881–1911.

Links

Abstract

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.

Citation

Please, cite this work as:

[SOD09] U. Straccia, M. Ojeda-Aciego, and C. V. Damásio. “On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs”. In: SIAM J. Comput. 38.5 (2009), pp. 1881-1911. DOI: 10.1137/070695976. URL: https://doi.org/10.1137/070695976.

BibTeX

@Article{Straccia2009,
     author = {Umberto Straccia and Manuel Ojeda-Aciego and Carlos Viegas Dam{’a}sio},
     journal = {{SIAM} J. Comput.},
     title = {On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs},
     year = {2009},
     number = {5},
     pages = {1881–1911},
     volume = {38},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/journals/siamcomp/StracciaOD09.bib},
     doi = {10.1137/070695976},
     timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
     url = {https://doi.org/10.1137/070695976},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

Citations
CrossRef - Citation Indexes: 22
Policy Citation - Policy Citations: 1
Scopus - Citation Indexes: 29

Captures
Mendeley - Readers: 8

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

[1] D. Acemoglu and M. Jackson. History, Expectations, and Leadership in the Evolution of Social Norms. May. 2011. DOI: 10.3386/w17066. URL: http://dx.doi.org/10.3386/w17066.

[2] D. Acemoglu and M. O. Jackson. “History, Expectations, and Leadership in Evolution of Social Norms”. In: SSRN Electronic Journal (2011). ISSN: 1556-5068. DOI: 10.2139/ssrn.1839768. URL: http://dx.doi.org/10.2139/ssrn.1839768.

[3] D. Acemoglu and M. O. Jackson. “History, Expectations, and Leadership in the Evolution of Social Norms”. In: The Review of Economic Studies 82.2 (Dec. 2014), p. 423–456. ISSN: 1467-937X. DOI: 10.1093/restud/rdu039. URL: http://dx.doi.org/10.1093/restud/rdu039.

[4] M. R. Alfuraidan. “Metric Fixed Point Theory in Spaces with a Graph”. In: Fixed Point Theory and Graph Theory. Elsevier, 2016, p. 287–363. ISBN: 9780128042953. DOI: 10.1016/b978-0-12-804295-3.50007-3. URL: http://dx.doi.org/10.1016/b978-0-12-804295-3.50007-3.

[5] M. R. Alfuraidan. “Remarks on monotone multivalued mappings on a metric space with a graph”. In: Journal of Inequalities and Applications 2015.1 (Jun. 2015). ISSN: 1029-242X. DOI: 10.1186/s13660-015-0712-6. URL: http://dx.doi.org/10.1186/s13660-015-0712-6.

[6] M. Blondeel, S. Schockaert, M. De Cock, et al. “Fuzzy autoepistemic logic and its relation to fuzzy answer set programming”. In: Fuzzy Sets and Systems 239 (Mar. 2014), p. 51–80. ISSN: 0165-0114. DOI: 10.1016/j.fss.2012.09.012. URL: http://dx.doi.org/10.1016/j.fss.2012.09.012.

[7] M. Blondeel, S. Schockaert, D. Vermeir, et al. “Complexity of fuzzy answer set programming under Łukasiewicz semantics”. In: International Journal of Approximate Reasoning 55.9 (Dec. 2014), p. 1971–2003. ISSN: 0888-613X. DOI: 10.1016/j.ijar.2013.10.011. URL: http://dx.doi.org/10.1016/j.ijar.2013.10.011.

[8] M. Blondeel, S. Schockaert, D. Vermeir, et al. “Fuzzy Answer Set Programming: An Introduction”. In: Soft Computing: State of the Art Theory and Novel Applications. Springer Berlin Heidelberg, 2013, p. 209–222. ISBN: 9783642349225. DOI: 10.1007/978-3-642-34922-5_15. URL: http://dx.doi.org/10.1007/978-3-642-34922-5_15.

[9] M. E. Cornejo, D. Lobo, and J. Medina. “Syntax and semantics of multi-adjoint normal logic programming”. In: Fuzzy Sets and Systems 345 (Aug. 2018), p. 41–62. ISSN: 0165-0114. DOI: 10.1016/j.fss.2017.12.009. URL: http://dx.doi.org/10.1016/j.fss.2017.12.009.

[10] A. Hanjing and S. Suantai. “Coincidence point and fixed point theorems for a new type of G-contraction multivalued mappings on a metric space endowed with a graph”. In: Fixed Point Theory and Applications 2015.1 (Sep. 2015). ISSN: 1687-1812. DOI: 10.1186/s13663-015-0420-4. URL: http://dx.doi.org/10.1186/s13663-015-0420-4.

[11] P. Hitzler and A. Seda. Mathematical Aspects of Logic Programming Semantics. CRC Press, Apr. 2016. ISBN: 9780429094231. DOI: 10.1201/b10397. URL: http://dx.doi.org/10.1201/b10397.

[12] J. Janssen, S. Schockaert, D. Vermeir, et al. “A core language for fuzzy answer set programming”. In: International Journal of Approximate Reasoning 53.4 (Jun. 2012), p. 660–692. ISSN: 0888-613X. DOI: 10.1016/j.ijar.2012.01.005. URL: http://dx.doi.org/10.1016/j.ijar.2012.01.005.

[13] J. Janssen, S. Schockaert, D. Vermeir, et al. “Aggregated Fuzzy Answer Set Programming”. In: Annals of Mathematics and Artificial Intelligence 63.2 (Aug. 2011), p. 103–147. ISSN: 1573-7470. DOI: 10.1007/s10472-011-9256-8. URL: http://dx.doi.org/10.1007/s10472-011-9256-8.

[14] J. JANSSEN, D. VERMEIR, S. SCHOCKAERT, et al. “Reducing fuzzy answer set programming to model finding in fuzzy logics”. In: Theory and Practice of Logic Programming 12.6 (Jun. 2011), p. 811–842. ISSN: 1475-3081. DOI: 10.1017/s1471068411000093. URL: http://dx.doi.org/10.1017/s1471068411000093.

[15] J. Medina and J. A. Torné-Zambrano. “Immediate consequences operator on generalized quantifiers”. In: Fuzzy Sets and Systems 456 (Mar. 2023), p. 72–91. ISSN: 0165-0114. DOI: 10.1016/j.fss.2022.08.014. URL: http://dx.doi.org/10.1016/j.fss.2022.08.014.

[16] G. Moreno, J. Penabad, and C. Vázquez. “Beyond multi-adjoint logic programming”. In: International Journal of Computer Mathematics 92.9 (Nov. 2014), p. 1956–1975. ISSN: 1029-0265. DOI: 10.1080/00207160.2014.975218. URL: http://dx.doi.org/10.1080/00207160.2014.975218.

[17] F. Ranzato. “Abstract Interpretation of Supermodular Games”. In: Static Analysis. Springer Berlin Heidelberg, 2016, p. 403–423. ISBN: 9783662534137. DOI: 10.1007/978-3-662-53413-7_20. URL: http://dx.doi.org/10.1007/978-3-662-53413-7_20.

[18] S. Romaguera, M. P. Schellekens, and O. Valero. “The complexity space of partial functions: a connection between complexity analysis and denotational semantics”. In: International Journal of Computer Mathematics 88.9 (Jun. 2011), p. 1819–1829. ISSN: 1029-0265. DOI: 10.1080/00207161003631885. URL: http://dx.doi.org/10.1080/00207161003631885.

[19] E. Saad. “Extended Fuzzy Logic Programs with Fuzzy Answer Set Semantics”. In: Scalable Uncertainty Management. Springer Berlin Heidelberg, 2009, p. 223–239. ISBN: 9783642043888. DOI: 10.1007/978-3-642-04388-8_18. URL: http://dx.doi.org/10.1007/978-3-642-04388-8_18.

[20] S. Schockaert, J. Janssen, and D. Vermeir. “Fuzzy Equilibrium Logic: Declarative Problem Solving in Continuous Domains”. In: ACM Transactions on Computational Logic 13.4 (Oct. 2012), p. 1–39. ISSN: 1557-945X. DOI: 10.1145/2362355.2362361. URL: http://dx.doi.org/10.1145/2362355.2362361.

[21] S. Schockaert, N. Makarytska, and M. De Cock. “Fuzzy Methods on the Web: A Critical Discussion”. In: 35 Years of Fuzzy Set Theory. Springer Berlin Heidelberg, 2010, p. 237–266. ISBN: 9783642166297. DOI: 10.1007/978-3-642-16629-7_12. URL: http://dx.doi.org/10.1007/978-3-642-16629-7_12.

[22] U. Straccia and F. Bobillo. “From Fuzzy to Annotated Semantic Web Languages”. In: Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering. Springer International Publishing, 2017, p. 203–240. ISBN: 9783319494937. DOI: 10.1007/978-3-319-49493-7_6. URL: http://dx.doi.org/10.1007/978-3-319-49493-7_6.

[23] X. Vives and O. Vravosinos. “Strategic complementarity in games”. In: Journal of Mathematical Economics 113 (Aug. 2024), p. 103005. ISSN: 0304-4068. DOI: 10.1016/j.jmateco.2024.103005. URL: http://dx.doi.org/10.1016/j.jmateco.2024.103005.