2024-03-29T11:23:40Zhttp://digital.csic.es/dspace-oai/requestoai:digital.csic.es:10261/1593162018-08-02T08:55:44Zcom_10261_60com_10261_4col_10261_439
2018-01-19T11:36:33Z
urn:hdl:10261/159316
Finding Hard Instances of Satisfiability in Lukasiewicz Logics
Bofill, Miquel
Manyà, Felip
Vidal, Amanda
Villaret, Mateu
Ministerio de Economía y Competitividad (España)
Ministerio de Educación, Cultura y Deporte (España)
Generalitat de Catalunya
Becnhmarks
Complexity
Easy-hard-easy pattern
Satisfiability
Phase transition
Lukasiewicz logics
One aspect that has been poorly studied in multiple-valued logics, and in particular in Lukasiewicz logics, is the generation of instances of varying difficulty for evaluating, comparing and improving satisfiability solvers. In this paper we present a new class of clausal forms, called Lukasiewicz L-clausal forms, motivate their usefulness, study their complexity, and report on an empirical investigation that shows an easy-hard-easy pattern and a phase transition phenomenon when testing the satisfiability of L-clausal forms. © 2015 IEEE.
2018-01-19T11:36:33Z
2018-01-19T11:36:33Z
2015-05-18
2018-01-19T11:36:34Z
comunicación de congreso
Proceedings of the 5th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2015: 30-35
http://hdl.handle.net/10261/159316
http://dx.doi.org/10.13039/501100003329
http://dx.doi.org/10.13039/501100003176
http://dx.doi.org/10.13039/501100002809
eng
Publisher's version
Sí
MINECO/TIN2011-27076-C03-03; MINECO/TIN2012-39348-C02-01; MINECO/TIN2012-33042
openAccess
Institute of Electrical and Electronics Engineers. Computer Group