Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/130972
COMPARTIR / EXPORTAR:
SHARE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | The Complexity of 3-Valued Lukasiewicz Rules |
Autor: | Bofill, Miquel; Manyà, Felip CSIC ORCID ; Vidal, Amanda; Villaret, Mateu | Palabras clave: | Boolean algebra Satisfiability Problem solving Satisfiability problems |
Fecha de publicación: | 2015 | Editor: | Springer Nature | Citación: | Lecture Notes in Computer Science, 12th International Conference on Modeling Decisions for Artificial Intelligence, MDAI 2015; Skovde; Sweden; 21 September 2015 through 23 September 2015; vol. 9321, pp. 221-229, 2015. | Resumen: | It is known that determining the satisfiability of n-valued Łukasiewicz rules is NP-complete for n ≥ 4, as well as that it can be solved in time linear in the length of the formula in the Boolean case (when n = 2). However, the complexity for n = 3 is an open problem. In this paper we formally prove that the satisfiability problem for 3-valued Łukasiewicz rules is NP-complete. Moreover, we also prove that when the consequent of the rule has at most one element, the problem is polynomially solvable. © Springer International Publishing Switzerland 2015. | Versión del editor: | http://link.springer.com/chapter/10.1007/978-3-319-23240-9_18 | URI: | http://hdl.handle.net/10261/130972 | DOI: | 10.1007/978-3-319-23240-9_18 | ISBN: | 978-331923239-3 | ISSN: | 03029743 |
Aparece en las colecciones: | (IIIA) Libros y partes de libros |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
LNCS9321_221-229.pdf | 266,41 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
Page view(s)
182
checked on 22-abr-2024
Download(s)
374
checked on 22-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.