Abstract
Recent years have witnessed the effort to extend answer set programming (ASP) with properties of fuzzy logic. The result of this combination is fuzzy answer set programming (FASP), a powerful framework for knowledge representation and non-monotonic reasoning with graded levels of truth. The various results in solving FASP make use of transformations into fuzzy satisfiability (SAT) problems, optimization programs, satisfiability modulo theories (SMT), or classical ASP, each of which comes with limitations or scaling problems. Moreover, most of the research revolves around Gödel and Łukasiewicz semantics. The former approach is elegant in its attempt to generalize well-known methods in classical ASP to the fuzzy case. In our work we seek to extend this approach under the product semantics, utilizing the fuzzy generalization of the DPLL algorithm. As such, we design the inner works of a DPLL-based fuzzy SAT solver for propositional product logic, which should provide foundations for the technical implementation of the solver.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We do not explicitly refer to the properties and neutral elements of \({\pmb {\vee }}\), \({\pmb {\wedge }}\).
- 2.
This is because we can regard rules as residual implicators.
- 3.
Constants in the open interval (0, 1).
- 4.
With the decreasing connective precedence: \(\lnot \), \({\Delta }\), \( { \& \ }\), \(\eqcirc \), \(\prec \), \(\wedge \), \(\vee \), \(\rightarrow \), \(\leftrightarrow \).
- 5.
With the decreasing operator precedence: \(\pmb \sim \), \({\pmb {\Delta }}\), \({\cdot }\), \({\pmb {\eqcirc }}\), \({\pmb {\prec }}\), \({\pmb {\wedge }}\), \({\pmb {\vee }}\), \({\pmb {\Rightarrow }}\).
References
Alviano, M., Amendola, G., Peñaloza, R.: Minimal undefinedness for fuzzy answer sets. In: Singh, S.P., Markovitch, S. (eds.) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4–9, 2017, San Francisco, California, USA, pp. 3694–3700. AAAI Press (2017). http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14309
Alviano, M., Peñaloza, R.: Fuzzy answer set computation via satisfiability modulo theories. TPLP 15(4–5), 588–603 (2015). https://doi.org/10.1017/S1471068415000241
Alviano, M., Pealoza, R.: Fuzzy answer sets approximations. Theory Pract. Log. Program. 13(4–5), 753–767 (2013)
Baaz, M., Hájek, P., Švejda, D., Krajíček, J.: Embedding logics into product logic. Stud. Log. 61(1), 35–47 (1998). https://doi.org/10.1023/A:1005026229560
Blondeel, M., Schockaert, S., De Cock, M., Vermeir, D.: NP-completeness of fuzzy answer set programming under Lukasiewicz semantics, pp. 43–50 (8 2012)
Bobillo, F., Straccia, U.: A fuzzy description logic with product t-norm. In: 2007 IEEE International Fuzzy Systems Conference, pp. 1–6 (2007). https://doi.org/10.1109/FUZZY.2007.4295443
Brys, T., Drugan, M.M., Bosman, P.A., De Cock, M., Nowé, A.: Solving satisfiability in fuzzy logics by mixing cma-es. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO ’13, pp. 1125–1132. ACM, New York, NY, USA (2013). https://doi.org/10.1145/2463372.2463510
Clark, K.L.: Negation as failure., pp. 293–322. Springer US, Boston, MA (1978). https://doi.org/10.1007/978-1-4684-3384-5_11
Dantzig, G.B.: Origins of the simplex method. A History of Scientific Computing, pp. 141–151. ACM, New York, NY, USA (1990). https://doi.org/10.1145/87252.88081
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers (2012)
Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming, pp. 1070–1080. MIT Press, Cambridge (1988)
Guller, D.: Expanding Gödel Logic with Truth Constants and the Equality, Strict Order, Delta Operators, pp. 241–269. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-48506-5_13
Guller, D.: A DPLL procedure for the propositional product logic. In: Proceedings of the 5th International Joint Conference on Computational Intelligence - Volume 1: FCTA, (IJCCI 2013). pp. 213–224. INSTICC, SciTePress (2013). https://doi.org/10.5220/0004557402130224
Guller, D.: An order hyperresolution calculus for Gödel logic with truth constants and equality, strict order, delta. In: 2015 7th International Joint Conference on Computational Intelligence (IJCCI), vol. 2, pp. 31–46 (2015)
Guller, D.: Technical foundations of a DPLL-based SAT solver for propositional product logic (2016), Unpublished manuscript
Hähnle, R.: Many-valued logic and mixed integer programming. Ann. Math. Artif. Intell. 12(3), 231–263 (1994). https://doi.org/10.1007/BF01530787
Hansen, N.: The CMA Evolution Strategy: A Comparing Review, pp. 75–102. Springer, Berlin, Heidelberg (2006). https://doi.org/10.1007/3-540-32494-1_4
Janssen, J., Schockaert, S., Vermeir, D., De Cock, M.: Answer Set Programming for Continuous Domains: A Fuzzy Logic Approach. Atlantis Computational Intelligence Systems. Atlantis Press, Paris (2012). https://books.google.sk/books?id=OLjCFm8KpZIC
Janssen, J., Schockaert, S., Vermeir, D., Cock, M.D.: Reducing fuzzy answer set programming to model finding in fuzzy logics (2011). http://arxiv.org/abs/1104.5133
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7(3), 499–562 (2006). https://doi.org/10.1145/1149114.1149117
Lifschitz, V.: Action languages, answer sets and planning. The Logic Programming Paradigm: a 25-Year Perspective, pp. 357–373. Springer, Berlin (1999). http://www.cs.utexas.edu/users/ai-lab/?lif99
Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by sat solvers. Artif. Intell. 157(1), 115–137 (2004). https://doi.org/10.1016/j.artint.2004.04.004
Mushthofa, M., Schockaert, S., Cock, M.D.: A finite-valued solver for disjunctive fuzzy answer set programs. In: Proceedings of the Twenty-first European Conference on Artificial Intelligence, ECAI’14, pp. 645–650. IOS Press, Amsterdam, The Netherlands (2014). https://doi.org/10.3233/978-1-61499-419-0-645
Mushthofa, M., Schockaert, S., De Cock, M.: Solving Disjunctive Fuzzy Answer Set Programs, pp. 453–466. Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_38
Mushthofa, M., Schockaert, S., De Cock, M.: Computing attractors of multi-valued gene regulatory networks using fuzzy answer set programming. In: Proceedings of the 2016 IEEE International Conference on Fuzzy Systems FUZZ-IEEE’2016. pp. 1955–1962. IEEE (2016)
Simons, P., Niemel, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1), 181–234 (2002). https://doi.org/10.1016/S0004-3702(02)00187-X
Uhliarik, I.: Solving fuzzy answer set programs in product logic. In: Proceedings of the 9th International Joint Conference on Computational Intelligence - Volume 1: IJCCI, pp. 367–372. INSTICC, SciTePress (2017). https://doi.org/10.5220/0006518303670372
Van Nieuwenborgh, D., De Cock, M., Vermeir, D.: Computing Fuzzy Answer Sets Using DLVHEX, pp. 449–450. Springer, Berlin, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74610-2_40
Van Nieuwenborgh, D., De Cock, M., Vermeir, D.: An introduction to fuzzy answer set programming. Ann. Math. Artif. Intell. 50(3), 363–388 (2007). https://doi.org/10.1007/s10472-007-9080-3
Acknowledgements
The research reported in this paper was supported by the grant UK/244/2018.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Uhliarik, I. (2019). Foundations of a DPLL-Based Solver for Fuzzy Answer Set Programs. In: Sabourin, C., Merelo, J.J., Madani, K., Warwick, K. (eds) Computational Intelligence. IJCCI 2017. Studies in Computational Intelligence, vol 829. Springer, Cham. https://doi.org/10.1007/978-3-030-16469-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-16469-0_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16468-3
Online ISBN: 978-3-030-16469-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)