Título

The Incremental Satisfiability Problem for a Two Conjunctive Normal Form

Autor

GUILLERMO DE ITA LUNA

JOSE RAYMUNDO MARCIAL ROMERO

JOSE ANTONIO HERNANDEZ SERVIN

Nivel de Acceso

Acceso Abierto

Licencia

http://creativecommons.org/licenses/by-nc-sa/4.0

Materias

satisfiability problem - ([1571-0661]) incremental satisfiability problem - ([1571-0661]) 2-sat - ([1571-0661]) entail propositional problem - ([1571-0661]) INGENIERÍA Y TECNOLOGÍA - (CTI)

Resumen o descripción

We propose a novel method to review K ⊢ φ when K and φ are both in Conjunctive Normal Forms (CF). We extend our method to solve the incremental satisfiablity problem (ISAT), and we present different cases where ISAT can be solved in polynomial time. Especially, we present an algorithm for 2-ISAT. Our last algorithm allow us to establish an upper bound for the time-complexity of 2-ISAT, as well as to establish some tractable cases for the 2-ISAT problem.

Editor

ELSEVIER

Fecha de publicación

1 de enero de 2016

Tipo de publicación

Artículo

Recurso de información

http://hdl.handle.net/20.500.11799/67669

Fuente

1571-0661

Idioma

Inglés

Relación

328;

Audiencia

Estudiantes

Investigadores

Repositorio Orígen

REPOSITORIO INSTITUCIONAL DE LA UAEM

Descargas

231