| Revista: | Computación y sistemas |
| Base de datos: | |
| Número de sistema: | 000560668 |
| ISSN: | 1405-5546 |
| Autores: | Ita, Guillermo De1 Bello, Pedro1 |
| Instituciones: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, México |
| Año: | 2022 |
| Periodo: | Ene-Mar |
| Volumen: | 26 |
| Número: | 1 |
| Paginación: | 59-70 |
| País: | México |
| Idioma: | Inglés |
| Resumen en inglés | Let K be a propositional formula and let ϕ be a query, the propositional inference problem K ⊨ ϕ is a Co-NP-complete problem for propositional formulas without restrictions. We show the existence of polynomial-time cases for some fragments of propositional formulas K and ϕ that are different from the already known case of Horn formulas. For example, in the case that K is a formula in the fragment Krom or Horn or Monotone, then K ⊨ ϕ can be decided in polynomial-time for any CNF ϕ. Given two conjunctive normal forms (CNF’s) K and ϕ, when K ⊭ ϕ, our proposal builds a minimal set of independent clauses S. The falsifying assignments of S are exactly the subset of models of K, which are not models for ϕ. In this way, the CNF S could extend the initial formula K in such a way that repair the inference, it is ( S ∪ K ) ⊨ ϕ is held. |
| Keyword: | Propositional inference, Repairing inference, Reasoning s, NP-complete, Co-NP-complete |
| Texto completo: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
