Chandru, V. ; Hooker, J. N. (1992) Detecting embedded horn structure in propositional logic Information Processing Letters, 42 (2). pp. 109-111. ISSN 0020-0190
![[img]](https://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Publisher Version
117kB |
Official URL: http://linkinghub.elsevier.com/retrieve/pii/002001...
Related URL: http://dx.doi.org/10.1016/0020-0190(92)90098-G
Abstract
We show that the problem of finding a maximum renamable Horn problem within a propositional satisfiability problem is NP-hard but can be formulated as a set packing and therefore a maximum clique problem, for which numerous algorithms and heuristics have been developed.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Computational Complexity; Renamable Horn Problems; Satisfiability |
| ID Code: | 5540 |
| Deposited On: | 19 Oct 2010 11:58 |
| Last Modified: | 16 May 2016 16:02 |
Repository Staff Only: item control page
