Document Open Access Logo

Constraint Solving over Multiple Similarity Relations

Authors Besik Dundua, Temur Kutsia, Mircea Marin, Cleopatra Pau

PDF
Thumbnail PDF

File

LIPIcs.FSCD.2020.30.pdf
  • Filesize: 0.55 MB
  • 19 pages

Document Identifiers

Author Details

Besik Dundua
  • FBT, International Black Sea University, Tbilisi, Georgia
  • VIAM, Ivane Javakhishvili Tbilisi State University, Georgia
Temur Kutsia
  • Johannes Kepler University, Research Institute for Symbolic Computation, Linz, Austria
Mircea Marin
  • West University of Timişoara, Romania
Cleopatra Pau
  • Johannes Kepler University, Research Institute for Symbolic Computation, Linz, Austria

Funding

This research has been partially supported by the Austrian Science Fund (FWF) under the project 28789-N32 and the Shota Rustaveli National Science Foundation of Georgia under the grant YS-18-1480.

Cite As Get BibTex

Besik Dundua, Temur Kutsia, Mircea Marin, and Cleopatra Pau. Constraint Solving over Multiple Similarity Relations. In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSCD.2020.30

Abstract

Similarity relations are reflexive, symmetric, and transitive fuzzy relations. They help to make approximate inferences, replacing the notion of equality. Similarity-based unification has been quite intensively investigated, as a core computational method for approximate reasoning and declarative programming. In this paper we consider solving constraints over several similarity relations, instead of a single one. Multiple similarities pose challenges to constraint solving, since we can not rely on the transitivity property anymore. Existing methods for unification with fuzzy proximity relations (reflexive, symmetric, non-transitive relations) do not provide a solution that would adequately reflect particularities of dealing with multiple similarities. To address this problem, we develop a constraint solving algorithm for multiple similarity relations, prove its termination, soundness, and completeness properties, and discuss applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
  • Computing methodologies → Symbolic and algebraic manipulation
  • Theory of computation → Semantics and reasoning
Keywords
  • Fuzzy relations
  • similarity
  • constraint solving

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hassan Aït-Kaci and Gabriella Pasi. Fuzzy unification and generalization of first-order terms over similar signatures. In Fabio Fioravanti and John P. Gallagher, editors, Logic-Based Program Synthesis and Transformation - 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers, volume 10855 of Lecture Notes in Computer Science, pages 218-234. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-94460-9_13.
  2. Hassan Aït-Kaci and Gabriella Pasi. Lattice operations on terms with fuzzy signatures. CoRR, abs/1709.00964, 2017. URL: http://arxiv.org/abs/1709.00964.
  3. Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, 1998. Google Scholar
  4. Franz Baader and Wayne Snyder. Unification theory. In John Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning (in 2 volumes), pages 445-532. Elsevier and MIT Press, 2001. URL: https://doi.org/10.1016/b978-044450813-3/50010-2.
  5. Francesca Arcelli Fontana and Ferrante Formato. Likelog: A logic programming language for flexible data retrieval. In Barrett R. Bryant, Gary B. Lamont, Hisham Haddad, and Janice H. Carroll, editors, Proceedings of the 1999 ACM Symposium on Applied Computing, SAC'99, San Antonio, Texas, USA, February 28 - March 2, 1999, pages 260-267. ACM, 1999. URL: https://doi.org/10.1145/298151.298348.
  6. Francesca Arcelli Fontana and Ferrante Formato. A similarity-based resolution rule. Int. J. Intell. Syst., 17(9):853-872, 2002. URL: https://doi.org/10.1002/int.10067.
  7. Ferrante Formato, Giangiacomo Gerla, and Maria I. Sessa. Extension of logic programming by similarity. In Maria Chiara Meo and Manuel Vilares Ferro, editors, 1999 Joint Conference on Declarative Programming, AGP'99, L'Aquila, Italy, September 6-9, 1999, pages 397-410, 1999. Google Scholar
  8. Ferrante Formato, Giangiacomo Gerla, and Maria I. Sessa. Similarity-based unification. Fundam. Inform., 41(4):393-414, 2000. URL: https://doi.org/10.3233/FI-2000-41402.
  9. Pascual Julián Iranzo and Clemente Rubio-Manzano. A sound and complete semantics for a similarity-based logic programming language. Fuzzy Sets and Systems, 317:1-26, 2017. URL: https://doi.org/10.1016/j.fss.2016.12.016.
  10. Pascual Julián Iranzo and Fernando Sáenz-Pérez. An efficient proximity-based unification algorithm. In 2018 IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2018, Rio de Janeiro, Brazil, July 8-13, 2018, pages 1-8. IEEE, 2018. URL: https://doi.org/10.1109/FUZZ-IEEE.2018.8491593.
  11. Joxan Jaffar and Michael J. Maher. Constraint logic programming: A survey. J. Log. Program., 19/20:503-581, 1994. URL: https://doi.org/10.1016/0743-1066(94)90033-7.
  12. Pascual Julián-Iranzo and Clemente Rubio-Manzano. Proximity-based unification theory. Fuzzy Sets and Systems, 262:21-43, 2015. URL: https://doi.org/10.1016/j.fss.2014.07.006.
  13. Cynthia Kop and Naoki Nishida. Term rewriting with logical constraints. In Pascal Fontaine, Christophe Ringeissen, and Renate A. Schmidt, editors, Frontiers of Combining Systems - 9th International Symposium, FroCoS 2013, Nancy, France, September 18-20, 2013. Proceedings, volume 8152 of Lecture Notes in Computer Science, pages 343-358. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40885-4_24.
  14. Stanislav Krajci, Rastislav Lencses, Jesús Medina, Manuel Ojeda-Aciego, and Peter Vojtás. A similarity-based unification model for flexible querying. In Troels Andreasen, Amihai Motro, Henning Christiansen, and Henrik Legind Larsen, editors, Flexible Query Answering Systems, 5th International Conference, FQAS 2002, Copenhagen, Denmark, October 27-29, 2002, Proceedings, volume 2522 of Lecture Notes in Computer Science, pages 263-273. Springer, 2002. URL: https://doi.org/10.1007/3-540-36109-X_21.
  15. Temur Kutsia and Cleo Pau. Solving proximity constraints. In Maurizio Gabbrielli, editor, Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8-10, 2019, Revised Selected Papers, volume 12042 of Lecture Notes in Computer Science, pages 107-122. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-45260-5_7.
  16. Jesús Medina, Manuel Ojeda-Aciego, and Peter Vojtás. Similarity-based unification: a multi-adjoint approach. Fuzzy Sets and Systems, 146(1):43-62, 2004. URL: https://doi.org/10.1016/j.fss.2003.11.005.
  17. Maria I. Sessa. Approximate reasoning by similarity-based SLD resolution. Theor. Comput. Sci., 275(1-2):389-426, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00188-8.
  18. Mariya I. Vasileva, Bryan A. Plummer, Krishna Dusad, Shreya Rajpal, Ranjitha Kumar, and David A. Forsyth. Learning type-aware embeddings for fashion compatibility. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XVI, volume 11220 of Lecture Notes in Computer Science, pages 405-421. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-01270-0_24.
  19. Andreas Veit, Serge J. Belongie, and Theofanis Karaletsos. Conditional similarity networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 1781-1789. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/CVPR.2017.193.
  20. Harry Virtanen. Vague domains, s-unification, logic programming. Electr. Notes Theor. Comput. Sci., 66(5):86-103, 2002. URL: https://doi.org/10.1016/S1571-0661(04)80516-4.
  21. Peter Vojtás. Declarative and procedural semantics of fuzzy similarity based unification. Kybernetika, 36(6):707-720, 2000. URL: http://www.kybernetika.cz/content/2000/6/707.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact